求解炼钢-连铸生产调度问题的拉格朗日算法  

Lagragian algorithm for steelmaking-continuous casting production scheduling

作　　者：毛坤[1] 潘全科[1] 庞新富[1] 

机构地区：[1]东北大学流程工业综合自动化国家重点实验室,辽宁沈阳110819

出　　处：《系统工程学报》2014年第2期233-245,共13页Journal of Systems Engineering

基　　金：高等学科创新与引智计划资助项目(B08015);教育部项目基本科研业务费资助项目(N110208001);国家自然科学基金资助项目(61174187;71021061;60974091;61104174);中央高校基本科研业务费资助项目(N100508001);东北大学科研启动经费资助项目(29321006)

摘　　要：炼钢-连铸是现代钢铁企业生产流程的核心工序.本文将炼钢-连铸调度问题抽象为具有复杂约束的混合流水车间调度问题.以炉次总驻留时间最短和浇次准时开浇为优化目标,以炉次连浇为等式约束,建立了该问题的0-1型混合整数非线性模型.通过松弛资源析取约束,解除连续变量和整数变量之间的耦合关系,将松弛问题分解成两个简单的子问题.提出一种拉格朗日松弛水平算法,采用对偶松弛函数下降水平控制策略,以保证算法收敛于对偶松弛问题最优解.不同的测试算例表明:与传统拉格朗日松弛算法相比,所提算法可得到更好的下界和对偶间隙,并且求解时间较短.尤其问题规模越大,其优越性更加明显.Steelmaking-continuous casting is the core production process in modem steel production. It is abstracted as a hybrid flowshop with complex constraints in this paper. A 0-1 mixed-integer nonlinear pro- gramming model, which treats the no dead time within the same cast at the last stage as an equality constraint and uses the total sojourn times of all jobs and the penalty of the earliness and tardiness of all casts as its minimum objective, is established. The disjunctive constraints of this model are relaxed in order to decouple the coupling relationship between continuous variables and integer variables. So the relaxed problem can be decomposed into two tractable sub-problems. A Lagrangian relaxation（LR） level algorithm is proposed for this scheduling problem. The algorithm applies the decreasing level control approach of the dual relaxation function evaluation in order to guarantee convergence. A computational comparison is provided for the LR level algorithm and traditional LR algorithm. Numerical results show that the LR level algorithm method can provide better lower bound, better dual gap and faster convergence for medium sized problems, especially for larger sized problems.

关 键 词：炼钢-连铸 生产调度 拉格朗日松弛水平算法 线性规划 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]