{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T05:53:41Z","timestamp":1746770021133,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,6,25]],"date-time":"2022-06-25T00:00:00Z","timestamp":1656115200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,25]],"date-time":"2022-06-25T00:00:00Z","timestamp":1656115200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001774","name":"University of Sydney","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001774","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study two <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard single-machine scheduling problems with generalized due-dates. In such problems, due-dates are associated with positions in the job sequence rather than with jobs. Accordingly, the job that is assigned to position <jats:italic>j<\/jats:italic> in the job processing order (job sequence), is assigned with a predefined due-date, <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta _{j}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mi>j<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In the first problem, the objective consists of finding a job schedule that minimizes the maximal absolute lateness, while in the second problem, we aim to maximize the weighted number of jobs completed exactly at their due-date. Both problems are known to be strongly <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard when the instance includes an arbitrary number of different due-dates. Our objective is to study the tractability of both problems with respect to the number of different due-dates in the instance, <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\nu _{d}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u03bd<\/mml:mi>\n                    <mml:mi>d<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We show that both problems remain <jats:inline-formula><jats:alternatives><jats:tex-math>$$ \\mathcal {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard even when <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\nu _{d}=2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>\u03bd<\/mml:mi>\n                      <mml:mi>d<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and are solvable in pseudo-polynomial time when the value of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\nu _{d}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u03bd<\/mml:mi>\n                    <mml:mi>d<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is upper bounded by a constant. To complement our results, we show that both problems are fixed parameterized tractable (<jats:italic>FPT<\/jats:italic>) when we combine the two parameters of number of different due-dates (<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\nu _{d}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u03bd<\/mml:mi>\n                    <mml:mi>d<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>) and number of different processing times (<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\nu _{p}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u03bd<\/mml:mi>\n                    <mml:mi>p<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>).<\/jats:p>","DOI":"10.1007\/s10951-022-00743-9","type":"journal-article","created":{"date-parts":[[2022,6,25]],"date-time":"2022-06-25T13:04:19Z","timestamp":1656162259000},"page":"577-587","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates"],"prefix":"10.1007","volume":"25","author":[{"given":"Gur","family":"Mosheiov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2571-6676","authenticated-orcid":false,"given":"Daniel","family":"Oron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dvir","family":"Shabtay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,25]]},"reference":[{"key":"743_CR1","unstructured":"Browne, J., Dubois, D., Rathmill, K., Sethi, S. P., & Stecke, K. (1984). Classification of flexible manufacturing systems. The FMS Magazine, 2, 114\u2013117."},{"key":"743_CR2","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0898-1221(87)90136-2","volume":"14","author":"TCE Cheng","year":"1987","unstructured":"Cheng, T. C. E. (1987). Minimizing the maximum deviation of job completion time about a common due-date. Computers and Mathematics with Applications, 14, 279\u2013283.","journal-title":"Computers and Mathematics with Applications"},{"key":"743_CR3","doi-asserted-by":"crossref","unstructured":"Downey, R., & Fellows, M. (1999). Parameterized complexity. Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"743_CR4","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1287\/moor.15.3.483","volume":"15","author":"J Du","year":"1990","unstructured":"Du, J., & Leung, J. Y. T. (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 15, 483\u2013495.","journal-title":"Mathematics of Operations Research"},{"key":"743_CR5","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability - a guide to the theory of NP completeness. Freeman."},{"key":"743_CR6","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1287\/moor.13.2.330","volume":"13","author":"MR Garey","year":"1988","unstructured":"Garey, M. R., Tarjan, R. E., & Wilfong, G. T. (1988). One-processor scheduling with symmetric earliness and tardiness penalties. Mathematics of Operations Research, 13, 330\u2013348.","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"743_CR7","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s10951-020-00638-7","volume":"23","author":"E Gerstl","year":"2020","unstructured":"Gerstl, E., & Mosheiov, G. (2020). Single machine scheduling to maximize the number of on-time jobs with generalized due-dates. Journal of Scheduling, 23(3), 289\u2013299.","journal-title":"Journal of Scheduling"},{"key":"743_CR8","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.orl.2015.12.006","volume":"44","author":"Y Gao","year":"2006","unstructured":"Gao, Y., & Yuan, J. (2006). Unary NP-hardness of minimizing total weighted tardiness with generalized due-dates. Operations Research Letters, 44, 92\u201395.","journal-title":"Operations Research Letters"},{"key":"743_CR9","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.","journal-title":"Annals of Discrete Mathematics"},{"key":"743_CR10","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1080\/07408178608975351","volume":"18","author":"NG Hall","year":"1986","unstructured":"Hall, N. G. (1986). Scheduling problems with generalized due dates. IIE Transactions, 18, 220\u2013222.","journal-title":"IIE Transactions"},{"key":"743_CR11","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/0377-2217(91)90149-P","volume":"51","author":"NG Hall","year":"1991","unstructured":"Hall, N. G., Sethi, S. P., & Sriskandarajah, C. (1991). On the complexity of generalized due-date scheduling problems. European Journal of Operational Research, 51, 100\u2013109.","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"743_CR12","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N Karmarkar","year":"1984","unstructured":"Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming. Combinatorica, 4(4), 373\u2013395.","journal-title":"Combinatorica"},{"key":"743_CR13","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1016\/0305-0548(95)00078-X","volume":"23","author":"A Lann","year":"1996","unstructured":"Lann, A., & Mosheiov, G. (1996). Machine scheduling to minimize the number of early and tardy jobs. Computers and Operations Research, 23, 765\u2013781.","journal-title":"Computers and Operations Research"},{"issue":"4","key":"743_CR14","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HL Lenstra","year":"1983","unstructured":"Lenstra, H. L. (1983). Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4), 538\u2013548.","journal-title":"Mathematics of Operations Research"},{"key":"743_CR15","doi-asserted-by":"crossref","unstructured":"Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford lecture series in mathematics and its applications. Oxford Univerity Press.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"743_CR16","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1002\/1520-6750(199008)37:4<587::AID-NAV3220370411>3.0.CO;2-O","volume":"37","author":"C Sriskandarajah","year":"1990","unstructured":"Sriskandarajah, C. (1990). A note on the generalized due-dates scheduling problems. Naval Research Logistics, 37, 587\u2013597.","journal-title":"Naval Research Logistics"},{"key":"743_CR17","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1080\/00207548108956679","volume":"19","author":"KE Stecke","year":"1981","unstructured":"Stecke, K. E., & Solberg, J. J. (1981). Loading and control policies for a flexible manufacturing system. International Journal of Production Research, 19, 481\u2013490.","journal-title":"International Journal of Production Research"},{"key":"743_CR18","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1023\/A:1018987625819","volume":"86","author":"K Tanaka","year":"1999","unstructured":"Tanaka, K., & Vlach, M. (1999). Minimizing maximum absolute lateness and range of lateness under generalized due-dates on a single machine. Annals of Operations Research, 86, 507\u2013526.","journal-title":"Annals of Operations Research"},{"key":"743_CR19","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1016\/j.amc.2012.08.008","volume":"219","author":"Y Yin","year":"2012","unstructured":"Yin, Y., Cheng, S. R., Cheng, T. C. E., Wu, C. C., & Wu, W. H. (2012). Two-agent single-machine scheduling with assignable due-dates. Applied Mathematics and Computation, 219, 1674\u20131685.","journal-title":"Applied Mathematics and Computation"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00743-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-022-00743-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00743-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T08:19:16Z","timestamp":1664439556000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-022-00743-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,25]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["743"],"URL":"https:\/\/doi.org\/10.1007\/s10951-022-00743-9","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2022,6,25]]},"assertion":[{"value":"8 April 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}