Iterative algorithms for no-wait flowshop problems with sequence-dependent setup times

摘要

In this paper, the m-machine no-wait flowshop scheduling problem with sequence-dependent setup times is considered to minimize the makespan. According to the problem characteristics, the increment properties of some fundamental operators of algorithms are analyzed. Two increment-based methods FSP (fittest swap points) and FMP (fittest move points) are constructed for fast evaluation on all algorithms. Four iterative algorithms on the basis of job insert, move and swap operators are proposed for the considered problem. In IMS (heuristic with insert, move and swap operators) algorithm, the current solution is constructed step by step by inserting a job at a time and is improved by conducting jobs move within a certain range. FR-IMS (full-range IMS) algorithm is a full-range IMS algorithm. Both IA (iterative algorithm) and IALS (iterative algorithm with local search) algorithms consist of two phases: solution initialization according to a certain rule and solution enhancement by iteratively conducting perturbation and move-based techniques. The main difference between IA and IALS lies in the fact that, instead of using FMP method in the enhancement phase like IA a local search process which is based on moves under a first-improvement type of pivoting rule as well as a restart mechanism is adopted in IALS. Experimental results show that the proposed algorithms outperform the best existing approaches, among which IALS is the most effective one.