Abstract: Flexible flowshop scheduling problem (FFSP) is a common combinational optimization problem in the field of production scheduling, which is widely applied in industries such as chemical, steel and automobile manufacturing. Classical FFSP often assumes that there is an infinite storage capacity for buffers between two adjacent production stages. However, due to the limitations of storage equipment and physical space, the buffer capacity is limited. In addition, some production technologies require continuous processing without interruptions in certain stages. Due to different parallel machine structures and machine wear, the unrelated parallel machine structure is closer to the actual production situation. Therefore, with the objective of minimizing the total weighted completion time, this paper investigates the dynamic flexible flowshop scheduling problem with mixed storage constraints (DFFSP-MSC) including zero wait and limited buffer under the unrelated parallel machine environment.
Each buffer is viewed as a stage with the function of buffering and the above DFFSP-MSC can be converted into an equivalent dynamic FFSP with mixed storage constraints including zero wait and blocking. Considering the dynamic arrival time of jobs and the transportation time between adjacent stages, an integer programming model is established for the transformed problem and an improved discrete artificial bee colony (IDABC)algorithm is presented integrating genetic algorithm (GA), neighborhood search (NS) and variable neighborhood descent (VND) algorithm. The algorithm adopts two-dimensional matrix for encoding food sources, and the machine idle rule and job right-shift strategy for decoding. The initial populations are generated by NEH heuristic algorithm and opposition-based learning strategy. Self-adaptive parameter adjustment strategy is designed for the employed bee stage to improve the genetic algorithm where two crossover operators including single-point row crossover and single-point column crossover, and two mutation operators including single-point row mutation and reverse-order inversion mutation are used to complete the update of the food sources. In the onlooker bee stage, three neighborhood structures of first-tail row crossover, single-point row insertion, and fragment row insertion are designed, and probability selection-based NS is applied to enhance the algorithm search capability. In the scout bee stage, the VND algorithm is used to search nearly the best solution and replace the worst solution.
To verify the effectiveness of the IDABC algorithm, simulation experiments are conducted by comparing it with artificial bee colony (ABC) algorithm, classical GA, improved GA combined with NEH heuristic (NEH-IGA), hybrid heuristic algorithm based on GA and tabu search (HH-GA&TS). The testing results of different scale instances are described below. For the small & medium-scale problems, within an average CPU time of 196.52s, the average objective value obtained by the IDABC algorithm is improved by 26.88%, 22.08%, 14.85% and 5.87% respectively, compared with the ABC algorithm, GA, NEH-IGA and HH-GA&TS. For the large-scale problems, within an average CPU time of 351.97s, the average objective value is improved by 21.29%, 16.57%, 11.68%, and 8.03% respectively, compared with the above four compared algorithms. It can be seen from convergence experiments that although the IDABC algorithm converges slightly more slowly than HH-GA&TS in the early iterations, it outperforms the other four algorithms with an increase of iteration number and has a faster convergence speed especially when the problem scale increases. The IDABC algorithm obtains better near-optimal solutions within the same iteration number. As a whole, the proposed IDABC algorithm has better solution performance.
In this paper, an IDABC algorithm is developed to solve dynamic FFSP with two intermediate storage constraints mixing zero wait and finite buffer between stages. Future research will focus on dynamic FFSP with other mixed intermediate storage constraints and multi-objective DFFSP-MSC.

Key words: flexible flowshop scheduling, mixed storage constraints, unrelated machine, improved discrete artificial bee colony algorithm, total weighted completion time

摘要： 研究了生产阶段间零等待和有限缓冲两种中间存储约束共存的动态柔性流水车间调度问题,每阶段的并行机为不相关机。将有限缓冲阶段转换为阻塞阶段,考虑工件动态到达时间和相邻阶段间的运输时间,以最小化总加权完工时间为目标,构建了整数规划模型,提出了一种融合遗传算法、邻域搜索和变邻域下降算法的改进离散人工蜂群算法。采用基于机器号的二维矩阵进行编码,应用机器空闲原则和工件右移策略进行解码,通过NEH(Nawaz-Enscore-Ham)启发式算法和反向学习策略生成初始种群,雇佣蜂阶段设计自适应参数调整策略改进遗传算法,跟随蜂阶段利用基于概率选择的邻域搜索提高算法搜索能力,侦察蜂阶段利用变邻域下降算法在最好解附近进行搜索并替换最差解。仿真实验测试了不同规模的算例,实验结果表明所提出的改进离散人工蜂群算法具有较好的求解性能。

关键词: 柔性流水车间调度, 混合存储约束, 不相关机器, 改进离散人工蜂群算法, 总加权完工时间