Abstract: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.
From: Niels Grüttemeier [view email]
[v1]
Sun, 1 Sep 2024 16:31:31 UTC (55 KB)
[v2]
Wed, 4 Sep 2024 21:00:54 UTC (55 KB)
[v3]
Mon, 24 Mar 2025 09:34:41 UTC (45 KB)
[v4]
Wed, 2 Sep 2026 12:46:51 UTC (60 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。