Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910889133735936 |
|---|---|
| author | Balzereit, Kaja Grüttemeier, Niels Morawietz, Nils Reinhardt, Dennis Windmann, Stefan Wolf, Petra |
| author_facet | Balzereit, Kaja Grüttemeier, Niels Morawietz, Nils Reinhardt, Dennis Windmann, Stefan Wolf, Petra |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_00771 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times Balzereit, Kaja Grüttemeier, Niels Morawietz, Nils Reinhardt, Dennis Windmann, Stefan Wolf, Petra Data Structures and Algorithms Computational Complexity 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. |
| title | Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2409.00771 |