{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T14:24:56Z","timestamp":1780496696558,"version":"3.54.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T00:00:00Z","timestamp":1729641600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T00:00:00Z","timestamp":1729641600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Fraunhofer-Institut f\u00fcr Techno- und Wirtschaftsmathematik ITWM"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$1 \\mid r_j, p_j = p \\mid \\sum w_j T_j$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\u2223<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mi>j<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>p<\/mml:mi>\n                      <mml:mi>j<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>p<\/mml:mi>\n                    <mml:mo>\u2223<\/mml:mo>\n                    <mml:mo>\u2211<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>w<\/mml:mi>\n                      <mml:mi>j<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:msub>\n                      <mml:mi>T<\/mml:mi>\n                      <mml:mi>j<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. 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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$1 \\mid r_j, p_j = p \\mid \\sum w_{j} T_{j}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\u2223<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mi>j<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>p<\/mml:mi>\n                      <mml:mi>j<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>p<\/mml:mi>\n                    <mml:mo>\u2223<\/mml:mo>\n                    <mml:mo>\u2211<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>w<\/mml:mi>\n                      <mml:mi>j<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:msub>\n                      <mml:mi>T<\/mml:mi>\n                      <mml:mi>j<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s10951-024-00825-w","type":"journal-article","created":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T10:02:03Z","timestamp":1729677723000},"page":"565-585","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Scheduling a single machine with multiple due dates per job"],"prefix":"10.1007","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-9217-3994","authenticated-orcid":false,"given":"Raphael","family":"K\u00fchn","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Wei\u00df","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Heiner","family":"Ackermann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sandy","family":"Heydrich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,10,23]]},"reference":[{"issue":"6","key":"825_CR1","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1002\/(SICI)1099-1425(199911\/12)2:6<245::AID-JOS28>3.0.CO;2-5","volume":"2","author":"P Baptiste","year":"1999","unstructured":"Baptiste, P. (1999). Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times. Journal of Scheduling, 2(6), 245\u2013252. https:\/\/doi.org\/10.1002\/(SICI)1099-1425(199911\/12)2:6<245::AID-JOS28>3.0.CO;2-5","journal-title":"Journal of Scheduling"},{"issue":"1\u20133","key":"825_CR2","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0166-218X(99)00238-3","volume":"103","author":"P Baptiste","year":"2000","unstructured":"Baptiste, P. (2000). Scheduling equal-length jobs on identical parallel machines. Discrete Applied Mathematics, 103(1\u20133), 21\u201332. https:\/\/doi.org\/10.1016\/S0166-218X(99)00238-3","journal-title":"Discrete Applied Mathematics"},{"key":"825_CR3","volume-title":"Scheduling Algorithms, 5","author":"P Brucker","year":"2007","unstructured":"Brucker, P. (2007). Scheduling Algorithms, 5 (ed). Springer-Verlag GmbH.","edition":"ed"},{"issue":"2","key":"825_CR4","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0377-2217(89)90100-8","volume":"38","author":"TCE Cheng","year":"1989","unstructured":"Cheng, T. C. E., & Gupta, M. C. (1989). Survey of scheduling research involving due date determination decisions. European Journal of Operational Research, 38(2), 156\u2013166. https:\/\/doi.org\/10.1016\/0377-2217(89)90100-8","journal-title":"European Journal of Operational Research"},{"key":"825_CR5","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. S.l.: A series of books in the mathematical sciences. W H Freeman."},{"issue":"3","key":"825_CR6","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0020-0190(98)00153-7","volume":"68","author":"V Gordon","year":"1998","unstructured":"Gordon, V., & Kubiak, W. (1998). Single machine scheduling with release and due date assignment to minimize the weighted number of late jobs. Information Processing Letters, 68(3), 153\u2013159. https:\/\/doi.org\/10.1016\/S0020-0190(98)00153-7","journal-title":"Information Processing Letters"},{"key":"825_CR7","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287\u2013326. https:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X","journal-title":"Annals of Discrete Mathematics"},{"issue":"5","key":"825_CR8","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1134\/S0005117920050069","volume":"81","author":"ER Gafarov","year":"2020","unstructured":"Gafarov, E. R., Lazarev, A. A., & Werner, F. (2020). Minimizing total weighted tardiness for scheduling equal-length jobs on a single machine. Automation and Remote Control, 81(5), 853\u2013868. https:\/\/doi.org\/10.1134\/S0005117920050069","journal-title":"Automation and Remote Control"},{"issue":"1","key":"825_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0377-2217(01)00181-3","volume":"139","author":"V Gordon","year":"2002","unstructured":"Gordon, V., Proth, J.-M., & Chu, C. (2002). A survey of the state-of-the-art of common due date assignment and scheduling research. European Journal of Operational Research, 139(1), 1\u201325. https:\/\/doi.org\/10.1016\/S0377-2217(01)00181-3","journal-title":"European Journal of Operational Research"},{"issue":"12","key":"825_CR10","doi-asserted-by":"publisher","first-page":"1712","DOI":"10.1287\/mnsc.40.12.1712","volume":"40","author":"AMA Hariri","year":"1994","unstructured":"Hariri, A. M. A., & Potts, C. N. (1994). Single machine scheduling with deadlines to minimize the weighted number of tardy jobs. Management Science, 40(12), 1712\u20131719. https:\/\/doi.org\/10.1287\/mnsc.40.12.1712","journal-title":"Management Science"},{"key":"825_CR11","doi-asserted-by":"publisher","unstructured":"Hertrich, C., Wei\u00df, C., Ackermann, H., Heydrich, S., & Krumke, S. O. (2020). Scheduling a proportionate flow shop of batching machines. Journal of Scheduling, 23(5), 575\u2013593. https:\/\/doi.org\/10.1007\/s10951-020-00667-2","DOI":"10.1007\/s10951-020-00667-2"},{"issue":"6","key":"825_CR12","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/s10951-022-00732-y","volume":"25","author":"C Hertrich","year":"2022","unstructured":"Hertrich, C., Wei\u00df, C., Ackermann, H., Heydrich, S., & Krumke, S. O. (2022). Online algorithms to schedule a proportionate flexible flow shop of batching machines. Journal of Scheduling, 25(6), 643\u2013657. https:\/\/doi.org\/10.1007\/s10951-022-00732-y","journal-title":"Journal of Scheduling"},{"key":"825_CR13","unstructured":"Jackson, J.R.: Scheduling a Production Line to Minimize Maximum Tardiness. Research Report 43, Mgmt. Sci. Research Project, UCLA, Los Angeles (1955)"},{"key":"825_CR14","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/S0167-5060(08)70742-8","volume":"1","author":"EL Lawler","year":"1977","unstructured":"Lawler, E. L. (1977). A \u201cpseudopolynomial\u2019\u2019 algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1, 331\u2013342. https:\/\/doi.org\/10.1016\/S0167-5060(08)70742-8","journal-title":"Annals of Discrete Mathematics"},{"key":"825_CR15","unstructured":"Lawler, E.L.: Scheduling a single machine to minimize the number of late jobs. Technical Report UCB\/CSD-83-139, EECS Department, University of California, Berkeley (Oct 1983). http:\/\/www2.eecs.berkeley.edu\/Pubs\/TechRpts\/1983\/6344.html"},{"issue":"1","key":"825_CR16","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1287\/mnsc.16.1.77","volume":"16","author":"EL Lawler","year":"1969","unstructured":"Lawler, E. L., & Moore, J. M. (1969). A functional equation and its application to resource allocation and sequencing problems. Management Science, 16(1), 77\u201384. https:\/\/doi.org\/10.1287\/mnsc.16.1.77","journal-title":"Management Science"},{"key":"825_CR17","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"JK Lenstra","year":"1977","unstructured":"Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343\u2013362. https:\/\/doi.org\/10.1016\/S0167-5060(08)70743-X","journal-title":"Annals of Discrete Mathematics"},{"issue":"1","key":"825_CR18","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1287\/mnsc.15.1.102","volume":"15","author":"JM Moore","year":"1968","unstructured":"Moore, J. M. (1968). An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15(1), 102\u2013109. https:\/\/doi.org\/10.1287\/mnsc.15.1.102","journal-title":"Management Science"},{"issue":"1","key":"825_CR19","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.ejor.2015.12.043","volume":"252","author":"D Shabtay","year":"2016","unstructured":"Shabtay, D. (2016). Optimal restricted due date assignment in scheduling. European Journal of Operational Research, 252(1), 79\u201389. https:\/\/doi.org\/10.1016\/j.ejor.2015.12.043","journal-title":"European Journal of Operational Research"},{"issue":"6","key":"825_CR20","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1016\/j.orl.2005.10.009","volume":"34","author":"D Shabtay","year":"2006","unstructured":"Shabtay, D., & Steiner, G. (2006). Two due date assignment problems in scheduling a single machine. Operations Research Letters, 34(6), 683\u2013691. https:\/\/doi.org\/10.1016\/j.orl.2005.10.009","journal-title":"Operations Research Letters"},{"issue":"6","key":"825_CR21","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/s10951-010-0181-1","volume":"13","author":"JM van den Akker","year":"2010","unstructured":"van den Akker, J. M., Diepen, G., & Hoogeveen, J. A. (2010). Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs. Journal of Scheduling, 13(6), 561\u2013576. https:\/\/doi.org\/10.1007\/s10951-010-0181-1","journal-title":"Journal of Scheduling"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-024-00825-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-024-00825-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-024-00825-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,16]],"date-time":"2024-11-16T13:03:56Z","timestamp":1731762236000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-024-00825-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,23]]},"references-count":21,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["825"],"URL":"https:\/\/doi.org\/10.1007\/s10951-024-00825-w","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,23]]},"assertion":[{"value":"1 October 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 October 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}