Abstract: Based on the integrated production operation of steel-making, continuous casting and hot rolling in steel industry, a new three-stage hybrid flowshop scheduling problem with serial batching machines was presented which the second stage contained several serial batching machines and other stages contains several discrete machines. The batch processing time was equal to the sum of processing times of all jobs in this batch at stage two. Moreover, the practical production features such as setup time were considered.The minimize total weighted completion time was used as objective function to built mathematical model for proposed problem. Based on workpiece decomposition strategy, Lagrangian relaxation algorithm was constructed. Machine ability constraint and batch processing constraint were relax into objective function by introducting Lagrangian multiplier, thus the formed relaxation problem was decomposed into several workpiece sub-problems, which were solved by dynamic programming algorithm. Heuristic algorithm was designed to convert solution of relaxation problem into feasible solution of primary problem. The simulation results showed that the designed algorithm could obtain better solution quality within acceptable computation time.

Key words: hybrid flowshop, scheduling, serial batching machine, machine setup time, Lagrangian relaxation

摘要： 基于钢铁行业炼钢-连铸-热轧一体化生产作业，提炼出新的三阶段混合流水车间调度问题。其中第二阶段有多台串行批处理机而其他阶段为离散机，批加工时间等于同一批内所有工件在第二阶段的加工时间之和，且考虑了设备需要调整时间等实际生产特征。以最小化总加权完成时间为目标函数，对该问题建立数学模型，提出基于工件分解策略的拉格朗日松弛算法，引入拉格朗日乘子将机器能力约束和批加工约束松弛到目标函数中，进而将形成的松弛问题分解为较易求解的多个工件级子问题，利用动态规划算法求解子问题，设计启发式算法将松弛问题的解转换为原问题的可行解。仿真实验表明，所设计的算法能够在可接受的运行时间内得到较好的近优解。

关键词: 混合流水车间, 调度, 串行批处理机, 机器调整时间, 拉格朗日松弛