| Autor: |
Balzereit, Kaja, Grüttemeier, Niels, Morawietz, Nils, Reinhardt, Dennis, Windmann, Stefan, Wolf, Petra |
| Rok vydání: |
2024 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
