Solving the blocking flow shop scheduling problem with makespan using a modified fruit fly optimisation algorithm
针对工业系统中常见的阻塞流水车间调度问题，提出一种改进果蝇优化算法，通过初始化、邻域搜索和局部搜索等策略最小化最大完工时间，实验证明算法高效且找到了新的最优解。
The flow shop scheduling problem with blocking has important applications in a variety of industrial systems but is under-represented in the research literature. In this paper, a modified fruit fly optimisation (MFFO) algorithm is proposed to solve the above scheduling problem for makespan minimisation. The MFFO algorithm mainly contains three key operators. One is related to the initialisation scheme in which a problem-specific heuristic is adopted to generate an initial fruit fly swarm location with high quality. The second is concerned with the smell-based search in which a neighbourhood strategy is designed to generate a new location. To further enhance the exploitation of the proposed algorithm considered, a speed-up insert-neighbourhood-based local search is applied with a probability. Finally, the last is for the vision-based search in which an update criterion is proposed to induce the fruit fly into a better searching space. The simulation experimental results demonstrated the efficiency of the proposed algorithm, in spite of its simple structure, in comparison with a state-of-the-art algorithm. Moreover, new best solutions for Taillard’s instances are reported for this problem, which can be used as a basis of comparison in future studies.