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

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