Effective constructive heuristics and discrete bee colony optimization for distributed flowshop with setup times

The distributed permutation flowshop scheduling problem (DPFSP) has been a hot issue in recent years. Due to the practical relevance of sequence-dependent setup time (SDST), we consider the DPFSP with SDST to minimize makespan. For the purpose, we propose three constructive heuristics and an effective discrete artificial bee colony (DABC) algorithm. All the heuristics are based on a greedy assignment rule and a local search of job blocks in each factory. In the local search, three different setup times are respectively considered for inserting a job block. In the DABC, to balance the local exploitation and the global exploration, we propose six composite neighborhood operators according to the problem characteristics. The first three are based on insertion and swap operators, and the second three have a close relationship with the critical factory. A problem-oriented local search method is developed to improve the best individual in the population. A comprehensive computational campaign against the closely related and state-of-the-art algorithms in the literature shows that both the proposed heuristics and DABC are very effective for solving the problem under consideration.

Automated summary

The study focuses on the DPFSP problem with SDST, proposing three constructive heuristics and a DABC algorithm. The heuristics are based on greedy rule and local search, while the DABC algorithm balances local and global exploration with six composite neighborhood operators. A problem-oriented local search method is introduced to improve the best individual in the population. The proposed methods are shown to be effective compared to existing algorithms in solving the problem.