This paper introduces a tabu search heuristic for a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The problem consists in scheduling a set of dependent jobs, where the transition between two jobs comprises an unrestricted setup that can be performed at any time, and a restricted setup that must be performed outside of a given time interval which repeats daily in the same position. The setup time between two jobs is thus a function of the completion time of the first job. The tabu search heuristic relies on shift and swap moves, and a surrogate objective function is used to speed-up the neighborhood evaluation. Computational experiments show that the proposed heuristic consistently finds better solutions in less computation time than a recent branch-and-cut algorithm. Furthermore, on instances where the branch-and-cut algorithm cannot find the optimal solution, the heuristic always identifies a better solution. © 2008 Springer Science+Business Media, LLC.
https://doi.org/10.1007/s10951-008-0068-6Cite as:
@article{Stecco_2008,
doi = {10.1007/s10951-008-0068-6},
url = {https://doi.org/10.1007%2Fs10951-008-0068-6},
year = 2008,
month = {jul},
publisher = {Springer Science and Business Media {LLC}},
volume = {12},
number = {1},
pages = {3--16},
author = {Gabriella Stecco and Jean-Fran{c{c}}ois Cordeau and Elena Moretti},
title = {A tabu search heuristic for a sequence-dependent and~time-dependent scheduling problem on a single machine},
journal = {Journal of Scheduling}
}