Iterated Local Search For The Sequence Dependent Setup Times Flow Shop Scheduling Problem

With the consideration of sequence dependent setup times on machines, a feature commonly derived from industrial settings, in the permutation flowshop scheduling problem (PFSP), the PFSP with sequence dependent setup times (SDST-PFSP) is more related to real production environments. It is so hard for traditional methods to solve this problem effectively that how to make an efficient scheduling solution has become an emergent and challenging problem for modern manufacturing industry. In this paper, some discussions are presented on this issue.As a simple but efficient and powerful metaheuristic, iterated local search (ILS) algorithm has been successfully applied for solving plenty of combinational optimization problems. It has made great progress for minimizing the total flowtime of PFSP. In this paper, the ILS is used for solving the SDST-PFSP, and the perturbation methods and local search procedure, which have significant impacts on the performance of ILS, are studied. The main research content is as follows:(1) Based on the previous work of researchers, the ILS_D is proposed and three different optimization objectives are considered:the maximum completion time (makespan), the total weighted tardiness (TWT) and the total flow time (TFT). Extensive comparisons are carried out among the ILS_D and the IG_RS, the current state-of-the-art method for the SDST-PFSP, on the benchmark that based on the instances of Taillard. The ILS_PR and IG_PR, which have achieved good performance in PFSP, are also adapted and compared. Experimental results indicate that the ILS_D is more powerful than the IG_RS for all objectives, and in most cases, significantly better than the ILS_PR and IG_PR.(2) Based on the elite pool strategy, three versions of ILS, the ILS_ADJ, ILS_INS and ILS_DC, are designed by using different perturbation methods, respectively. The methods include:the adjacent pairwise interchange (ADJ), the insertion moves (INS) and the destruction and construction heuristic (DC). The comparisons corresponding to the performance of the proposed ILS methods and the ILS_D indicate that the elite pool strategy is very robust and helpful for minimizing the Makespan and TWT objectives. With various requirements among the objectives, the above perturbation methods are more preferable for minimizing the TWT, Makespan and TFT, respectively.(3) Based on the enhanced ILS (EILS), in which two neighborhoods are employed, the EILS_INS and EILS_DC are modified by using different perturbation methods, respectively. Experimental results show that the proposed EILS methods using multi neighborhoods haven’t made significant improvements for minimizing the TWT and TFT objectives. With the complexity of per iteration increased from O (mn2) to O (mn3), much less iterations were performed, which contributes to the worse performance of the proposed EILS methods for minimizing the makespan. The results indicating that the multi neighborhoods local search is not very robust and a well designed local search method using multi neighborhoods for specific problems is needed for further improvement.