Single-machine scheduling with release times, deadlines, setup times, and rejection

Single-machine scheduling where jobs have a penalty for being late or for being rejected altogether is an important (sub)problem in manufacturing, logistics, and satellite scheduling. It is known to be NP-hard in the strong sense, and there is no polynomial-time algorithm that can guarantee a constant-factor approximation (unless P=NP). We provide an exact algorithm that is fixed-parameter tractable in the slack and the maximum number of time windows overlapping at any point in time, i.e., the width. This algorithm has a runtime exponential in these parameters, but quadratic in the number of jobs, even when modeling sequence-dependent setup times. We further provide a fixed-parameter fully-polynomial time approximation scheme (FPTAS) with only this width as a parameter, having a runtime bound that is cubic. Finally, we propose a neighbourhood heuristic similar to the Balas-Simonetti neighbourhood. All algorithms use an efficient representation of the state space inspired by decision diagrams, where partial solutions that are provably dominated are excluded from further consideration. Experimental evidence shows that the exact method significantly outperforms the state-of-the-art on instances where the width is smaller than one third of the number of jobs and finds optimal solutions to previously unsolved instances. The FPTAS is competitive to state-of-the-art heuristics only when the width is significantly smaller, but the neighbourhood heuristic outperforms most other heuristics in runtime or quality. (c) 2020 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/)

Automated summary

In single-machine scheduling with penalties, the problem is known to be NP-hard and lacks a polynomial-time constant-factor approximation algorithm. The provided exact algorithm is fixed-parameter tractable in certain parameters and a fixed-parameter fully-polynomial time approximation scheme is also offered. Experimental results show the exact method outperforms current methods on certain instances, while the neighbourhood heuristic performs better in runtime or quality compared to other heuristics.