An Improved Discrete Migrating Birds Optimization for Lot-Streaming Flow Shop Scheduling Problem with Blocking

摘要

Blocking lot-streaming flow shop (BLSFS) scheduling problems have considerable applications in various industrial systems, however, they have not yet been well studied. In this paper, an optimization model of BLSFS scheduling problems is formulated, and an improved migrating birds optimization (iMBO) algorithm is proposed to solve the above optimization problem with the objective of minimizing makespan. The proposed algorithm utilizes discrete job permutations to represent solutions, and applies multiple neighborhoods based on insert and swap operators to improve the leading solution. An estimation of distribution algorithm (EDA) is employed to obtain solutions for the rest migrating birds. A local search based on the insert neighborhood is embedded to improve the algorithm's local exploitation ability. iMBO is compared with the existing discrete invasive weed optimization, estimation of distribution algorithm and modified MBO algorithms based on the well-known lot-streaming flow shop benchmark. The computational results and comparison demonstrate the superiority of the proposed iMBO algorithm for the BLSFS scheduling problems with makespan criterion.