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

摘要

炼钢-连铸是现代钢铁企业生产流程的核心工序.本文将炼钢-连铸调度问题抽象为具有复杂约束的混合流水车间调度问题.以炉次总驻留时间最短和浇次准时开浇为优化目标,以炉次连浇为等式约束,建立了该问题的0-1型混合整数非线性模型.通过松弛资源析取约束,解除连续变量和整数变量之间的耦合关系,将松弛问题分解成两个简单的子问题.提出一种拉格朗日松弛水平算法,采用对偶松弛函数下降水平控制策略,以保证算法收敛于对偶松弛问题最优解.不同的测试算例表明:与传统拉格朗日松弛算法相比,所提算法可得到更好的下界和对偶间隙,并且求解时间较短.尤其问题规模越大,其优越性更加明显.