Abstract: To effectively solve serial batch scheduling,an improved Lagrangian Relaxation algorithm mixed with Interleaved Subgradient Optimization(LR&ISO)was presented for the Flexible Flow Shop Problem(FFSP)with batch and discrete processors.The objective was to minimize total weighted completion time.This problem arises from the integrated production process of steelmaking-continuous casting-hot rolling in iron and steel industry.In order to speed up resolution process and expand resolution scale,the ISO was introduced into LR where a batch-level subproblem was optimized at each iteration and the other solutions were kept the same as the ones at the previous iteration to obtain a reasonable multiplier updating direction.It leaded to a much shorter computational time of each iteration.Numerical experiments was carried out to compare the proposed algorithm with LR based on batch decoupling and subgradient optimization.The results on practical production data and randomly generated larger-sized instances showed that the proposed algorithm can obtain the competitive performance,and its superiority on solution quality and convergence speed was more obvious with the increasing of problem size.

Key words: interleaved subgradient optimization, Lagrangian relaxation algorithm, flexible flow shop problem, batch and discrete processors, total weighted completion time

摘要： 为有效解决串行批调度问题,提出了一个混合异步次梯度优化的拉格朗日松弛算法,来求解带批和离散机的柔性流水车间问题(FFSP),目标是最小化总加权完成时间。该问题来源于钢铁业的炼钢—连铸—热轧一体化生产过程,为了加快算法的求解速度,扩大求解规模,在拉格朗日松弛优化算法中引入异步次梯度优化,每次迭代仅最优求解一个批级子问题,而其他子问题的解仍维持为前一次迭代的值,以此获取一个合理的乘子更新方向,大大缩短了每次迭代所消耗的运行时间。通过与基于批解耦和次梯度法的拉格朗日松弛算法的实验对比,说明了无论是实际生产数据还是随机产生的大规模数据,所提出的改进拉格朗日松弛算法都能获得具有竞争性的结果,对于较大规模问题,它在解的质量和收敛速度方面的优势更加明显。

关键词: 异步次梯度优化, 拉格朗日松弛算法, 柔性流水车间问题, 批处理机和离散机, 总加权完成时间