A jigsaw puzzle inspired algorithm for solving large-scale no-wait flow shop scheduling problems

摘要

The no-wait flow shop scheduling problem (NWFSP), as a typical NP-hard problem, has important ramifications in the modern industry. In this paper, a jigsaw puzzle inspired heuristic (JPA) is proposed for solving NWFSP with the objective of minimizing makespan. The core idea behind JPA is to find the best match for each job until all the jobs are scheduled in the set of process. In JPA, a waiting time matrix is constructed to measure the gap between two jobs. Then, a matching matrix based on the waiting time matrix is obtained. Finally, the optimal scheduling sequence is built by using the matching matrix. Experimental results on large-scale benchmark instances show that JPA is superior to the state-of-the-art heuristics.