运输能力有限混合流水车间调度的改进拉格朗日松弛算法

Improved LR algorithm for hybrid flowshop scheduling with transportation consideration

为改善在制品库存和能耗问题,研究了从钢铁实际生产环境提炼出的运输能力有限的动态混合流水车间调度问题。将运输机视为虚拟机器,可将原问题转换成与其等价的不考虑运输能力但在偶数阶段机器有不可用时间段的动态混合流水车间调度问题,其中机器不可用时间段取决于其运送的工件。对转换后的问题建立数学模型,提出基于阶段分解的拉格朗日松弛算法进行求解,该算法将优先级约束松弛到目标函数中,将拉格朗日松弛问题分解为多个阶段级子问题,进而设计了动态规划求解这些带任意权重和机器不可用时间段的并行同构机调度子问题。对不同问题规模的测试结果表明,所提算法能够在较短的运行时间内获得满意的近优解。

To improve the inventory and energy consumption of work in process,the dynamic hybrid flowshop scheduling with transportation consideration in practical manufacturing circumstances of steel enterprises was studied.Transporters were viewed as virtual machines to transform the original problem into dynamic Hybrid FlowShop（HFS）scheduling problem of one without transportation but with job-dependent unavailable time windows of machines at even stages,in which the unavailable time of machines depended on delivery workpieces.The mathematical model for transformed problem was constructed,and Lagrangian Relaxation（LR）algorithm based on stage-decomposition was solved.In this algorithm,the precedence constraints were relaxed into objective function,and LR problem was decomposed in multiple stage-level sub-problems.Thus a dynamic programming algorithm was designed to solve these parallel identical machine scheduling sub-problems with any job weight and unavailable time windows of machines.Numerical results on problems with different scale showed that the designed LR algorithm could obtain acceptable near-optimal solutions within a shorter computational time.