【作者】 汪恭书；

【导师】 唐立新；

【作者基本信息】 东北大学 ， 物流优化与控制， 2008， 博士

【摘要】 铁钢区的批量计划和物流调度是钢铁企业生产运作管理中急需解决的重大关键问题,科学的制定有利于提高生产效率和资源利用率、降低生产成本和能源消耗。由于铁钢区的批量计划和物流调度问题都可归结为NP-Hard的组合最优化问题,因此,探讨适合这类问题的有效和实用算法已成为学术界和工业界关注的热点研究课题。列生成作为一种重要的最优化技术,与其他算法相结合已经成功地求解许多NP-Hard的经典组合最优化问题,获得问题的最优解或次优解。本文从影响列生成算法性能的要素出发,分别针对算法体系结构、价格子问题的求解以及整数解的获取三个方面进行了理论和改进研究；并以从铁钢区提炼出来的炼钢—连铸Lot批量计划问题、炼钢—连铸浇次批量计划问题、铁水流向分配问题、铁水机车调度问题为背景,对列生成方法进行了应用研究。针对铁钢区的实际炼钢—连铸批量计划问题,设计并提出了有效的智能优化算法,以此为核心开发了相应的决策支持系统。具体内容概括如下：1)算法体系结构改进。将基于次梯度的拉格朗日松弛(LR)算法嵌入列生成算法框架中,形成拉格朗日松弛和列生成的混合算法。该算法包含双重迭代,在内环通过求解拉格朗日松弛子问题和基于次梯度更新乘子来获得LR对偶问题的下界同时生成列；在外环将内环生成的负消减费用列加入限制主问题,通过求解获得其最优解(对应LR对偶问题的上界)以及影子价格,并将影子价格同历史最好次梯度乘子进行加权组合并传递给内环作为初始乘子。以炼钢—连铸Lot批量计划问题为研究对象,对该算法进行了应用研究。对该问题建立一个混合整数规划模型,通过松弛模型中一组耦合约束获得拉格朗日松弛问题,并将其分解为两级子问题,分别设计了有效动态规划算法,进一步将LR对偶问题等价转换为适合列生成的粗放型线性规划模型,从而结合基于次梯度的拉格朗日松弛算法和列生成算法,形成LR&CG混合算法,共同求解LR对偶问题。2)求解价格子问题方法的改进。提出三种不同改进策略,包括：状态空间松弛技术、降低搜索空间策略以及基于启发式生成列的策略。(1)状态空间松弛技术以消弱主问题的下界为代价,来降低价格子问题的复杂度,从而加速价格子问题的求解。以铁水流向分配问题为研究对象,进行了该策略的应用研究。通过对NP-Hard单机调度子问题的状态空间进行松弛而设计了一个伪多项式动态规划算法,同时允许单机子问题的伪调度(列)加入限制主问题,从而对子问题求解的加速和主问题下界的削弱进行了折衷,提高了算法的整体性能。(2)降低搜索空间策略主要是针对那些采用探索技术获得价格子问题最优解的方法,通过对价格子问题性质的分析,识别那些不可能扩充为最优解的部分解,将其尽早排除,从而节约搜索无效空间带来的计算时间。以炼钢—连铸浇次批量计划问题和铁水机车调度问题为研究对象,分别进行了该策略的应用研究。炼钢—连铸浇次批量计划问题列生成算法的价格子问题可归结为带有资源约束“族单元”最短路径问题,为该问题设计了广义Dijkstra算法,提出统治规则和标签下界估值来抑制标签的快速增殖,从而限制了无效的搜索空间,提高价格子问题的求解效率。这个策略还可扩展到铁水机车调度问题列生成算法的价格子问题,归结为带有非线性目标函数和时间约束的“单元”最短路径问题。(3)基于启发式生成列的策略是在列生成算法迭代的初始阶段,采用启发式生成负消减费用列,从而降低价格子问题最优求解的复杂性,节约计算时间。以炼钢—连铸浇次批量计划问题列生成算法的价格子问题为例,针对当前基变量对应的列,采用贪婪思想进行先插入后删除,由此形成新的负消减费用列,并加入限制主问题。以炼钢—连铸Lot批量计划问题的拉格朗日松弛子问题为例,通过对子问题进一步松弛获得松弛子问题的最优解,基于此改造获得子问题的可行解,从而搜寻合适的下降方向和负消减费用列。3)整数解的获取。提出三类不同方法获取最优或次优整数解,即分枝—定界,基于列生成的分数解改造策略和基于拉格朗日松弛问题解的改造策略。(1)通过探究原模型同Dantzig-Wolfe分解模型之间变量的等价关系和问题自身的性质,提出有效分枝策略,从而实现基于列生成的分枝—价格算法获取最优解,应用于炼钢—连铸浇次批量计划问题、铁水流向分配问题以及铁水机车调度问题。(2)通过改造列生成算法所获得的最优分数解来获取原问题的整数解(上界),包含两种不同类型的改造。针对炼钢—连铸浇次批量计划问题,基于当前分数解,采用一种过滤策略获取部分整数解,剩余的列和行构成降维问题,进行新一轮的列生成。最后对获得的整数解进行局域搜索来获得改进,并且仅在根节点处执行该策略,不执行分枝操作。针对铁水机车调度问题,在每个分枝节点都针对分数解进行改造,首先通过计算任务和机车之间的分配关系,然后按照字典序关系将任务插入机车调度。这种策略试图在分枝树上搜寻较好上界,以帮助修剪分枝节点、抑制分枝树的规模。(3)拉格朗日松弛算法中,常对拉格朗日松弛问题的最优解进行改造来得到原问题的可行解,称为LR启发式,但LR启发式没有固定的实现模式。在炼钢—连铸Lot批量计划问题的LR&CG混合算法中,通过固定Lot的选取,以及松弛部分约束,将原问题转化为线性规划的运输问题,获得分数解后再进行舍入取整获取可行整数解。4)针对考虑复杂因素的实际炼钢—连铸批量计划问题,通过分析问题的工艺、管理约束和要求,抽取问题的关键特征,建立符合生产实际的数学模型,提出有效的启发式和禁忌搜索算法,并以模型算法为核心开发决策支持系统,进行实际应用验证。通过对实际数据的测试,验证算法的有效性和系统的稳定性。更多还原

