{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:10:45Z","timestamp":1740103845076,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,9,21]],"date-time":"2021-09-21T00:00:00Z","timestamp":1632182400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,21]],"date-time":"2021-09-21T00:00:00Z","timestamp":1632182400000},"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\/501100003407","name":"ministero dell\u2019istruzione","doi-asserted-by":"publisher","award":["AHeAD: efficient Algorithms for HArnessing networked Data"],"award-info":[{"award-number":["AHeAD: efficient Algorithms for HArnessing networked Data"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"dell\u2019universit\u00e0 e della ricerca","doi-asserted-by":"publisher","award":["AHeAD: efficient Algorithms for HArnessing networked Data"],"award-info":[{"award-number":["AHeAD: efficient Algorithms for HArnessing networked Data"]}],"id":[{"id":"10.13039\/501100003407","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":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper considers single-machine scheduling problems in which a given solution, i.e., an ordered set of jobs, has to be improved as much as possible by re-sequencing the jobs. The need for rescheduling may arise in different contexts, e.g., due to changes in the job data or because of the local objective in a stage of a supply chain that is not aligned with the given sequence. A common production setting entails the movement of jobs (or parts) on a conveyor. This is reflected in our model by facilitating the re-sequencing of jobs via a buffer of limited capacity accessible by a LIFO policy. We consider the classical objective functions of total weighted completion time, maximum lateness and (weighted) number of late jobs and study their complexity. For three of these problems, we present strictly polynomial-time dynamic programming algorithms, while for the case of minimizing the weighted number of late jobs NP-hardness is proven and a pseudo-polynomial algorithm is given.<\/jats:p>","DOI":"10.1007\/s10951-021-00707-5","type":"journal-article","created":{"date-parts":[[2021,9,21]],"date-time":"2021-09-21T04:02:32Z","timestamp":1632196952000},"page":"663-680","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Optimally rescheduling jobs with a Last-In-First-Out buffer"],"prefix":"10.1007","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4043-2812","authenticated-orcid":false,"given":"Gaia","family":"Nicosia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6144-0024","authenticated-orcid":false,"given":"Andrea","family":"Pacifici","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8881-1497","authenticated-orcid":false,"given":"Ulrich","family":"Pferschy","sequence":"additional","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":[[2021,9,21]]},"reference":[{"issue":"1","key":"707_CR1","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1023\/A:1014934612090","volume":"107","author":"A Agnetis","year":"2001","unstructured":"Agnetis, A., Detti, P., Meloni, C., & Pacciarelli, D. (2001). Coordination between two stages of a supply chain. Annals of Operations Research, 107(1), 15\u201332.","journal-title":"Annals of Operations Research"},{"issue":"15","key":"707_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"},{"issue":"1","key":"707_CR3","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.ejor.2018.12.048","volume":"276","author":"A Agnetis","year":"2019","unstructured":"Agnetis, A., Chen, B., Nicosia, G., & Pacifici, A. (2019). Price of fairness in two-agent single-machine scheduling problems. European Journal of Operational Research, 276(1), 79\u201387.","journal-title":"European Journal of Operational Research"},{"issue":"6","key":"707_CR4","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"},{"key":"707_CR5","series-title":"AIRO Springer series","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","author":"A Alfieri","year":"2018","unstructured":"Alfieri, A., Nicosia, G., Pacifici, A., & Pferschy, U. (2018a). Constrained job rearrangements on a single machine. AIRO Springer seriesIn P. Daniele & L. Scrimali (Eds.), New trends in emerging complex real life problems (Vol. 1, pp. 33\u201341). Berlin: Springer."},{"key":"707_CR6","unstructured":"Alfieri, A., Nicosia, G., Pacifici, A., & Pferschy, U. (2018b). Single machine scheduling with bounded job rearrangements. In Proceedings of 16th Cologne-Twente workshop on graphs and combinatorial optimization (pp. 124\u2013127)."},{"issue":"1","key":"707_CR7","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"},{"issue":"6","key":"707_CR8","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.","journal-title":"Journal of Scheduling"},{"issue":"2","key":"707_CR9","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1016\/j.ejor.2004.04.011","volume":"165","author":"J Blazewicz","year":"2005","unstructured":"Blazewicz, J., Pesch, E., Sterna, M., & Werner, F. (2005). The two-machine flow-shop problem with weighted late work criterion and common due date. European Journal of Operational Research, 165(2), 408\u2013415.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"707_CR10","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1287\/mnsc.41.2.363","volume":"42","author":"RL Daniels","year":"1995","unstructured":"Daniels, R. L., & Kouvelis, P. (1995). Robust scheduling to hedge against processing time uncertainty in single-stage production. Management Science, 42(2), 363\u2013737.","journal-title":"Management Science"},{"key":"707_CR11","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"},{"issue":"3","key":"707_CR12","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"},{"issue":"4","key":"707_CR13","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":"707_CR14","doi-asserted-by":"publisher","first-page":"1509","DOI":"10.1016\/j.ifacol.2015.06.300","volume":"48","author":"D Ivanov","year":"2015","unstructured":"Ivanov, D., & Sokolov, B. (2015). Coordination of the supply chain schedules with re-scheduling considerations. IFAC-PapersOnLine, 48(3), 1509\u20131514.","journal-title":"IFAC-PapersOnLine"},{"issue":"2","key":"707_CR15","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1287\/opre.1090.0744","volume":"58","author":"JYT Leung","year":"2010","unstructured":"Leung, J. Y. T., Pinedo, M., & Wan, G. (2010). Competitive two-agent scheduling and its applications. Operations Research, 58(2), 458\u2013469.","journal-title":"Operations Research"},{"key":"707_CR16","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10951-020-00672-5","volume":"24","author":"X Li","year":"2021","unstructured":"Li, X., Ventura, J. A., & Bunn, K. A. (2021). A joint order acceptance and scheduling problem with earliness and tardiness penalties considering overtime. Journal of Scheduling, 24, 49\u201368.","journal-title":"Journal of Scheduling"},{"key":"707_CR17","doi-asserted-by":"crossref","unstructured":"Liebchen C, L\u00fcbbecke M, M\u00f6hring R, 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, pp. 1\u201327). Springer.","DOI":"10.1007\/978-3-642-05465-5_1"},{"key":"707_CR18","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":"707_CR19","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":"707_CR20","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":"707_CR21","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"},{"issue":"1","key":"707_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2013.09.017","volume":"235","author":"P Perez-Gonzalez","year":"2014","unstructured":"Perez-Gonzalez, P., & Framinan, J. M. (2014). A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems. European Journal of Operational Research, 235(1), 1\u201316.","journal-title":"European Journal of Operational Research"},{"issue":"7","key":"707_CR23","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1287\/mnsc.34.7.843","volume":"34","author":"CN Potts","year":"1988","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.","journal-title":"Management Science"},{"issue":"1","key":"707_CR24","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"},{"issue":"1","key":"707_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0305-0548(93)90091-V","volume":"20","author":"SD Wu","year":"1993","unstructured":"Wu, S. D., Storer, R. H., & Chang, P. C. (1993). One machine rescheduling heuristics with efficiency and stability as criteria. Computers & Operations Research, 20(1), 1\u201314.","journal-title":"Computers & Operations Research"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00707-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-021-00707-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00707-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,16]],"date-time":"2021-11-16T08:17:34Z","timestamp":1637050654000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-021-00707-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,21]]},"references-count":25,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["707"],"URL":"https:\/\/doi.org\/10.1007\/s10951-021-00707-5","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2021,9,21]]},"assertion":[{"value":"13 August 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2021","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":"Conflict of interest"}}]}}