Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
<|reference_start|>Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times: In this work, we study the task of scheduling jobs on a single machine with sequence dependent family setup times under the goal of minimizing the makespan, that is, the completion time of the last job in the schedule. This notoriously NP-hard problem is highly relevant in practical productions and requires heuristics that provide good solutions quickly in order to deal with large instances. In this paper, we present a heuristic based on the approach of parameterized local search. That is, we aim to replace a given solution by a better solution having distance at most $k$ in a pre-defined distance measure. This is done multiple times in a hill-climbing manner, until a locally optimal solution is reached. We analyze the trade-off between the allowed distance $k$ and the algorithm's running time for four natural distance measures. Example of allowed operations for our considered distance measures are: swapping $k$ pairs of jobs in the sequence, or rearranging $k$ consecutive jobs. For two distance measures, we show that finding an improvement for given $k$ can be done in $f(k) \cdot n^{\mathcal{O}(1)}$ time, while such a running time for the other two distance measures is unlikely. We provide a preliminary experimental evaluation of our local search approaches.<|reference_end|>
@article{balzereit2024scalable,
    title={Scalable Neighborhood Local Search for Single-Machine Scheduling with
  Family Setup Times},
    author={Kaja Balzereit, Niels Gr"uttemeier, Nils Morawietz, Dennis Reinhardt,
  Stefan Windmann, Petra Wolf},
    journal={arXiv preprint arXiv:2409.00771},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.00771},
    primaryClass={cs.DS cs.CC}
}