{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T15:03:13Z","timestamp":1772550193430,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T00:00:00Z","timestamp":1726185600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T00:00:00Z","timestamp":1726185600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["452470135"],"award-info":[{"award-number":["452470135"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003483","name":"Hebrew University of Jerusalem","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003483","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We study a single machine scheduling problem with generalized due-dates and general position-dependent job processing times. The objective function is minimum number of tardy jobs. The problem is proved to be NP-hard in the strong sense. We introduce an efficient algorithm that solves medium size problems in reasonable running time. A simple and efficient heuristic is also introduced, which obtained the optimal solution in the vast majority of our tests.<\/jats:p>","DOI":"10.1007\/s11590-024-02138-5","type":"journal-article","created":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T04:02:20Z","timestamp":1726200140000},"page":"833-845","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Minimizing the number of tardy jobs with generalized due-dates and position-dependent processing times"],"prefix":"10.1007","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9158-984X","authenticated-orcid":false,"given":"Enrique","family":"Gerstl","sequence":"first","affiliation":[]},{"given":"Gur","family":"Mosheiov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,13]]},"reference":[{"key":"2138_CR1","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1080\/07408178608975351","volume":"18","author":"NG Hall","year":"1986","unstructured":"Hall, N.G.: Scheduling problems with generalized due dates. IIE Trans. 18, 220\u2013222 (1986)","journal-title":"IIE Trans."},{"key":"2138_CR2","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.: On the complexity of generalized due date scheduling problems. Eur. J. Oper. Res.Oper. Res. 51, 100\u2013109 (1991)","journal-title":"Eur. J. Oper. Res.Oper. Res."},{"key":"2138_CR3","doi-asserted-by":"publisher","first-page":"3164","DOI":"10.1080\/00207543.2016.1266055","volume":"55","author":"E Gerstl","year":"2017","unstructured":"Gerstl, E., Mosheiov, G.: Single machine scheduling problems with generalized due-dates and job-rejection. Int. J. Prod. Res. 55, 3164\u20133172 (2017)","journal-title":"Int. J. Prod. Res."},{"key":"2138_CR4","doi-asserted-by":"publisher","first-page":"1850046","DOI":"10.1142\/S021759591850046X","volume":"35","author":"BC Choi","year":"2018","unstructured":"Choi, B.C., Park, M.J.: Just-in-time scheduling with generalized due dates and identical due date intervals. Asia-Pacific J. Oper. Res.Oper. Res. 35, 1850046 (2018)","journal-title":"Asia-Pacific J. Oper. Res.Oper. Res."},{"key":"2138_CR5","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/j.ajsl.2018.12.008","volume":"34","author":"MJ Park","year":"2018","unstructured":"Park, M.J., Min, Y.H., Choi, B.C.: Two-agent scheduling with generalized due dates. Asian J Shipp Logist 34, 345\u2013350 (2018)","journal-title":"Asian J Shipp Logist"},{"key":"2138_CR6","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1016\/j.orl.2019.08.002","volume":"47","author":"BC Choi","year":"2019","unstructured":"Choi, B.C., Min, Y., Park, M.J.: Strong NP-hardness of minimizing total deviation with generalized and periodic due dates. Oper. Res. Lett. Res. Lett. 47, 433\u2013437 (2019)","journal-title":"Oper. Res. Lett. Res. Lett."},{"key":"2138_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.: Single machine to maximize the number of on-time jobs with generalized due-dates. J. Sched. 23, 289\u2013299 (2020)","journal-title":"J. Sched."},{"key":"2138_CR8","doi-asserted-by":"crossref","unstructured":"Choi, B. C., Park, M. J., and Min, Y.: A Just-in-time Scheduling Problem with Generalized Due Dates and Controllable Processing Times. \ud55c\uad6d SCM \ud559\ud68c\uc9c0. 20(1), 17\u201323 (2020)","DOI":"10.25052\/KSCM.2020.05.20.1.17"},{"key":"2138_CR9","doi-asserted-by":"publisher","first-page":"1681","DOI":"10.1007\/s11590-019-01462-5","volume":"14","author":"SS Li","year":"2020","unstructured":"Li, S.S., Chen, R.X.: Scheduling with common due date assignment to minimize generalized weighted earliness\u2013tardiness penalties. Optim. Lett. 14, 1681\u20131699 (2020)","journal-title":"Optim. Lett."},{"key":"2138_CR10","doi-asserted-by":"publisher","first-page":"1950032","DOI":"10.1142\/S0217595919500325","volume":"37","author":"MJ Park","year":"2020","unstructured":"Park, M.J., Choi, B.C., Min, Y., Kim, K.M.: Two-machine ordered flow shop scheduling with generalized due dates. Asia-Pacific J. Oper. Res.Oper. Res. 37, 1950032 (2020)","journal-title":"Asia-Pacific J. Oper. Res.Oper. Res."},{"key":"2138_CR11","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/s10951-021-00697-4","volume":"24","author":"B Mor","year":"2021","unstructured":"Mor, B., Mosheiov, G., Shabtay, D.: Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates. J. Sched. 24, 553\u2013567 (2021)","journal-title":"J. Sched."},{"key":"2138_CR12","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s11590-021-01739-8","volume":"16","author":"BC Choi","year":"2022","unstructured":"Choi, B.C., Kim, K.M., Min, Y., Park, M.J.: Scheduling with generalized and periodic due dates under single-and two-machine environments. Optim. Lett. 16, 623\u2013633 (2022)","journal-title":"Optim. Lett."},{"key":"2138_CR13","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1016\/j.ejor.2020.12.061","volume":"293","author":"G Mosheiov","year":"2021","unstructured":"Mosheiov, G., Oron, D., Shabtay, D.: Minimizing total late work on a single machine with generalized due-dates. Eur. J. Oper. Res.Oper. Res. 293, 837\u2013846 (2021)","journal-title":"Eur. J. Oper. Res.Oper. Res."},{"issue":"5","key":"2138_CR14","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/s10951-022-00743-9","volume":"25","author":"G Mosheiov","year":"2022","unstructured":"Mosheiov, G., Oron, D., Shabtay, D.: On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates. J. Sched. 25(5), 577\u2013587 (2022). https:\/\/doi.org\/10.1007\/s10951-022-00743-9","journal-title":"J. Sched."},{"key":"2138_CR15","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0377-2217(98)00246-X","volume":"115","author":"D Biskup","year":"1999","unstructured":"Biskup, D.: Single-machine scheduling with learning considerations. Eur. J. Oper. Res.Oper. Res. 115, 173\u2013178 (1999)","journal-title":"Eur. J. Oper. Res.Oper. Res."},{"key":"2138_CR16","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ejor.2007.05.040","volume":"188","author":"D Biskup","year":"2008","unstructured":"Biskup, D.: A state-of-the-art review on scheduling with learning effects. Eur. J. Oper. Res.Oper. Res. 188, 315\u2013329 (2008)","journal-title":"Eur. J. Oper. Res.Oper. Res."},{"key":"2138_CR17","doi-asserted-by":"publisher","first-page":"2311","DOI":"10.1080\/00207543.2013.855833","volume":"52","author":"Y Yin","year":"2014","unstructured":"Yin, Y., Wu, W.H., Cheng, T.C.E., Wu, C.C.: Due-date assignment and single-machine scheduling with generalised position-dependent deteriorating jobs and deteriorating multi-maintenance activities. Int. J. Prod. Res. 52, 2311\u20132326 (2014)","journal-title":"Int. J. Prod. Res."},{"key":"2138_CR18","doi-asserted-by":"publisher","first-page":"2897","DOI":"10.1016\/j.apm.2014.11.002","volume":"39","author":"X Huang","year":"2015","unstructured":"Huang, X., Wang, J.J.: Machine scheduling problems with a position-dependent deterioration. Appl. Math. Model. 39, 2897\u20132908 (2015)","journal-title":"Appl. Math. Model."},{"key":"2138_CR19","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.ipl.2010.11.016","volume":"111","author":"G Mosheiov","year":"2011","unstructured":"Mosheiov, G.: Proportionate flowshops with general position-dependent processing times. Inf. Process. Lett. 111, 174\u2013177 (2011)","journal-title":"Inf. Process. Lett."},{"key":"2138_CR20","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1016\/j.ipl.2012.06.009","volume":"112","author":"E Gerstl","year":"2012","unstructured":"Gerstl, E., Mosheiov, G.: Scheduling on parallel identical machines with job-rejection and position-dependent processing times. Inf. Process. Lett. 112, 743\u2013747 (2012)","journal-title":"Inf. Process. Lett."},{"key":"2138_CR21","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1016\/j.ipl.2014.02.009","volume":"114","author":"X Yu","year":"2014","unstructured":"Yu, X., Zhang, Y., Huang, K.: Multi-machine scheduling with general position-based deterioration to minimize total load revisited. Inf. Process. Lett. 114, 399\u2013404 (2014)","journal-title":"Inf. Process. Lett."},{"key":"2138_CR22","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1007\/s11590-016-1059-8","volume":"11","author":"A Agnetis","year":"2017","unstructured":"Agnetis, A., Mosheiov, G.: Scheduling with job-rejection and position-dependent processing times on proportionate flowshops. Optim. Lett. 11, 885\u2013892 (2017)","journal-title":"Optim. Lett."},{"key":"2138_CR23","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/j.cor.2017.02.010","volume":"83","author":"E Gerstl","year":"2017","unstructured":"Gerstl, E., Mor, B., Mosheiov, G.: Minmax scheduling with acceptable lead-times: extensions to position-dependent processing times, due-window and job rejection. Comput. Oper. Res. Oper. Res. 83, 150\u2013156 (2017)","journal-title":"Comput. Oper. Res. Oper. Res."},{"key":"2138_CR24","doi-asserted-by":"publisher","first-page":"1257","DOI":"10.1007\/s11590-016-1074-9","volume":"11","author":"J Pei","year":"2017","unstructured":"Pei, J., Liu, X., Pardalos, P.M., Li, K., Fan, W., Migdalas, A.: Single-machine serial-batching scheduling with a machine availability constraint, position-dependent processing time, and time-dependent set-up time. Optim. Lett. 11, 1257\u20131271 (2017)","journal-title":"Optim. Lett."},{"key":"2138_CR25","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.ipl.2017.12.004","volume":"132","author":"S Fiszman","year":"2018","unstructured":"Fiszman, S., Mosheiov, G.: Minimizing total load on a proportionate flowshop with position-dependent processing times and job-rejection. Inf. Process. Lett. 132, 39\u201343 (2018)","journal-title":"Inf. Process. Lett."},{"key":"2138_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ipl.2019.02.008","volume":"147","author":"MY Kovalyov","year":"2019","unstructured":"Kovalyov, M.Y., Mosheiov, G., \u0160e\u0161ok, D.: Comments on \u201cproportionate flowshops with general position dependent processing times\u201d [Inf. Process. Lett. 111 (2011) 174\u2013177] and \u201cminimizing total load on a proportionate flowshop with position-dependent processing times and job-rejection\u201d [Inf. process. Lett. 132 (2018) 39\u201343]. Inf. Process. Lett. 147, 1\u20132 (2019)","journal-title":"Inf. Process. Lett."},{"key":"2138_CR27","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.tcs.2019.08.023","volume":"796","author":"L Yang","year":"2019","unstructured":"Yang, L., Lu, X.: Two-agent scheduling problems with the general position-dependent processing time. Theoret. Comput. Sci.. Comput. Sci. 796, 90\u201398 (2019)","journal-title":"Theoret. Comput. Sci.. Comput. Sci."},{"issue":"4","key":"2138_CR28","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s10288-019-00418-w","volume":"18","author":"G Mosheiov","year":"2020","unstructured":"Mosheiov, G., Sarig, A., Strusevich, V.: Minmax scheduling and due-window assignment with position-dependent processing times and job rejection. 4OR 18(4), 439\u2013456 (2020). https:\/\/doi.org\/10.1007\/s10288-019-00418-w","journal-title":"4OR"},{"key":"2138_CR29","doi-asserted-by":"crossref","unstructured":"Montoya-Torres, J. R., Botta-Genoulaz, V., Materzok, N., G\u00edslason, \u00de. P. and Mendiela, S.: Modeling the parallel machine scheduling problem with worker-and position-dependent processing times. In: IFIP International Conference on Advances in Production Management Systems. pp. 351\u2013359. Springer, Cham (2021)","DOI":"10.1007\/978-3-030-85906-0_39"},{"key":"2138_CR30","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10878-021-00821-2","volume":"44","author":"B Przybylski","year":"2022","unstructured":"Przybylski, B.: Parallel-machine scheduling of jobs with mixed job-, machine-and position-dependent processing times. J. Comb. Optim.Optim. 44, 207\u2013222 (2022)","journal-title":"J. Comb. Optim.Optim."},{"key":"2138_CR31","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.: An n job, one machine sequencing algorithm for minimizing the number of late jobs. Manag. Sci. 15, 102\u2013109 (1968)","journal-title":"Manag. Sci."},{"key":"2138_CR32","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0377-2217(93)E0280-B","volume":"84","author":"JC Ho","year":"1995","unstructured":"Ho, J.C., Chang, Y.L.: Minimizing the number of tardy jobs for m parallel machines. Eur. J. Oper. Res.Oper. Res. 84, 343\u2013355 (1995)","journal-title":"Eur. J. Oper. Res.Oper. Res."},{"key":"2138_CR33","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1016\/0305-0548(95)00078-X","volume":"23","author":"A Lann","year":"1996","unstructured":"Lann, A., Mosheiov, G.: Single machine scheduling to minimize the number of early and tardy jobs. Comput. Oper. Res.. Oper. Res. 23, 769\u2013778 (1996)","journal-title":"Comput. Oper. Res.. Oper. Res."},{"key":"2138_CR34","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/S0377-2217(03)00404-1","volume":"159","author":"E Lodree Jr","year":"2004","unstructured":"Lodree, E., Jr., Jang, W., Klein, C.M.: A new rule for minimizing the number of tardy jobs in dynamic flow shops. Eur. J. Oper. Res.Oper. Res. 159, 258\u2013263 (2004)","journal-title":"Eur. J. Oper. Res.Oper. Res."},{"key":"2138_CR35","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1057\/palgrave.jors.2601809","volume":"56","author":"G Mosheiov","year":"2005","unstructured":"Mosheiov, G., Sidney, J.B.: Note on scheduling with general learning curves to minimize the number of tardy jobs. J Operational Res Soc 56, 110\u2013112 (2005)","journal-title":"J Operational Res Soc"},{"key":"2138_CR36","doi-asserted-by":"publisher","first-page":"1601","DOI":"10.1016\/j.cor.2011.09.011","volume":"39","author":"G Mosheiov","year":"2012","unstructured":"Mosheiov, G., Oron, D.: Minimizing the number of tardy jobs on a proportionate flowshop with general position-dependent processing times. Comput. Oper. Res.. Oper. Res. 39, 1601\u20131604 (2012)","journal-title":"Comput. Oper. Res.. Oper. Res."},{"issue":"1","key":"2138_CR37","doi-asserted-by":"publisher","first-page":"219","DOI":"10.3934\/jimo.2014.10.219","volume":"10","author":"MO Adamu","year":"2013","unstructured":"Adamu, M.O., Adewumi, A.O.: A survey of single machine scheduling to minimize weighted number of tardy jobs. J Ind manag optim 10(1), 219\u2013241 (2013)","journal-title":"J Ind manag optim"},{"key":"2138_CR38","first-page":"391","volume":"33","author":"A Allahverdi","year":"2016","unstructured":"Allahverdi, A., Aydilek, A., Aydilek, H.: Minimizing the number of tardy jobs on a two-stage assembly flowshop. J. Ind. Prod. Eng. 33, 391\u2013403 (2016)","journal-title":"J. Ind. Prod. Eng."},{"key":"2138_CR39","doi-asserted-by":"publisher","first-page":"982","DOI":"10.1016\/j.apm.2017.01.039","volume":"45","author":"A Aydilek","year":"2017","unstructured":"Aydilek, A., Aydilek, H., Allahverdi, A.: Algorithms for minimizing the number of tardy jobs for reducing production cost with uncertain processing times. Appl. Math. Model. 45, 982\u2013996 (2017)","journal-title":"Appl. Math. Model."},{"key":"2138_CR40","doi-asserted-by":"publisher","first-page":"106009","DOI":"10.1016\/j.ipl.2020.106009","volume":"164","author":"B Mor","year":"2020","unstructured":"Mor, B., Mosheiov, G., Shapira, D.: Lot scheduling on a single machine to minimize the (weighted) number of tardy orders. Inf. Process. Lett. 164, 106009 (2020)","journal-title":"Inf. Process. Lett."},{"key":"2138_CR41","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1007\/s10878-021-00697-2","volume":"41","author":"R He","year":"2021","unstructured":"He, R., Yuan, J., Ng, C.T., Cheng, T.C.E.: Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work. J. Comb. Optim.Optim. 41, 504\u2013525 (2021)","journal-title":"J. Comb. Optim.Optim."},{"key":"2138_CR42","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10479-018-2852-9","volume":"298","author":"D Hermelin","year":"2021","unstructured":"Hermelin, D., Karhi, S., Pinedo, M., Shabtay, D.: New algorithms for minimizing the weighted number of tardy jobs on a single machine. Ann. Oper. Res.Oper. Res. 298, 271\u2013287 (2021)","journal-title":"Ann. Oper. Res.Oper. Res."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-024-02138-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-024-02138-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-024-02138-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,15]],"date-time":"2025-04-15T05:37:32Z","timestamp":1744695452000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-024-02138-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,13]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["2138"],"URL":"https:\/\/doi.org\/10.1007\/s11590-024-02138-5","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,13]]},"assertion":[{"value":"10 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 September 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}