带队列约束的RHFS列生成调度算法

为有效提升多重入车间的生产效率，考虑实际生产中队列约束，提出了基于列生成算法的可重入混合流水车间的调度方法.首先对两阶段生产调度问题进行描述，以最小化工件总完成时间为优化目标，建立数学规划模型.针对该调度模型提出列生成算法，设计带多重决策的动态规划方法来求解工件级子问题，为更快收敛，主问题求解中采用自适应加速策略.在使用分支定界将得到的解整数化的过程中，构造列池并设计局部变异.最后，对各种不同问题规模进行了数值实验，结果表明所提出的调度算法是有效可行的.

Column Generation Scheduling Algorithm of Reentrant Hybrid Flow Shops(RHFS) with Queue Constraints

To effectively enhance the production efficiency of multi-reentrant workshop， the queue constraint was considered where products were processed layer by layer， and then a scheduling method of reentrant hybrid flow shops(RHFS)was proposed based on column generation algorithm. Firstly， a two-stage scheduling model of RHFS was described and a mathematical programming model was built with an objective of minimizing the total completion time. A column generation algorithm was developed and dynamic programming with multiple decision-making was designed to solve each sub-problem. Further， the adaptive accelerating strategy was applied to effectively improve the algorithm convergence. In the process of generating integral solutions by using branch-and-bound method， column pool was built and neighborhood mutation method was emploied. Finally， numerical experiments in different problem scales were carried out to analyze the proposed algorithm. Results verify the validness and feasibility of the proposed algorithm.