Integrating non-preemptive open shops scheduling with sequence-dependent setup times using advanced metaheuristics

摘要

In this article, we consider non-preemptive open shops scheduling problem (OSSP) where setup times are sequence-dependent (SDST) on each machine to minimize makespan. The contributions of this article are threefold. Firstly, we incorporate a very practical assumption in our problem, SDST, which, according to Allahverdi et al. (2008) [Allahverdi, A., Ng, C. T., Cheung, T. C. E., & Kovalyov, Y. M. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187(3), 985–1032], no paper has ever attempted to integrate into OSSP. Secondly, we propose two new advanced metaheuristics: multi-neighborhood search simulated annealing and hybrid simulated annealing to tackle the problem at hand. Thirdly, for the first time, we adapt two well-known constructive heuristics: longest total processing time and longest total remaining processing from the literature so as to consider the case of SDSTs. We also apply genetic algorithm from the literature of OSSP to embrace the concepts of SDST. Since there is no standard SDST-OSSP benchmark, we make certain adaptations on the Taillard’s benchmark [Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278–285] to include setup times. An experimental design based on foregoing benchmark is conducted to evaluate the competitiveness and robustness of our proposed algorithm against some effective algorithms in the literature. The obtained results strongly support the high performance of our proposed algorithms with respect to other well-known heuristic and metaheuristic algorithms.