关键词: 系统工程, 异步次梯度法, 拉格朗日松弛算法, 多阶段混合流水车间问题, 总加权完成时间

Abstract: In order to reduce solution complexity and computation time, an improved Lagrangian relaxation algorithm combined with an interleaved subgradient method is presented to solve total weighted completion time problem of multi-stage hybrid flowshop. An integer programming model is firstly formulated for HFSP considering finite waiting time and job release time. An interleaved subgradient method is then introduced into Lagrangian relaxation which requires approximately solving Lagrangian relaxation problem to obtain a reasonable interleaved subgradient direction. The distance to optimal solutions can be decreased step by step along this searching direction. Computation experiments demonstrate the effectiveness of the presented algorithm. Compared with regular Lagrangian relaxation based on subgradient optimization, the testing results show that the developed method can get better schedule results with less time in aspect of solution quality and computation efficiency, especially for large-sized problems.

Key words: systems engineering, interleaved subgradient method, Lagrangian relaxation, multi-stage hybrid flowshop problem, total weighted completion time