【Abstract】 In iron and steel industry, the batching decision and logistics scheduling problems arising in ironmaking and steelmaking area are key and urgent issues of production management. Scientific solving those problems can help to improve productivity and resource utilization, to reduce production cost and energy consumption. Since most of those problems can be reduced to combinational optimization problems belong to NP-Hard, it becomes a hot research topic to investigate the efficient and suitable models and algorithms, which are curretly focused by both academic and industrial communities. As an important optimization technique, column generation combined with other algorithms has been successfully used to solve a great deal of classical combinatorial optimization problems belong to NP-Hard, by which the optimal or near optimal solutions are obtained. This dissertation makes basic research on the theory and improvement of column generation and its application research on Lot batching problem, cast batching problem, molten iron allocation problem and molten iron locomotive scheduling problem. Based on the structure of column generation and the key factors affecting algorithm performance, this algorithm is improved respectively from the following three aspects, i.e. framework of algorithm, solving pricing subproblems and obtaining integer solutions. For the practical batching decision problems, the effective algorithm besed one intelligent optimization is proposed. By embedding this algorithm, the decision support systems (DSS) software with interactive planning editor is developed. The content of the dissertation is summarized as follows.1) Improving the framework of algorithm. By embedding the subgradient based Lagrangian relaxation algorithm into the column generation framework, a new combined algorithm named LR&CG is proposed, which consists of nested double loops. In the inner loop, the Lagrangian subproblem is solved within a fixed number of iterations, and the subgradient method is employed to update Lagrangian multipliers at each iteration, and the valid lower bound and the columns corresponding to solutions of Lagrangian subproblem are obtained. In the outer loop, the columns with negative reduced costs are added to the restricted master problem, which is then solved and the upper bound of LR dual problem and shadow prices are obtained. At the initialization of the inner loop, Lagrangian multipliers are initialized as weighted decomposition of shadow prices of the restricted master problem and the best Lagrangian multipliers found so far. Its application is then studied for solving the lot batching problem in steelmaking and continuous casting. The problem is formulated as a mixed integer programming, and then the Lagrangian relaxation problem is obtained by decoupling assignment constraints which is further decomposed into two-level subproblems. Two dynamic programming algorithms are designed for solving two level subproblems respectively. The Lagrangian dual problem is transformed into an extensive linear programming which is suitable to be solved by column generation. Finally, subgradient based Lagrangian relaxation and column generation algorithms are combined to solve the Lagrangian dual problem.2) Improving the methods of solving pricing subproblems. Three different strategies are proposed for solving pricing subproblems, and they are state space relaxation, reducing search space and generating columns by heuristics, resepectively.(1) At the cost of loosing the lower bound of the master problem, state space relaxation is introduced to reduce the complexity of pricing subproblem and to accelerate the solving of pricing subproblem. Its application is put on the molten iron allocation problem. By relaxing the state space of the pricing subproblem problem which is NP-hard single machine scheduling problem, a pseudo polynomial dynamic programming algorithm is designed to obtain columns corresponding to pseudo schedules or feasible schedules. The columns obtained are allowed to add to the restricted master problem. This strategy is a compromise between the dynamic programming algorithm for the subproblem and the branch-and-bound algorithm for the master problem.(2) Reducing search space is actived when the exploring techniques are adopted to obtain the optimal solutions of pricing subproblems. In exploring technique, the partial schedules which are impossible to expand to the optimal schedule are recognized by analyzing the problem characters, and they are excluded for further expanding as early as possible, so that the CPU time for searching unpromising space is saved. Its application is put on both cast batching problem in steelmaking and continuous casting and molten iron locomotive scheduling problem. The pricing subproblem of the former can be reduced to "family elementary" shortest path problem with resource constraints. The generalization of famous Dijkstra algorithm is designed to solve it, then dominant rules and lower bound estimation of labels is introduced to suppress proliferation of labels. Based on above two techniques, unpromising space is restricted, and therefore efficiency of solving pricing subproblem is improved. Such techniques can be further extended to the pricing subproblem of molten iron locomotive scheduling problem, which can be reduced to an elementary shortest path problem with nonlinear objective and time windows constraints.(3) In the beginning, columns with negative reduced costs can be generated by heuristics to reduce the complexity of optimization methods of pricing subproblem and accordingly to save computational time. In the cast batching problem, the basic idea of such approach is to generate new columns with a negative reduced cost by modifying existing columns with a zero reduced cost. For the lot batching problem, Lagrangian subproblems are solved at the relaxed version, and a rounding procedure is employed to obtain the feasible solutions of Lagrangian subproblems in the begining of LR&CG algorithm. It aims to find columns with negative reduced costs for restricted master problem and to find an appropriate descended direction for Lagrangian relaxation algorithm.3) Obtaining integer solutions. Three different methods are proposed to obtain optimal or near optimal integer solutions, they are branch-and-bound, heuristics based on the frictional optimal solution obtained by column generation, heuristics based on the solution of Lagrangian relaxation problem.(1) By exploiting the relationship between variables of the original compact mixed integer programming and variables of the Dantzig-Wolfe decomposition formulation, the effective branching strategy is proposed and the branch-and-bound procedure is employed to obtain the optimal solution. Its application is put on the cast batching problem in steelmaking and continuous casting, molten iron allocation problem and molten iron locomotive scheduling problem, respectively.(2) The integer solution is obtained by transforming the fraction optimal solution from column generation, and two types of such strategies are proposed in this dissertation. The first one deals with the cast batching problem. Based on the optimal fraction solution of linear relaxation of master problem, a filtration strategy is employed to select some columns which are stored as part of integer solution, and then a reduced problem is obtained by deleting corresponding columns and rows, and column generation is re-executed on the reduced problem. The obtained integer solution is further improved by local search. Note that such process is not invoked at any node other than the root node of the branch-and-bound tree. The second one deals with molten iron locomotive scheduling problem in which heuristics of transforming fraction solution into integer solution is invoked at all nodes. It first calculates the assignment values between tasks and locomotives, and then schedule for each locomotive is constructed or expanded step by step according to assignment values and feasibility of insertion. Searching feasible solutions at each node of the branch-and-bound tree may considerably reduce the overall computing time needed to reach a provably optimal solution.(3) The integer solution is obtained by transforming the optimal solution of Lagrangian relaxation problem, which is often used in Lagrangian relaxation algorithm. However, no routine is existed for such transforming. In the LR&CG algorithm for lot batching problem, a heuristics is proposed by fixing lot selection decision variables, and converting the original problem into a linear programming transportation problem, which is easy to obtain fraction solution. The rounding procedure is employed to transform the fraction solution into a feasible solution.4) After analyzing the technologic constraints and management requirements, the key characters of the practical steelmaking and continuous casting batching decision problems are abstracted and taken into account. According to those characters, two mathematical models are developed, and then the effective dynamic programming based the heuristics and the tabu search algorithms are proposed. Based on the models and solution approaches, the decision support system is developed, and has been tested using the practical production data collected from an most advanced iron and steel complex in China, the computational experiments are carried out and the computational results verify the efficiency of solution approaches and stability of system.更多还原