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

Mathijs de Weerdt, Robert Baart and Lei He

European Journal of Operational Research, 2021, vol. 291, issue 2, 629-639

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.

Keywords: Scheduling; Order acceptance; Dynamic programming; Decision diagrams; Fixed-parameter tractability (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720308468
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:291:y:2021:i:2:p:629-639

DOI: 10.1016/j.ejor.2020.09.042

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().