{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T15:29:03Z","timestamp":1768404543363,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,10,7]],"date-time":"2022-10-07T00:00:00Z","timestamp":1665100800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,7]],"date-time":"2022-10-07T00:00:00Z","timestamp":1665100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100009882","name":"Regione Lombardia","doi-asserted-by":"publisher","award":["E97F17000000009"],"award-info":[{"award-number":["E97F17000000009"]}],"id":[{"id":"10.13039\/501100009882","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009057","name":"Karl-Franzens-Universit\u00e4t Graz","doi-asserted-by":"publisher","award":["COLIBRI"],"award-info":[{"award-number":["COLIBRI"]}],"id":[{"id":"10.13039\/501100009057","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Rescheduling can help to improve the quality of a schedule with respect to an initially given sequence. In this paper, we consider the possibility of rescheduling jobs arriving for processing at a single machine under the following limitations: (a) jobs can only be moved toward the end of the schedule and not toward the front, and (b) when a job is taken out of the sequence, it is put on a buffer of limited capacity before being reinserted in its new position closer to the end of the sequence. The buffer is organized as a stack with a last-in\/first-out policy. As an objective function, we consider the minimization of the weighted number of late jobs. For this NP-hard problem, we first provide two different integer linear programming (ILP) formulations. Furthermore, we develop a branch-and-bound algorithm with a branching rule based on the movement of jobs. Then a new pseudo-polynomial dynamic programming algorithm is presented which utilizes dominance criteria and an efficient handling of states. Our computational experiments with up to 100 jobs show that this algorithm performs remarkably well and can be seen as the current method of choice.<\/jats:p>","DOI":"10.1007\/s10951-022-00751-9","type":"journal-article","created":{"date-parts":[[2022,10,7]],"date-time":"2022-10-07T19:02:42Z","timestamp":1665169362000},"page":"267-287","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Algorithms for rescheduling jobs with a LIFO buffer to minimize the weighted number of late jobs"],"prefix":"10.1007","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8881-1497","authenticated-orcid":false,"given":"Ulrich","family":"Pferschy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julia","family":"Resch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giovanni","family":"Righini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,7]]},"reference":[{"issue":"7","key":"751_CR1","doi-asserted-by":"publisher","first-page":"2065","DOI":"10.1080\/002075497195074","volume":"35","author":"R Abumaizar","year":"1997","unstructured":"Abumaizar, R., & Svestka, J. (1997). Rescheduling job shops under random disruptions. International Journal of Production Research, 35(7), 2065\u20132082.","journal-title":"International Journal of Production Research"},{"issue":"15","key":"751_CR2","doi-asserted-by":"publisher","first-page":"2044","DOI":"10.1016\/j.dam.2005.04.019","volume":"154","author":"A Agnetis","year":"2006","unstructured":"Agnetis, A., Hall, N. G., & Pacciarelli, D. (2006). Supply chain scheduling: Sequence coordination. Discrete Applied Mathematics, 154(15), 2044\u20132063.","journal-title":"Discrete Applied Mathematics"},{"key":"751_CR3","unstructured":"Alfieri, A., Nicosia, G., Pacifici, & Pferschy, U. (2018a). Single machine scheduling with bounded job rearrangements. In: Proceedings of 16th cologne-Twente workshop on graphs and combinatorial optimization, 124\u2013127."},{"key":"751_CR4","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-030-00473-6_5","volume-title":"New Trends in Emerging Complex Real Life Problems, AIRO Springer Series","author":"A Alfieri","year":"2018","unstructured":"Alfieri, A., Nicosia, G., Pacifici, A., & Pferschy, U. (2018b). Constrained Job Rearrangements on a Single Machine. In P. Daniele & L. Scrimali (Eds.), New Trends in Emerging Complex Real Life Problems, AIRO Springer Series (Vol. 1, pp. 33\u201341). Springer."},{"issue":"1","key":"751_CR5","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/s10951-018-0570-4","volume":"22","author":"F Ballest\u00edn","year":"2019","unstructured":"Ballest\u00edn, F., P\u00e9rez, A., & Quintanilla, S. (2019). Scheduling and rescheduling elective patients in operating rooms to minimise the percentage of tardy patients. Journal of Scheduling, 22(1), 107\u2013118.","journal-title":"Journal of Scheduling"},{"key":"751_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.cor.2019.03.001","volume":"107","author":"P Detti","year":"2019","unstructured":"Detti, P., Nicosia, G., Pacifici, A., Manrique, Zabalo, & de Lara, G. (2019). Robust single machine scheduling with a flexible maintenance activity. Computers & Operations Research, 107, 19\u201331.","journal-title":"Computers & Operations Research"},{"key":"751_CR7","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s10951-006-7186-9","volume":"9","author":"A Drexl","year":"2006","unstructured":"Drexl, A., Kimms, A., & Matthie\u00dfen, L. (2006). Algorithms for the car sequencing and the level scheduling problem. Journal of Scheduling, 9, 153\u2013176.","journal-title":"Journal of Scheduling"},{"key":"751_CR8","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"},{"issue":"4","key":"751_CR9","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1287\/ijoc.1060.0209","volume":"19","author":"NG Hall","year":"2007","unstructured":"Hall, N. G., Liu, Z., & Potts, C. N. (2007). Rescheduling for Multiple New Orders. INFORMS Journal on Computing, 19(4), 633\u2013645.","journal-title":"INFORMS Journal on Computing"},{"issue":"3","key":"751_CR10","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1287\/opre.1030.0101","volume":"52","author":"N Hall","year":"2004","unstructured":"Hall, N., & Potts, C. N. (2004). Rescheduling for new orders. Operations Research, 52(3), 440\u2013453.","journal-title":"Operations Research"},{"issue":"3","key":"751_CR11","doi-asserted-by":"publisher","first-page":"746","DOI":"10.1287\/opre.1090.0751","volume":"58","author":"NG Hall","year":"2010","unstructured":"Hall, N. G., & Potts, C. N. (2010). Rescheduling for Job Unavailability. Operations Research, 58(3), 746\u2013755.","journal-title":"Operations Research"},{"key":"751_CR12","doi-asserted-by":"crossref","unstructured":"Liebchen, C., L\u00fcbbecke, M., M\u00f6hring, & Stiller, S. (2009). The Concept of Recoverable Robustness, Linear Programming Recovery, and Railway Applications. In: Robust and online Large-Scale optimization: models and techniques for transportation systems, vol 5868, Springer, 1\u201327.","DOI":"10.1007\/978-3-642-05465-5_1"},{"key":"751_CR13","doi-asserted-by":"crossref","unstructured":"Li, C. L., & Li, F. (2020). Rescheduling production and outbound deliveries when transportation service is disrupted. European Journal of Operational Research, 286(1), 138\u2013148.","DOI":"10.1016\/j.ejor.2020.03.033"},{"key":"751_CR14","unstructured":"Nicosia, G., Pacifici, A., Pferschy, U., Polimeno, E., & Righini, G. (2019) Optimally rescheduling jobs under LIFO constraints. In: Proceedings of the 17th cologne-twente workshop on graphs and combinatorial optimization, pp 107\u2013110"},{"key":"751_CR15","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1007\/s10951-021-00707-5","volume":"24","author":"G Nicosia","year":"2021","unstructured":"Nicosia, G., Pacifici, A., Pferschy, P., Resch, J., & Righini, G. (2021). Optimally rescheduling jobs with a LIFO buffer. Journal of Scheduling, 24, 663\u2013680.","journal-title":"Journal of Scheduling"},{"key":"751_CR16","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.cor.2018.08.007","volume":"101","author":"S Niu","year":"2019","unstructured":"Niu, S., Song, S., Ding, J. Y., Zhang, Y., & Chiong, R. (2019). Distributionally robust single machine scheduling with the total tardiness criterion. Computers & Operations Research, 101, 13\u201328.","journal-title":"Computers & Operations Research"},{"key":"751_CR17","first-page":"461","volume":"762","author":"M Nouiri","year":"2018","unstructured":"Nouiri, M., Bekrar, A., Jemai, A., Ammari, A. C., & Niar, S. (2018). A New Rescheduling Heuristic for Flexible Job Shop Problem with Machine Disruption. Studies in Computational Intelligence, 762, 461\u2013476.","journal-title":"Studies in Computational Intelligence"},{"issue":"4","key":"751_CR18","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s10951-008-0090-8","volume":"12","author":"D Ouelhadj","year":"2009","unstructured":"Ouelhadj, D., & Petrovic, S. (2009). A survey of dynamic scheduling in manufacturing systems. Journal of Scheduling, 12(4), 417\u2013431.","journal-title":"Journal of Scheduling"},{"key":"751_CR19","unstructured":"Polimeno, E. (2019). Optimal rescheduling of jobs under LIFO constraints. Master thesis, University of Milan, Department of Computer Science."},{"key":"751_CR20","doi-asserted-by":"crossref","unstructured":"Potts, C. N., & Van Wassenhove, L. N. (1988). Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs. Management Science, 34(7), 843\u2013858.","DOI":"10.1287\/mnsc.34.7.843"},{"key":"751_CR21","doi-asserted-by":"crossref","unstructured":"Rener, E., Salassa, F., & T\u2019kindt, V,. (2022). Single machine rescheduling for new orders with maximum lateness minimization. Computers & Operations Research,144, 105815.","DOI":"10.1016\/j.cor.2022.105815"},{"issue":"6","key":"751_CR22","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1007\/s10951-018-0559-z","volume":"21","author":"M van den Akker","year":"2018","unstructured":"van den Akker, M., Hoogeveen, H., & Stoef, J. (2018). Combining two-stage stochastic programming and recoverable robustness to minimize the number of late jobs in the case of uncertain processing times. Journal of Scheduling, 21(6), 607\u2013617.","journal-title":"Journal of Scheduling"},{"issue":"1","key":"751_CR23","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1023\/A:1022235519958","volume":"6","author":"GE Vieira","year":"2003","unstructured":"Vieira, G. E., Herrmann, J. W., & Lin, E. (2003). Rescheduling Manufacturing Systems: A Framework of Strategies, Policies, and Methods. Journal of Scheduling, 6(1), 39\u201362.","journal-title":"Journal of Scheduling"},{"key":"751_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-15-3528-4","volume-title":"Rescheduling Under Disruptions in Manufacturing Systems: Models and Algorithms","author":"D Wang","year":"2020","unstructured":"Wang, D., Yin, Y., & Jin, Y. (2020). Rescheduling Under Disruptions in Manufacturing Systems: Models and Algorithms. Uncertainty and Operations Research: Springer."}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00751-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-022-00751-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-00751-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T03:31:52Z","timestamp":1686195112000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-022-00751-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,7]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["751"],"URL":"https:\/\/doi.org\/10.1007\/s10951-022-00751-9","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,7]]},"assertion":[{"value":"1 August 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}