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

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