带运输考虑的多阶段动态可重入混合流水车间调度

可重入混合流水车间调度允许一个工件多次进入某些加工阶段,它广泛出现在许多工业制造过程中,如半导体制造、印刷电路板制造等.本文研究了带运输时间的多阶段动态可重入混合流水车间问题,目标是最小化总加权完成时间.针对该问题,建立了整数规划模型,进而基于工件解耦方式提出了两种改进的拉格朗日松弛(LR)算法.在这些算法中,设计了动态规划的改进策略以加速工件级子问题的求解,提出了异步次梯度法以得到有效的乘子更新方向.测试结果说明了所提出的两种改进算法在解的质量和运行时间方面均优于常规LR算法,两种算法都能在可接受的计算时间内得到较好的近优解.

Multi-stage dynamic reentrant hybrid flowshop scheduling with transportation consideration

Reentrant hybrid flowshop scheduling is widely found in many industries such as semiconductor manufacturingand printed circuit board fabrication, where a job visits some processing stages for several times. A multi-stage dynamicreentrant hybrid flowshop problem with transportation time is studied with the objective of minimizing total weighted completiontime. Then an integer programming model is formulated and two improved Lagrangian relaxation (LR) algorithmsare presented based on job decoupling. In these algorithms, dynamic programming is improved to speedup the resolutionof job-level subproblems and interleaved subgradient optimization is designed to obtain an effective multiplier updatingdirection. Testing results demonstrate that the two proposed LR algorithms outperform the traditional LR in terms of solutionquality and running time. Both of the two algorithms could get better near-optimal schedules within an acceptablecomputational time.