考虑多约束的混合流水车间MOJ调度

Scheduling multiple orders per job with various constraints for hybrid flow shop

考虑晶圆加工过程中的多品种和与次序相关的换模时间约束,以系统总完工时间最小为优化目标,建立混合流水车间MOJ调度模型.在此基础上,提出了基于作业-产品-机器三层析取网络流的列生成算法.为进一步改善列生成算法存在的尾效应,将基于次梯度优化的拉格朗日松弛算法嵌入列生成算法框架中,构建了采用双重迭代的改进型列生成(MCG)算法.最后,通过理论分析和仿真实验表明了MCG算法是有效、可行的.

With a comprehensive consideration of multiple product types and sequence-dependent setup times constraints in which processes of wafer fabrications, a scheduling model of multiple orders per job（MOJ） in a hybrid flow shop with an objective function of minimizing total completion time of the system is developed. On the basis of the descriptions, a column generation algorithm based on the job-product-machine three level disjunctive network flow is proposed. Furthermore, to improve the degradation effects of column generation algorithm, Lagrangian relaxation with sub-gradient optimization is combined into the frame of column generation algorithm, and then a modified column generation（MCG） algorithm adopting dual iteration is proposed. Finally, theory analysis and simulation experiments show that the developed MCG algorithm is valid and feasible.