Scheduling a single machine with multiple due dates per job

Raphael Kühn (), Christian Weiß (), Heiner Ackermann () and Sandy Heydrich ()
Additional contact information
Raphael Kühn: Fraunhofer Institute for Industrial Mathematics ITWM
Christian Weiß: Fraunhofer Institute for Industrial Mathematics ITWM
Heiner Ackermann: Fraunhofer Institute for Industrial Mathematics ITWM
Sandy Heydrich: Fraunhofer Institute for Industrial Mathematics ITWM

Journal of Scheduling, 2024, vol. 27, issue 6, No 4, 565-585

Abstract: Abstract In this paper, we consider single-machine scheduling with multiple due dates per job. This is motivated by several industrial applications, where it is not important by how much we miss a due date. Instead the relevant objective is to minimize the number of missed due dates. Typically, this situation emerges whenever fixed delivery appointments are chosen in advance, such as in the production of individualized pharmaceuticals or when customers can only receive goods at certain days in the week, due to constraints in their warehouse operation. We compare this previously unexplored problem with classical due date scheduling, for which it is a generalization. We show that single-machine scheduling with multiple due dates is NP-hard in the strong sense if processing times are job dependent. If processing times are equal for all jobs, then single-machine scheduling with multiple due dates is at least as hard as the long-standing open problem of weighted tardiness with equal processing times and release dates $$1 \mid r_j, p_j = p \mid \sum w_j T_j$$ 1 ∣ r j , p j = p ∣ ∑ w j T j . Finally, we focus on the case of equal processing times and provide several polynomially solvable special cases as well as an exact branch-and-bound algorithm and heuristics for the general case. Experiments show that our branch-and-bound algorithm compares well to modern exact methods to solve problem $$1 \mid r_j, p_j = p \mid \sum w_{j} T_{j}$$ 1 ∣ r j , p j = p ∣ ∑ w j T j .

Keywords: Single-machine scheduling; Multiple due dates; Branch and bound (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-024-00825-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:27:y:2024:i:6:d:10.1007_s10951-024-00825-w

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-024-00825-w

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().