A multi-start tabu search method for a single-machine scheduling problem with periodic maintenance and sequence-dependent set-up times

作者：Pacheco Joaquin; Angel Bello Francisco; Alvarez Ada^*

来源：Journal of Scheduling, 2013, 16(6): 661-673.

DOI：10.1007/s10951-012-0280-2

• Scheduling
• Maintenance
• Sequence-dependent setup
• Tabu Search

In this paper we study a problem of sequencing jobs in a machine with programmed preventive maintenance and sequence-dependent set-up times. The problem combines two NP-hard problems, so we propose a heuristic method for solving it, which hybridizes multi-start strategies with Tabu Search. We compare our method with the only published metaheuristic algorithm for this problem on a set of 420 instances. The comparison favors the method developed in this work, showing that is able to find high quality solutions in very short computational times.

• 出版日期2013-12