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

Abstract

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.