基于列生成的铁钢区批量计划与物流调度
|
摘要
铁钢区的批量计划和物流调度是钢铁企业生产运作管理中急需解决的重大关键问题,科学的制定有利于提高生产效率和资源利用率、降低生产成本和能源消耗。由于铁钢区的批量计划和物流调度问题都可归结为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)针对考虑复杂因素的实际炼钢—连铸批量计划问题,通过分析问题的工艺、管理约束和要求,抽取问题的关键特征,建立符合生产实际的数学模型,提出有效的启发式和禁忌搜索算法,并以模型算法为核心开发决策支持系统,进行实际应用验证。通过对实际数据的测试,验证算法的有效性和系统的稳定性。
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.
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)针对考虑复杂因素的实际炼钢—连铸批量计划问题,通过分析问题的工艺、管理约束和要求,抽取问题的关键特征,建立符合生产实际的数学模型,提出有效的启发式和禁忌搜索算法,并以模型算法为核心开发决策支持系统,进行实际应用验证。通过对实际数据的测试,验证算法的有效性和系统的稳定性。
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.
引文
[1]Tang L X, Liu J Y, Rong A Y, Yang Z H. A review of planning and scheduling systems and methods for integrated steel production [J], European Journal of Operational Research,2001,133:1-20.
[2]唐立新CIMS下生产批量计划理论及其应用[M],北京：科学出版社,1999.
[3]Vasko F J. Using facility location algorithm to solve large set covering problem [J], Operations Research Letters,1984,3:85-90.
[4]Vasko F J, Wilson G R. An efficient heuristic for large scale set covering problems [J], Naval Research Logistics,1984,33:241-249.
[5]Vasko F J, Wolf F W, Stott K L. Optimal selection of ingot sizes via set covering [J], Operations Research,1987,35:346-352.
[6]Vasko F J, Wolf F W. Solving large set covering problems on a personal computer [J], Computers and Operations Research,1988,15:115-121.
[7]Vasko F J, Wolf F E. A set covering approach to metallurgical grade assignment [J], European Journal of Operational Research,1989,38:27-34.
[8]Vasko F J, Wolf F E, Stott K L, Scherier J W. Selecting optimal ingot size for bethlehem steel [J], Interfaces,1989,19(1):68-83.
[9]Vasko F J, Cregger M L, Stott K L, Woodyatt L R. Assigning slabs to orders-an example of appropriate model formulation [J], Computers and Industrial Engineering,1994,26: 797-800.
[10]Dorn J, Shams R. Scheduling high-grade steelmaking [J], IEEE Expert,1996,11(1): 28-35.
[11]Box R E, Herbe D G. A scheduling model for LTV Steel's Cleveland works'twin strand continuous slab caster [J], Interfaces,1988,18(1):42-56.
[12]Lee H S, Murthy S S, Haider S W, Morse D V. Primary production scheduling at steel making industries [J], IBM Journal of Research and Development,1996,40(2): 231-252.
[13]Chang S Y, Chang M R, Hong Y S. A lot grouping algorithm for a continuous slab caster in an integrated steel mill [J], Production Planning & Control,2000,11:363-368.
[14]Harjunkoski I, Grossmann I E. A decomposition approach for the scheduling of steel plant production [J], Computers & Chemical Engineering,2001,25:1647-1660.
[15]Dorn J, Kerr R. Co-operating scheduling systems communicating through Fuzzy sets [A], IFAC Intelligent Manufacturing Systems [C], Vienna, Austria,1994,449-455.
[16]Tamura R, Nagai M, Nakagawa Y, Tanizaki T, Nakajima H. Functionally partitioned scheduling system equipped with two-stage scheduling algorithm in steel sheet manufacturing [J], Instruments and Automatic Control,1995,8(10):592-601.
[17]Craiga I K, Camisani-Calzolaria F R, Pistoriusb P C. A contemplative stance on the automation of continuous casting in steel processing [J], Control Engineering Practice, 2001,9:1013-1020.
[18]Roy R, Adesola B A, Thornton S. Development of a knowledge model for managing schedule disturbance in steel-making [J], International Journal of Production Research, 2004,42(18):3975-3994.
[19]Pacciarelli D, Pranzo M. Production scheduling in a steelmaking continuous casting plant [J], Computers & Chemical Engineering,2004,28:2823-2835.
[20]Kumar V, Kumar S, Tiwari M K. Auction-based approach to resolve the scheduling problem in the steel making process [J], International Journal of Production Research,2006,44(8): 1503-1522.
[21]Bellabdaoui A, Teghem J. A mixed-integer linear programming model for the continuous casting planning [J], International Journal of Production Economics,2006, 104(2):260-270.
[22]Zanoni S, Zavanella L. Model and analysis of integrated production-inventory system: The case of steel production [J], International Journal of Production Economics,2005, 93-94:197-205.
[23]Ferretti I, Zanoni S, Zavanella L. Production-inventory scheduling using Ant System metaheuristic [J], International Journal of Production Economics,2006,104:317-326.
[24]Missbauer H, Hauber W, Stadler W. A scheduling system for the steelmaking continuous casting process of a steel plant [A], INFORMS [C], HongKong,25-28, June,2006.
[25]Tang L X, Liu J Y, Rong A Y, Yang Z H. A mathematical programming model for scheduling steelmaking-continuous casting production [J], European Journal of Operational Research,2000,120:423-435.
[26]Tang L X, Luh P B, Liu J Y, Fang L. Steelmaking process scheduling using Lagrangian relaxation [J], International Journal of Production Research,2002,40(1):55-70.
[27]铃木節也,藤原義已,西海建一.溶銑输送管理ッステム[J],神户制钢技报,1995,30(2)：48-50.
[28]田村昌弘,稲葉佑三,古贺康彦,有阑德美,何合登,入谷英樹.溶铣物流システムの改善[J],神户制钢技报,1996,46(2)：15-18.
[29]Lubbecke, M E. Engine scheduling by column generation [D], Braunschweig University of Technology,2001.
[30]Lubbecke M E, Zimmermann U T. Engine routing and scheduling at industrial in-plant railroads [J], Transportation Science,2003,37 (2):183-197.
[31]Imai T, Nakagawa Y, Kumamoto K, Nohira M, Yamaguchi T. Multistage job shop scheduling with complex material handling system [A], Proceedings of Production Scheduling Symposium [C],1996,151-156. (in Japanese)
[32]Imai T, Asada K, Nakagawa Y, Kumamoto K, Nohira M. A scheduling system for the steel-making process using a general approach [J], Transactions of the Institute of Systems, Control and Information Engineers,1997,10(4):204-210. (in Japanese)
[33]Tamura T, Tanizaki T, Imai T, Kumamoto K. Development of a scheduling algorithm at steel making plant [A], Proceedings of Scheduling Symposium [C],2002,140-145. (in Japanese)
[34]Honda N, Mouri S, Ishii H. Steel making process scheduling with crane interference [A], Proceedings of Scheduling Symposium [C],2002,108-113. (in Japanese)
[35]Tanizaki T, Tamura T, Sakai H, Takahashi Y, Imai T. A heuristic scheduling algorithm for steel making process with crane handling [J], Journal of the Operations Research Society of Japan,2006,49(3):188-201.
[36]Dantzig G B, Wolfe P. Decomposition principle for linear programs [J], Operations Research,1960,8:101-111.
[37]Gilmore P, Gomory R. A linear programming approach to the cutting stock problem [J], Operations Research,1961,9:849-859.
[38]Desrosiers J, Soumis F, Desrochers M. Routing with time windows by column generation [J], Networks,1984,14:545-565.
[39]Barnhart C, Johnson E L, Nemhauser G L, Savelsbergh M W P, Vance P H. Branch-and-Price:column generation for solving huge integer programs [J], Operations Research,1998,46(3):316-329.
[40]Vanderbeck F. Decomposition and column generation for integer programs [D], Universite catholique de Louvain,1994.
[41]Desaulniers G, Desrosiers J, Solomon M M. Accelerating strategies in column generation methods for vehicle routing and crew scheduling problems [J], Les Cahiers du GERAD G-99-36, Ecole des Hautes Etudes Commerciales, Montreal, Canada,1999.
[42]姚恩瑜,何勇,陈仕平.数学规划与组合优化[M],浙江：浙江大学出版社,2001.
[43]运筹学教材编写组.运筹学[M],北京：清华大学出版社,1991.
[44]Vanderbeck F. On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a Branch-and-Price algorithm [J], Operations Research,2000, 48(1):111-128.
[45]Nemhauser G L, Wolsey L A. Integer and Combinatorial Optimization [M], Chichester, England:Wiley,1988.
[46]Manne A S. Programming of economic lot sizes [J], Management Science,1958,4(2): 115-135.
[47]Sol M, Savelsbergh M W P. A Branch-and-Price algorithm for the pickup and delivery problem with time windows [J], Report COC-94-06, Georgia Institute of Technology, Atlanta, Georgia,1994.
[48]Lavoie S, Minoux M, Odier E. A new approach for crew pairing problems by column generation with an application to air transportation [J], European Journal of Operational Research,1988,35(1):45-58.
[49]Anbil R, Tanga R, Johnson E L. A global approach to crew-pairing optimization [J], IBM Systems Journal,1993,31:71-78.
[50]Skitt R A, Levary R R. Vehicle routing via column generation [J], European Journal of Operational Research,1985,21(1):65-76.
[51]Savelsbergh M W P. A branch and price algorithm for the generalized assignment problem [J], Operations Research,1996,45(6):831-841.
[52]Vance P H, Barnhart C, Johnson E L, Nemhauser G L. Solving binary cutting stock problems by column generation and branch-and-bound [J], Report COC-92-09, Computational Optimization Center, Georgia Institute of Technology, Atlanta, Georgia, 1992.
[53]Ryan D M, Foster B A. An integer programming approach to scheduling [J]. In:Wren A (ed.). Computer Scheduling of Public Transport:Urban Passenger Vehicle and Crew Scheduling. Amsterdam:North-Holland Publishing,1981,269-280.
[54]Gilmore P, Gomory R. A linear programming approach to the cutting stock problem-Part II [J], Operations Research,1963,11:863-888.
[55]Valerio de Carvalho J M, Guimaraes Rodrigues A J. An LP based approach to a two-phase cutting stock problem [J], European Journal of Operational Research,1995, 84:580-589.
[56]Vance P H. Branch-and-Price algorithms for the one-dimensional cutting stock problem [J], Computational Optimization and Applications,1998,9:211-228.
[57]Kantorovich L. Mathematical methods of organising and planning production (translated from a report in Russian, dated 1939) [J], Management Science,1960,6: 366-422.
[58]Chauhan S S, Alain M, Sophie D A. Roll assortment optimization in a paper mill:An integer programming approach [J], Computers & Operations Research,2008,35: 614-627.
[59]Dumas Y, Desrosiers J, Soumis F. The pick-up and delivery problem with time windows [J], European Journal of Operational Research,1991,54:7-22.
[60]Desrochers M, Desrosiers J, Solomon M M. A new optimization algorithm for the vehicle routing problem with time windows [J], Operations Research,1992,40: 342-354.
[61]Desaulniers G, Lavigne J, Soumis F. Multi-depot vehicle scheduling problems with time windows and waiting costs [J], European Journal of Operational Research,1998, 111:479-494.
[62]Palmgren M, Ronnqvist M, Varbrand P. A near-exact method for solving the log-truck scheduling problem [J], International Transactions in Operational Research,2004,11: 447-464.
[63]Xu H, Chen Z L, Rajagopal S, Arunapuram S. Solving a practical pickup and delivery problem [J], Transportation Science,2003,37(3):347-364.
[64]Chen Z L, Xu H. Dynamic column generation for dynamic vehicle routing with time windows [J], Transportation Science,2006,40(1):74-88.
[65]Christiansen C H, Lysgaard J. A Branch-and-Price algorithm for the capacitated vehicle routing problem with stochastic demands [J], Operations Research Letters,2007,35(6): 773-781.
[66]Chen Z L, Powell W B. Solving parallel machine scheduling problems by column generation [J], INFORMS Journal on Computing,1999,11:78-94.
[67]Van den Akker J M, Hoogeveen J A, Van de Velde S L. Parallel machine scheduling by column generation [J], Operations Research,1999,47:862-872.
[68]Chen Z L, Powell W B. A column generation based decomposition algorithm for a parallel machine just-ih-time scheduling problem [J], European Journal of Operational Research,1999,116:220-232.
[69]Lee C Y, Chen Z L. Scheduling jobs and maintenance activities on parallel machines [J], Naval Research Logistics,2000,47:145-165.
[70]Chen Z L, Lee C Y. Parallel machine scheduling with a common due window [J], European Journal of Operational Research,2002,136:512-527.
[71]Chen Z L, Powell W B. Exact algorithms for scheduling multiple families of jobs on parallel machines [J], Naval Research Logistics,2003,50:823-840.
[72]Bard J F, Rojanasoonthon S. A Branch-and-Price algorithm for parallel machine scheduling with time windows and job priorities [J], Naval Research Logistics,2006,53: 24-44.
[73]Pereira Lopes M J, Valerio de Carvalho J M. A Branch-and-Price algorithm for scheduling parallel machines with sequence dependent setup times [J], European Journal of Operational Research,2007,176:1508-1527.
[74]Oguz O. Generalized column generation for linear programming [J], Management Science,2002,48(3):444-452.
[75]Jaumard B, Marcotte O, Meyer C, Vovor T. Comparison of column generation models for channel assignment in cellular networks [J], Discrete Applied Mathematics,2001, 112:217-240.
[76]Hemazro T D, Jaumard B, Marcotte O. A column generation and branch-and-cut algorithm for the channel assignment problem [J]. Computers & Operations Research, 2008,35(4):204-1226.
[77]Bard J F, Purnomo H W. A column generation-based approach to solve the preference scheduling problem for nurses with downgrading [J], Socio-Economic Planning Sciences,2005,39(3):193-213.
[78]Bard J F, Purnomo H W. Preference scheduling for nurses using column generation [J], European Journal of Operational Research,2005,164(2):510-534.
[79]Valerio de Carvalho J M. Exact solution of bin-packing problems using column generation and branch-and-bound [J], Annals of Operational Research,1999,86: 629-659.
[80]Valerio de Carvalho J M. LP models for bin-packing and cutting stock problems [J], European Journal of Operational Research,2002,141(2):253-273.
[81]Degraeve Z, Jans R. A new Dantzig-Wolfe reformulation and Branch-and-Price algorithm for the capacitated lot-sizing problem with setup times [J], Operations Research,2007,55(5):909-920.
[82]Van den Akker J M, Hurkens C A J, Savelsbergh M W P. Time-indexed formulations for single-machine scheduling problems:column generation [J], INFORMS Journal on Computing,2000,12:111-124.
[83]Valerio de Carvalho J M. Using extra dual cuts to accelerate column generation [J], INFORMS Journal on Computing,2005,17(2):175-182.
[84]Alves C, Valerio de Carvalho J M. Accelerating column generation for variable sized bin-packing problems [J], European Journal of Operational Research,2007,183: 1333-1352.
[85]Degraeve Z, Peeters M. Optimal integer solutions to industrial cutting-stock problems: Part 2, benchmark results [J], INFORMS Journal on Computing,2003,15:58-81.
[86]Oukil A, Ben Amor H, Desrosiers J, Gueddari H E. Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems [J], Computers& Operations Research,2007,34:817-834.
[87]Desaulniers G. Managing large fixed costs in vehicle routing and crew scheduling problems solved by column generation [J], Computers & Operations Research,2007, 34(4):1221-1239.
[88]Desaulniers G, Desrosiers J, Dumas Y, Solomon M M, Soumis F. Daily aircraft routing and scheduling [J], Management Science,1997,841-855.
[89]Choi E, Tcha D W. A column generation approach to the heterogeneous fleet vehicle routing problem [J], Computers & Operations Research,2007,34(7):2080-2095.
[90]Chabrier A. Vehicle Routing Problem with elementary shortest path based column generation [J], Computers & Operations Research,2006,33:2972-2990.
[91]Feillet D, Dejax P, Gendreau M, Gueguen C. An exact algorithm for the elementary shortest path problem with resource constraints:application to some vehicle routing problems [J], Networks,2004,43(3):216-229.
[92]Ceselli A, Righini G. A Branch-and-Price Algorithm for the multilevel generalized assignment problem [J], Operations Research,2006,54(6):1172-1184.
[93]Fei H, Chu C, Meskens N, Artiba A. Solving surgical cases assignment problem by a Branch-and-Price approach [J], International Journal Production Economics, In Press.
[94]Klose A, Drexl A. Lower bounds for the capacitated facility location problem based on column generation [J], Management Science,2005,51:1689-1705.
[95]Klose A, Gortz S. A Branch-and-Price algorithm for the capacitated facility location problem [J], European Journal of Operational Research,2007,179:1109-1125.
[96]Van den Akker J M, Hoogeveen J A, Van de Velde S L. Combining column generation and Lagrangean relaxation to solve a single-machine common due date problem [J], INFORMS Journal on Computing,2002,14:37-51.
[97]Jans R, Degraeve Z. An industrial extension of the discrete lot sizing and scheduling problem [J],IIE Transactions,2004,36:47-58.
[98]Huisman D, Jans R, Peeters M, Wagelmans A P M. Combining column generation and Lagrangian relaxation, Column Generation [M], Springer,2005,247-270.
[99]Brucker P, Knust S. A linear programming and constraint propagation-based lower bound for the RCPSP [J], European Journal of Operational Research,2000,127(2): 355-362.
[100]Fahle T, Junker U, Karisch S E, Kohl N, Sellmann M, Vaaben B. Constraint programming based column generation for crew assignment [J], Journal of Heuristics, 2002,8:59-81.
[101]Gronkvist M. Accelerating column generation for aircraft scheduling using constraint propagation [J], Computers & Operations Research,2006,33:2918-2934.
[102]Sadykov R, Wolsey L A. Integer programming and constraint programming in solving a multimachine assignment scheduling problem with deadlines and release dates [J], INFORMS Journal on Computing,2006,18(2):209-217.
[103]Rousseau L M, Gendreau M, Pesant G. Solving VRPTWs with constraint programming based column generation [J], Annals of Operations Research,2004,130:199-216.
[104]Zak E J. Row and column generation technique for a multistage cutting stock problem [J], Computers & Operations Research,2002,29:1143-1156.
[105]Avella P, Auria B D, Salerno S. A LP-based heuristic for a time-constrained routing problem [J], European Journal of Operational Research,2006,173:120-124.
[106]Avella P, Sassano A, Vasilev I. Computational study of large-scale p-median problems [J], Mathematical Programming Serie A,2007,109:89-114.
[107]戴韬,霍佳震.钢铁企业铁水运输调度自动指令系统的实现[J],上海管理科学,2005,6：32-34.
[108]刘峰.宝钢铁水运输组织及运输能力分析[J],宝钢技术,2001,5：30-33.
[109]赵沛,成国光,沈甦.炉外精炼及铁水预处理实用技术手册[M],北京：冶金工业出版社,2004.
[110]王文瑞.宝钢铁水监控及管理系统(上)[J],冶金自动化,2001,25(4)：20-23.
[111]王文瑞.宝钢铁水监控及管理系统(下)[J],冶金自动化,2001,25(5)：16-19.
[112]董金刚.宝钢—炼钢精炼设备功能比较分析[J],炼钢,2006,22(5)：1-3.
[113]Erlenkotter D. A dual-based procedure for uncapacitated facility location [J], Operations Research,1978,26:992-1009.
[114]Sun M H. Solving the uncapacitated facility location problem using tabu search [J], Computers & Operations Research,2006,33(9):2563-2589.
[115]Cornuejols G, Nemhauser G L, Wolsey L A. The uncapacitated facility location problem, Discrete location theory [M], NewYork:Wiley,1990,119-171.
[116]Lorena L A N, Senne E L F. A column generation approach to capacitated p-median problems [J], Computers & Operations Research,2004,31(6):863-876.
[117]Senne E L F, Lorena L A N, Pereira M A. A Branch-and-Price approach to p-median location problems [J], Computers & Operations Research,2005,32:1655-1664.
[118]Fisher M L. Lagrangian relaxation method for solving integer programming [J], Management Science,1981,27:221-218.
[119]Zhao X, Luh P B, Wang J. Surrogate gradient algorithm for Lagrangian relaxation [J], Journal of Optimization Theory and Application,1999,100:699-712.
[120]Tang L X, Xuan H. Lagrangian relaxation algorithms for real-time hybrid flowshop scheduling with finite intermediate buffers [J], Journal of the Operational Research Society,2006,57(3):316-324.
[121]轩华.拉格朗日松弛的改进及在生产调度中的应用[D],东北大学,2006.
[122]Park H, Hong Y S, Chang S T. An effcient scheduling algorithm for the hot coil making in the steel mini-mill [J], Production Planning & Control,2002,13(3):298-306.
[123]Araque J R, Kudva G, Morin T L, Pekny J F. A branch and cut algorithm for the vehicle routing problem [J], Annals of Operations Research,1994,50:37-59.
[124]Letchford A N, Eglese R W, Lysgaard J. Multistars, partial multistars and the capacitated vehicle routing problem [J], Mathematical Programming,2002,94:21-40.
[125]Dror M. Note on the complexity of the shortest path models for column generation in VRPTW [J], Operations Research,1994,42:977-978.
[126]Feillet D, Dejax P, Gendreau M. Traveling salesman problems with profits [J], Transportation Science,2005,39(2):188-205.
[127]Paessens H. The savings algorithm for the vehicle routing problem [J], European Journal of Operational Research,1988,34(3):336-344.
[128]Bruno J, Coffman E G, Sethi R. Scheduling independent tasks to reduce mean finishing time [J], Communications of the ACM,1974,17:382-387.
[129]Tang L X, Wang G S, Liu J Y. A Branch-and-Price algorithm to solve the molten iron allocation problem in iron and steel industry [J], Computers & Operations Research 2007,34:3001-3015.
[130]Lenstra J K, Rinnooy Kan A H G., Brucker P. Complexity of machine scheduling problems [J], Annals of Discrete Mathematics,1977,1:343-362.
[131]Christofides N, Mingozzi A, Toth P. State-space relaxation procedures for the computation of bounds to routing problems [J], Networks,1981,11:145-164.
[132]Savelsbergh M W P, Sol M. The general pickup and delivery problem [J], Transportation Science,1995,29(1):17-29.
[133]Lu Q, Dessouky M M. A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows [J], European Journal of Operational Research,2006,175(2):672-687.
[134]Holland J. Adaption in natural and artificial systems [M], Ann Arbor:The University of Michigan Press,1975.
[135]Glover F. Tabu search:part Ⅰ. ORSA [J], Journal on Computing,1989,1:190-206.
[136]Glover F. Tabu search:part Ⅱ. ORSA [J], Journal on Computing,1990,2:4-32.
[137]Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing [J], Science,1983,220:671-680.
[138]Hopfield J. Neural networks and physical systems with emergent collective computational abilities [A], Proceedings of National Academy of Sciences [C],1982, 79:2254-2558.
[139]李韶华.钢铁原料输入物流建模及优化算法研究[D],东北大学,2006.
[140]Cowling P. A flexible decision support system for steel hot rolling mill scheduling [J], Computers & Industrial Engineering,2003,45:307-321.
[141]Lopez L, Carter M W, Gendreau M. The hot strip mill production scheduling problem:a tabu search algorithm [J], European Journal of Operational Research,1998,106: 317-335.
[142]Stauffer L, Liebling T M. Rolling horizon scheduling in a rolling mill [J], Annals of Operations Research,1997,69:323-349.
[143]Cowling P. Optimization in steel hot rolling, Optimization in industry [M], Chichester, England:Wiley,1995.
[144]den. Besten M, Stutzle T, Dorigo M. Design of iterated local search algorithms-An example application to the single machine total weighted tardiness problem [A], Applications of Evolutionary Computing Proceedings [C], Lecture Notes in Computer Science,2001,2037:441-451.
[145]Paquete L, Stutzle T. An experimental investigation of iterated local search for coloring graphs [A], Applications of Evolutionary Computing Proceedings [C], Lecture Notes in Computer Science,2002,2279:122-131.
[2]唐立新CIMS下生产批量计划理论及其应用[M],北京：科学出版社,1999.
[3]Vasko F J. Using facility location algorithm to solve large set covering problem [J], Operations Research Letters,1984,3:85-90.
[4]Vasko F J, Wilson G R. An efficient heuristic for large scale set covering problems [J], Naval Research Logistics,1984,33:241-249.
[5]Vasko F J, Wolf F W, Stott K L. Optimal selection of ingot sizes via set covering [J], Operations Research,1987,35:346-352.
[6]Vasko F J, Wolf F W. Solving large set covering problems on a personal computer [J], Computers and Operations Research,1988,15:115-121.
[7]Vasko F J, Wolf F E. A set covering approach to metallurgical grade assignment [J], European Journal of Operational Research,1989,38:27-34.
[8]Vasko F J, Wolf F E, Stott K L, Scherier J W. Selecting optimal ingot size for bethlehem steel [J], Interfaces,1989,19(1):68-83.
[9]Vasko F J, Cregger M L, Stott K L, Woodyatt L R. Assigning slabs to orders-an example of appropriate model formulation [J], Computers and Industrial Engineering,1994,26: 797-800.
[10]Dorn J, Shams R. Scheduling high-grade steelmaking [J], IEEE Expert,1996,11(1): 28-35.
[11]Box R E, Herbe D G. A scheduling model for LTV Steel's Cleveland works'twin strand continuous slab caster [J], Interfaces,1988,18(1):42-56.
[12]Lee H S, Murthy S S, Haider S W, Morse D V. Primary production scheduling at steel making industries [J], IBM Journal of Research and Development,1996,40(2): 231-252.
[13]Chang S Y, Chang M R, Hong Y S. A lot grouping algorithm for a continuous slab caster in an integrated steel mill [J], Production Planning & Control,2000,11:363-368.
[14]Harjunkoski I, Grossmann I E. A decomposition approach for the scheduling of steel plant production [J], Computers & Chemical Engineering,2001,25:1647-1660.
[15]Dorn J, Kerr R. Co-operating scheduling systems communicating through Fuzzy sets [A], IFAC Intelligent Manufacturing Systems [C], Vienna, Austria,1994,449-455.
[16]Tamura R, Nagai M, Nakagawa Y, Tanizaki T, Nakajima H. Functionally partitioned scheduling system equipped with two-stage scheduling algorithm in steel sheet manufacturing [J], Instruments and Automatic Control,1995,8(10):592-601.
[17]Craiga I K, Camisani-Calzolaria F R, Pistoriusb P C. A contemplative stance on the automation of continuous casting in steel processing [J], Control Engineering Practice, 2001,9:1013-1020.
[18]Roy R, Adesola B A, Thornton S. Development of a knowledge model for managing schedule disturbance in steel-making [J], International Journal of Production Research, 2004,42(18):3975-3994.
[19]Pacciarelli D, Pranzo M. Production scheduling in a steelmaking continuous casting plant [J], Computers & Chemical Engineering,2004,28:2823-2835.
[20]Kumar V, Kumar S, Tiwari M K. Auction-based approach to resolve the scheduling problem in the steel making process [J], International Journal of Production Research,2006,44(8): 1503-1522.
[21]Bellabdaoui A, Teghem J. A mixed-integer linear programming model for the continuous casting planning [J], International Journal of Production Economics,2006, 104(2):260-270.
[22]Zanoni S, Zavanella L. Model and analysis of integrated production-inventory system: The case of steel production [J], International Journal of Production Economics,2005, 93-94:197-205.
[23]Ferretti I, Zanoni S, Zavanella L. Production-inventory scheduling using Ant System metaheuristic [J], International Journal of Production Economics,2006,104:317-326.
[24]Missbauer H, Hauber W, Stadler W. A scheduling system for the steelmaking continuous casting process of a steel plant [A], INFORMS [C], HongKong,25-28, June,2006.
[25]Tang L X, Liu J Y, Rong A Y, Yang Z H. A mathematical programming model for scheduling steelmaking-continuous casting production [J], European Journal of Operational Research,2000,120:423-435.
[26]Tang L X, Luh P B, Liu J Y, Fang L. Steelmaking process scheduling using Lagrangian relaxation [J], International Journal of Production Research,2002,40(1):55-70.
[27]铃木節也,藤原義已,西海建一.溶銑输送管理ッステム[J],神户制钢技报,1995,30(2)：48-50.
[28]田村昌弘,稲葉佑三,古贺康彦,有阑德美,何合登,入谷英樹.溶铣物流システムの改善[J],神户制钢技报,1996,46(2)：15-18.
[29]Lubbecke, M E. Engine scheduling by column generation [D], Braunschweig University of Technology,2001.
[30]Lubbecke M E, Zimmermann U T. Engine routing and scheduling at industrial in-plant railroads [J], Transportation Science,2003,37 (2):183-197.
[31]Imai T, Nakagawa Y, Kumamoto K, Nohira M, Yamaguchi T. Multistage job shop scheduling with complex material handling system [A], Proceedings of Production Scheduling Symposium [C],1996,151-156. (in Japanese)
[32]Imai T, Asada K, Nakagawa Y, Kumamoto K, Nohira M. A scheduling system for the steel-making process using a general approach [J], Transactions of the Institute of Systems, Control and Information Engineers,1997,10(4):204-210. (in Japanese)
[33]Tamura T, Tanizaki T, Imai T, Kumamoto K. Development of a scheduling algorithm at steel making plant [A], Proceedings of Scheduling Symposium [C],2002,140-145. (in Japanese)
[34]Honda N, Mouri S, Ishii H. Steel making process scheduling with crane interference [A], Proceedings of Scheduling Symposium [C],2002,108-113. (in Japanese)
[35]Tanizaki T, Tamura T, Sakai H, Takahashi Y, Imai T. A heuristic scheduling algorithm for steel making process with crane handling [J], Journal of the Operations Research Society of Japan,2006,49(3):188-201.
[36]Dantzig G B, Wolfe P. Decomposition principle for linear programs [J], Operations Research,1960,8:101-111.
[37]Gilmore P, Gomory R. A linear programming approach to the cutting stock problem [J], Operations Research,1961,9:849-859.
[38]Desrosiers J, Soumis F, Desrochers M. Routing with time windows by column generation [J], Networks,1984,14:545-565.
[39]Barnhart C, Johnson E L, Nemhauser G L, Savelsbergh M W P, Vance P H. Branch-and-Price:column generation for solving huge integer programs [J], Operations Research,1998,46(3):316-329.
[40]Vanderbeck F. Decomposition and column generation for integer programs [D], Universite catholique de Louvain,1994.
[41]Desaulniers G, Desrosiers J, Solomon M M. Accelerating strategies in column generation methods for vehicle routing and crew scheduling problems [J], Les Cahiers du GERAD G-99-36, Ecole des Hautes Etudes Commerciales, Montreal, Canada,1999.
[42]姚恩瑜,何勇,陈仕平.数学规划与组合优化[M],浙江：浙江大学出版社,2001.
[43]运筹学教材编写组.运筹学[M],北京：清华大学出版社,1991.
[44]Vanderbeck F. On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a Branch-and-Price algorithm [J], Operations Research,2000, 48(1):111-128.
[45]Nemhauser G L, Wolsey L A. Integer and Combinatorial Optimization [M], Chichester, England:Wiley,1988.
[46]Manne A S. Programming of economic lot sizes [J], Management Science,1958,4(2): 115-135.
[47]Sol M, Savelsbergh M W P. A Branch-and-Price algorithm for the pickup and delivery problem with time windows [J], Report COC-94-06, Georgia Institute of Technology, Atlanta, Georgia,1994.
[48]Lavoie S, Minoux M, Odier E. A new approach for crew pairing problems by column generation with an application to air transportation [J], European Journal of Operational Research,1988,35(1):45-58.
[49]Anbil R, Tanga R, Johnson E L. A global approach to crew-pairing optimization [J], IBM Systems Journal,1993,31:71-78.
[50]Skitt R A, Levary R R. Vehicle routing via column generation [J], European Journal of Operational Research,1985,21(1):65-76.
[51]Savelsbergh M W P. A branch and price algorithm for the generalized assignment problem [J], Operations Research,1996,45(6):831-841.
[52]Vance P H, Barnhart C, Johnson E L, Nemhauser G L. Solving binary cutting stock problems by column generation and branch-and-bound [J], Report COC-92-09, Computational Optimization Center, Georgia Institute of Technology, Atlanta, Georgia, 1992.
[53]Ryan D M, Foster B A. An integer programming approach to scheduling [J]. In:Wren A (ed.). Computer Scheduling of Public Transport:Urban Passenger Vehicle and Crew Scheduling. Amsterdam:North-Holland Publishing,1981,269-280.
[54]Gilmore P, Gomory R. A linear programming approach to the cutting stock problem-Part II [J], Operations Research,1963,11:863-888.
[55]Valerio de Carvalho J M, Guimaraes Rodrigues A J. An LP based approach to a two-phase cutting stock problem [J], European Journal of Operational Research,1995, 84:580-589.
[56]Vance P H. Branch-and-Price algorithms for the one-dimensional cutting stock problem [J], Computational Optimization and Applications,1998,9:211-228.
[57]Kantorovich L. Mathematical methods of organising and planning production (translated from a report in Russian, dated 1939) [J], Management Science,1960,6: 366-422.
[58]Chauhan S S, Alain M, Sophie D A. Roll assortment optimization in a paper mill:An integer programming approach [J], Computers & Operations Research,2008,35: 614-627.
[59]Dumas Y, Desrosiers J, Soumis F. The pick-up and delivery problem with time windows [J], European Journal of Operational Research,1991,54:7-22.
[60]Desrochers M, Desrosiers J, Solomon M M. A new optimization algorithm for the vehicle routing problem with time windows [J], Operations Research,1992,40: 342-354.
[61]Desaulniers G, Lavigne J, Soumis F. Multi-depot vehicle scheduling problems with time windows and waiting costs [J], European Journal of Operational Research,1998, 111:479-494.
[62]Palmgren M, Ronnqvist M, Varbrand P. A near-exact method for solving the log-truck scheduling problem [J], International Transactions in Operational Research,2004,11: 447-464.
[63]Xu H, Chen Z L, Rajagopal S, Arunapuram S. Solving a practical pickup and delivery problem [J], Transportation Science,2003,37(3):347-364.
[64]Chen Z L, Xu H. Dynamic column generation for dynamic vehicle routing with time windows [J], Transportation Science,2006,40(1):74-88.
[65]Christiansen C H, Lysgaard J. A Branch-and-Price algorithm for the capacitated vehicle routing problem with stochastic demands [J], Operations Research Letters,2007,35(6): 773-781.
[66]Chen Z L, Powell W B. Solving parallel machine scheduling problems by column generation [J], INFORMS Journal on Computing,1999,11:78-94.
[67]Van den Akker J M, Hoogeveen J A, Van de Velde S L. Parallel machine scheduling by column generation [J], Operations Research,1999,47:862-872.
[68]Chen Z L, Powell W B. A column generation based decomposition algorithm for a parallel machine just-ih-time scheduling problem [J], European Journal of Operational Research,1999,116:220-232.
[69]Lee C Y, Chen Z L. Scheduling jobs and maintenance activities on parallel machines [J], Naval Research Logistics,2000,47:145-165.
[70]Chen Z L, Lee C Y. Parallel machine scheduling with a common due window [J], European Journal of Operational Research,2002,136:512-527.
[71]Chen Z L, Powell W B. Exact algorithms for scheduling multiple families of jobs on parallel machines [J], Naval Research Logistics,2003,50:823-840.
[72]Bard J F, Rojanasoonthon S. A Branch-and-Price algorithm for parallel machine scheduling with time windows and job priorities [J], Naval Research Logistics,2006,53: 24-44.
[73]Pereira Lopes M J, Valerio de Carvalho J M. A Branch-and-Price algorithm for scheduling parallel machines with sequence dependent setup times [J], European Journal of Operational Research,2007,176:1508-1527.
[74]Oguz O. Generalized column generation for linear programming [J], Management Science,2002,48(3):444-452.
[75]Jaumard B, Marcotte O, Meyer C, Vovor T. Comparison of column generation models for channel assignment in cellular networks [J], Discrete Applied Mathematics,2001, 112:217-240.
[76]Hemazro T D, Jaumard B, Marcotte O. A column generation and branch-and-cut algorithm for the channel assignment problem [J]. Computers & Operations Research, 2008,35(4):204-1226.
[77]Bard J F, Purnomo H W. A column generation-based approach to solve the preference scheduling problem for nurses with downgrading [J], Socio-Economic Planning Sciences,2005,39(3):193-213.
[78]Bard J F, Purnomo H W. Preference scheduling for nurses using column generation [J], European Journal of Operational Research,2005,164(2):510-534.
[79]Valerio de Carvalho J M. Exact solution of bin-packing problems using column generation and branch-and-bound [J], Annals of Operational Research,1999,86: 629-659.
[80]Valerio de Carvalho J M. LP models for bin-packing and cutting stock problems [J], European Journal of Operational Research,2002,141(2):253-273.
[81]Degraeve Z, Jans R. A new Dantzig-Wolfe reformulation and Branch-and-Price algorithm for the capacitated lot-sizing problem with setup times [J], Operations Research,2007,55(5):909-920.
[82]Van den Akker J M, Hurkens C A J, Savelsbergh M W P. Time-indexed formulations for single-machine scheduling problems:column generation [J], INFORMS Journal on Computing,2000,12:111-124.
[83]Valerio de Carvalho J M. Using extra dual cuts to accelerate column generation [J], INFORMS Journal on Computing,2005,17(2):175-182.
[84]Alves C, Valerio de Carvalho J M. Accelerating column generation for variable sized bin-packing problems [J], European Journal of Operational Research,2007,183: 1333-1352.
[85]Degraeve Z, Peeters M. Optimal integer solutions to industrial cutting-stock problems: Part 2, benchmark results [J], INFORMS Journal on Computing,2003,15:58-81.
[86]Oukil A, Ben Amor H, Desrosiers J, Gueddari H E. Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems [J], Computers& Operations Research,2007,34:817-834.
[87]Desaulniers G. Managing large fixed costs in vehicle routing and crew scheduling problems solved by column generation [J], Computers & Operations Research,2007, 34(4):1221-1239.
[88]Desaulniers G, Desrosiers J, Dumas Y, Solomon M M, Soumis F. Daily aircraft routing and scheduling [J], Management Science,1997,841-855.
[89]Choi E, Tcha D W. A column generation approach to the heterogeneous fleet vehicle routing problem [J], Computers & Operations Research,2007,34(7):2080-2095.
[90]Chabrier A. Vehicle Routing Problem with elementary shortest path based column generation [J], Computers & Operations Research,2006,33:2972-2990.
[91]Feillet D, Dejax P, Gendreau M, Gueguen C. An exact algorithm for the elementary shortest path problem with resource constraints:application to some vehicle routing problems [J], Networks,2004,43(3):216-229.
[92]Ceselli A, Righini G. A Branch-and-Price Algorithm for the multilevel generalized assignment problem [J], Operations Research,2006,54(6):1172-1184.
[93]Fei H, Chu C, Meskens N, Artiba A. Solving surgical cases assignment problem by a Branch-and-Price approach [J], International Journal Production Economics, In Press.
[94]Klose A, Drexl A. Lower bounds for the capacitated facility location problem based on column generation [J], Management Science,2005,51:1689-1705.
[95]Klose A, Gortz S. A Branch-and-Price algorithm for the capacitated facility location problem [J], European Journal of Operational Research,2007,179:1109-1125.
[96]Van den Akker J M, Hoogeveen J A, Van de Velde S L. Combining column generation and Lagrangean relaxation to solve a single-machine common due date problem [J], INFORMS Journal on Computing,2002,14:37-51.
[97]Jans R, Degraeve Z. An industrial extension of the discrete lot sizing and scheduling problem [J],IIE Transactions,2004,36:47-58.
[98]Huisman D, Jans R, Peeters M, Wagelmans A P M. Combining column generation and Lagrangian relaxation, Column Generation [M], Springer,2005,247-270.
[99]Brucker P, Knust S. A linear programming and constraint propagation-based lower bound for the RCPSP [J], European Journal of Operational Research,2000,127(2): 355-362.
[100]Fahle T, Junker U, Karisch S E, Kohl N, Sellmann M, Vaaben B. Constraint programming based column generation for crew assignment [J], Journal of Heuristics, 2002,8:59-81.
[101]Gronkvist M. Accelerating column generation for aircraft scheduling using constraint propagation [J], Computers & Operations Research,2006,33:2918-2934.
[102]Sadykov R, Wolsey L A. Integer programming and constraint programming in solving a multimachine assignment scheduling problem with deadlines and release dates [J], INFORMS Journal on Computing,2006,18(2):209-217.
[103]Rousseau L M, Gendreau M, Pesant G. Solving VRPTWs with constraint programming based column generation [J], Annals of Operations Research,2004,130:199-216.
[104]Zak E J. Row and column generation technique for a multistage cutting stock problem [J], Computers & Operations Research,2002,29:1143-1156.
[105]Avella P, Auria B D, Salerno S. A LP-based heuristic for a time-constrained routing problem [J], European Journal of Operational Research,2006,173:120-124.
[106]Avella P, Sassano A, Vasilev I. Computational study of large-scale p-median problems [J], Mathematical Programming Serie A,2007,109:89-114.
[107]戴韬,霍佳震.钢铁企业铁水运输调度自动指令系统的实现[J],上海管理科学,2005,6：32-34.
[108]刘峰.宝钢铁水运输组织及运输能力分析[J],宝钢技术,2001,5：30-33.
[109]赵沛,成国光,沈甦.炉外精炼及铁水预处理实用技术手册[M],北京：冶金工业出版社,2004.
[110]王文瑞.宝钢铁水监控及管理系统(上)[J],冶金自动化,2001,25(4)：20-23.
[111]王文瑞.宝钢铁水监控及管理系统(下)[J],冶金自动化,2001,25(5)：16-19.
[112]董金刚.宝钢—炼钢精炼设备功能比较分析[J],炼钢,2006,22(5)：1-3.
[113]Erlenkotter D. A dual-based procedure for uncapacitated facility location [J], Operations Research,1978,26:992-1009.
[114]Sun M H. Solving the uncapacitated facility location problem using tabu search [J], Computers & Operations Research,2006,33(9):2563-2589.
[115]Cornuejols G, Nemhauser G L, Wolsey L A. The uncapacitated facility location problem, Discrete location theory [M], NewYork:Wiley,1990,119-171.
[116]Lorena L A N, Senne E L F. A column generation approach to capacitated p-median problems [J], Computers & Operations Research,2004,31(6):863-876.
[117]Senne E L F, Lorena L A N, Pereira M A. A Branch-and-Price approach to p-median location problems [J], Computers & Operations Research,2005,32:1655-1664.
[118]Fisher M L. Lagrangian relaxation method for solving integer programming [J], Management Science,1981,27:221-218.
[119]Zhao X, Luh P B, Wang J. Surrogate gradient algorithm for Lagrangian relaxation [J], Journal of Optimization Theory and Application,1999,100:699-712.
[120]Tang L X, Xuan H. Lagrangian relaxation algorithms for real-time hybrid flowshop scheduling with finite intermediate buffers [J], Journal of the Operational Research Society,2006,57(3):316-324.
[121]轩华.拉格朗日松弛的改进及在生产调度中的应用[D],东北大学,2006.
[122]Park H, Hong Y S, Chang S T. An effcient scheduling algorithm for the hot coil making in the steel mini-mill [J], Production Planning & Control,2002,13(3):298-306.
[123]Araque J R, Kudva G, Morin T L, Pekny J F. A branch and cut algorithm for the vehicle routing problem [J], Annals of Operations Research,1994,50:37-59.
[124]Letchford A N, Eglese R W, Lysgaard J. Multistars, partial multistars and the capacitated vehicle routing problem [J], Mathematical Programming,2002,94:21-40.
[125]Dror M. Note on the complexity of the shortest path models for column generation in VRPTW [J], Operations Research,1994,42:977-978.
[126]Feillet D, Dejax P, Gendreau M. Traveling salesman problems with profits [J], Transportation Science,2005,39(2):188-205.
[127]Paessens H. The savings algorithm for the vehicle routing problem [J], European Journal of Operational Research,1988,34(3):336-344.
[128]Bruno J, Coffman E G, Sethi R. Scheduling independent tasks to reduce mean finishing time [J], Communications of the ACM,1974,17:382-387.
[129]Tang L X, Wang G S, Liu J Y. A Branch-and-Price algorithm to solve the molten iron allocation problem in iron and steel industry [J], Computers & Operations Research 2007,34:3001-3015.
[130]Lenstra J K, Rinnooy Kan A H G., Brucker P. Complexity of machine scheduling problems [J], Annals of Discrete Mathematics,1977,1:343-362.
[131]Christofides N, Mingozzi A, Toth P. State-space relaxation procedures for the computation of bounds to routing problems [J], Networks,1981,11:145-164.
[132]Savelsbergh M W P, Sol M. The general pickup and delivery problem [J], Transportation Science,1995,29(1):17-29.
[133]Lu Q, Dessouky M M. A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows [J], European Journal of Operational Research,2006,175(2):672-687.
[134]Holland J. Adaption in natural and artificial systems [M], Ann Arbor:The University of Michigan Press,1975.
[135]Glover F. Tabu search:part Ⅰ. ORSA [J], Journal on Computing,1989,1:190-206.
[136]Glover F. Tabu search:part Ⅱ. ORSA [J], Journal on Computing,1990,2:4-32.
[137]Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing [J], Science,1983,220:671-680.
[138]Hopfield J. Neural networks and physical systems with emergent collective computational abilities [A], Proceedings of National Academy of Sciences [C],1982, 79:2254-2558.
[139]李韶华.钢铁原料输入物流建模及优化算法研究[D],东北大学,2006.
[140]Cowling P. A flexible decision support system for steel hot rolling mill scheduling [J], Computers & Industrial Engineering,2003,45:307-321.
[141]Lopez L, Carter M W, Gendreau M. The hot strip mill production scheduling problem:a tabu search algorithm [J], European Journal of Operational Research,1998,106: 317-335.
[142]Stauffer L, Liebling T M. Rolling horizon scheduling in a rolling mill [J], Annals of Operations Research,1997,69:323-349.
[143]Cowling P. Optimization in steel hot rolling, Optimization in industry [M], Chichester, England:Wiley,1995.
[144]den. Besten M, Stutzle T, Dorigo M. Design of iterated local search algorithms-An example application to the single machine total weighted tardiness problem [A], Applications of Evolutionary Computing Proceedings [C], Lecture Notes in Computer Science,2001,2037:441-451.
[145]Paquete L, Stutzle T. An experimental investigation of iterated local search for coloring graphs [A], Applications of Evolutionary Computing Proceedings [C], Lecture Notes in Computer Science,2002,2279:122-131.