Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/315297 
Erscheinungsjahr: 
2024
Quellenangabe: 
[Journal:] Journal of Scheduling [ISSN:] 1099-1425 [Volume:] 27 [Issue:] 6 [Publisher:] Springer US [Place:] New York [Year:] 2024 [Pages:] 565-585
Verlag: 
Springer US, New York
Zusammenfassung: 
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∣rj,pj=p∣∑wjTj. 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∣rj,pj=p∣∑wjTj.
Schlagwörter: 
Single-machine scheduling
Multiple due dates
Branch and bound
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version
Erscheint in der Sammlung:

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.