Efficient heuristic for solving non-permutation flow-shop scheduling problems with maximal and minimal time lags

•Clarified the conditions for feasibility and dominance for non-PFSP.•Developed 5 efficient neighbourhood searching heuristics.•Proposed the best performed PFSP algorithm and non-PFSP heuristic.

Flow-shop scheduling problem is an attractive subject in the scheduling field, which has attracted the attention of many researchers in the past five decades. However, few studies focused on non-permutation flow-shop problems with time lag consideration. In the present work, the non-permutation flow-shop scheduling problem with time lags has been studied to minimize the makespan as a performance measure. First, we obtain a near-optimal permutation solution using the permutation flow-shop problem (PFSP) heuristic. Then, an effective iterated greedy heuristic, which can identify high-quality non-permutation solutions, is presented. Using the neighbourhood non-PFSP searching heuristic, we searched for non-PFSP schedules using the proposed heuristic algorithms in the second stage. Finally, the computational results were used to evaluate the performance and effectiveness of the proposed heuristic. The proposed heuristics were able to find near optimal non-PFSP solutions with very short computational time. Thus, the proposed algorithms is efficient and can be used in industrial applications. Moreover, the proposed heuristic algorithms are very simple to implement, which is attractive for industrial applications.

Graphical abstractInfeasibility of non-permutation schedules in m-machine problem.Download high-res image (60KB)Download full-size image