{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T04:10:05Z","timestamp":1759032605950,"version":"3.44.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T00:00:00Z","timestamp":1741824000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T00:00:00Z","timestamp":1741824000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Bern"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2025,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Rescheduling problems arise in a variety of situations where a previously planned schedule needs to be adjusted to deal with unforeseen events. A common problem is the arrival of new orders, i.e., jobs, which have to be integrated into the schedule of the so-called old jobs. The maximum and total absolute time deviations of the completion times of these jobs are modeled as a disruption constraint to limit the change in the original schedule. Disruption constraints influence the shape of an optimal schedule in particular with respect to the sequencing of old jobs and the insertion of idle time. In this paper, a classification into idle and no-idle problems is given, through several examples, for a set of single machine rescheduling problems with different objective functions. We also prove the complexity of four rescheduling problems that have been left open in the literature. Finally, algorithms are provided to solve the timing problem that arises for certain single machine rescheduling problems when the order of the jobs is fixed.<\/jats:p>","DOI":"10.1007\/s10951-025-00837-0","type":"journal-article","created":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T17:09:46Z","timestamp":1741885786000},"page":"469-482","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Single machine rescheduling for new orders with maximum and total time disruption constraints"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2371-8360","authenticated-orcid":false,"given":"Elena","family":"Rener","sequence":"first","affiliation":[]},{"given":"Fabio","family":"Salassa","sequence":"additional","affiliation":[]},{"given":"Vincent","family":"T\u2019kindt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,13]]},"reference":[{"issue":"1","key":"837_CR1","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ejor.2003.08.027","volume":"161","author":"H Aytug","year":"2005","unstructured":"Aytug, H., Lawley, M. A., McKay, K., et al. (2005). Executing production schedules in the face of uncertainties: A review and some future directions. European Journal of Operational Research, 161(1), 86\u2013110. https:\/\/doi.org\/10.1016\/j.ejor.2003.08.027","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"837_CR2","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/S0304-3975(01)00220-1","volume":"292","author":"P Chr\u00e9tienne","year":"2003","unstructured":"Chr\u00e9tienne, P., & Sourd, F. (2003). PERT scheduling with convex cost functions. Theoretical Computer Science, 292(1), 145\u2013164. https:\/\/doi.org\/10.1016\/S0304-3975(01)00220-1","journal-title":"Theoretical Computer Science"},{"key":"837_CR3","doi-asserted-by":"publisher","DOI":"10.1080\/01605682.2023.2197000","author":"K Fang","year":"2023","unstructured":"Fang, K., Luo, W., Pinedo, M. L., et al. (2023). Rescheduling for new orders on a single machine with rejection. Journal of the Operational Research Society. https:\/\/doi.org\/10.1080\/01605682.2023.2197000","journal-title":"Journal of the Operational Research Society"},{"issue":"2","key":"837_CR4","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(2), 330\u2013348. https:\/\/doi.org\/10.1287\/moor.13.2.330","journal-title":"Mathematics of Operations Research"},{"key":"837_CR5","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R Graham","year":"1979","unstructured":"Graham, R., Lawler, E., Lenstra, J., et al. (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"},{"key":"837_CR6","doi-asserted-by":"publisher","first-page":"1205","DOI":"10.1109\/ACCESS.2019.2957132","volume":"9","author":"Y Guo","year":"2021","unstructured":"Guo, Y., Huang, M., Wang, Q., et al. (2021). Single-machine rework rescheduling to minimize total waiting time with fixed sequence of jobs and release times. IEEE Access, 9, 1205\u20131218. https:\/\/doi.org\/10.1109\/ACCESS.2019.2957132","journal-title":"IEEE Access"},{"issue":"3","key":"837_CR7","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. (2004). Rescheduling for new orders. Operations Research, 52(3), 440\u2013453. https:\/\/doi.org\/10.1287\/opre.1030.0101","journal-title":"Operations Research"},{"issue":"4","key":"837_CR8","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1287\/ijoc.1060.0209","volume":"19","author":"N Hall","year":"2007","unstructured":"Hall, N., Liu, Z., & Potts, C. (2007). Rescheduling for multiple new orders. INFORMS Journal on Computing, 19(4), 633\u2013645. https:\/\/doi.org\/10.1287\/ijoc.1060.0209","journal-title":"INFORMS Journal on Computing"},{"key":"837_CR9","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2023.0038","author":"S Lendl","year":"2024","unstructured":"Lendl, S., Pferschy, U., & Rener, E. (2024). Rescheduling with new orders under bounded disruption. INFORMS Journal on Computing. https:\/\/doi.org\/10.1287\/ijoc.2023.0038","journal-title":"INFORMS Journal on Computing"},{"issue":"14","key":"837_CR10","doi-asserted-by":"publisher","first-page":"2640","DOI":"10.1080\/00207721.2013.876519","volume":"46","author":"L Liu","year":"2015","unstructured":"Liu, L., & Zhou, H. (2015). single-machine rescheduling with deterioration and learning effects against the maximum sequence disruption. International Journal of Systems Science, 46(14), 2640\u20132658. https:\/\/doi.org\/10.1080\/00207721.2013.876519","journal-title":"International Journal of Systems Science"},{"issue":"1","key":"837_CR11","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.ejor.2017.09.015","volume":"266","author":"Z Liu","year":"2018","unstructured":"Liu, Z., Lu, L., & Qi, X. (2018). Cost allocation in rescheduling with machine unavailable period. European Journal of Operational Research, 266(1), 16\u201328. https:\/\/doi.org\/10.1016\/j.ejor.2017.09.015","journal-title":"European Journal of Operational Research"},{"key":"837_CR12","doi-asserted-by":"publisher","unstructured":"Luo, W., Chin, R., Cai, A., et al. (2022). A tardiness-augmented approximation scheme for rejection-allowed multiprocessor rescheduling. Journal of Combinatorial Optimization, 44, 690\u2013722. https:\/\/doi.org\/10.1007\/s10878-022-00857-y","DOI":"10.1007\/s10878-022-00857-y"},{"key":"837_CR13","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/s10951-022-00751-9","volume":"26","author":"U Pferschy","year":"2023","unstructured":"Pferschy, U., Resch, J., & Righini, G. (2023). Algorithms for rescheduling jobs with a LIFO buffer to minimize the weighted number of late jobs. Journal of Scheduling, 26, 267\u2013287. https:\/\/doi.org\/10.1007\/s10951-022-00751-9","journal-title":"Journal of Scheduling"},{"key":"837_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2022.105815","volume":"144","author":"E Rener","year":"2022","unstructured":"Rener, E., Salassa, F., & T\u2019kindt, V. (2022). Single machine rescheduling for new orders with maximum lateness minimization. Computers & Operations Research, 144, 105815. https:\/\/doi.org\/10.1016\/j.cor.2022.105815","journal-title":"Computers & Operations Research"},{"key":"837_CR15","doi-asserted-by":"publisher","unstructured":"Teghem, J., & Tuyttens, D. (2014). A bi-objective approach to reschedule new jobs in a one machine model. International Transactions in Operational Research, 21(6), 871\u2013898. https:\/\/doi.org\/10.1111\/itor.12066","DOI":"10.1111\/itor.12066"},{"issue":"2","key":"837_CR16","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1002\/net.21587","volume":"65","author":"T Vidal","year":"2015","unstructured":"Vidal, T., Crainic, T. G., Gendreau, M., et al. (2015). Timing problems and algorithms: Time decisions for sequences of activities. Networks, 65(2), 102\u2013128. https:\/\/doi.org\/10.1002\/net.21587","journal-title":"Networks"},{"issue":"1","key":"837_CR17","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1023\/A:1022235519958","volume":"6","author":"G Vieira","year":"2003","unstructured":"Vieira, G., Herrmann, J., & Lin, E. (2003). Rescheduling manufacturing systems: A framework of strategies, policies, and methods. Journal of Scheduling, 6(1), 39\u201362. https:\/\/doi.org\/10.1023\/A:1022235519958","journal-title":"Journal of Scheduling"},{"key":"837_CR18","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1016\/j.omega.2018.04.008","volume":"81","author":"D Wang","year":"2018","unstructured":"Wang, D., Yin, Y., & Cheng, T. (2018). Parallel-machine rescheduling with job unavailability and rejection. Omega, 81, 246\u2013260. https:\/\/doi.org\/10.1016\/j.omega.2018.04.008","journal-title":"Omega"},{"key":"837_CR19","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/s00170-006-0590-7","volume":"34","author":"B Yang","year":"2007","unstructured":"Yang, B. (2007). Single machine rescheduling with new jobs arrivals and processing time compression. International Journal of Advanced Manufacturing Technologies, 34, 378\u2013384. https:\/\/doi.org\/10.1007\/s00170-006-0590-7","journal-title":"International Journal of Advanced Manufacturing Technologies"},{"issue":"2","key":"837_CR20","doi-asserted-by":"publisher","first-page":"936","DOI":"10.1016\/j.ejor.2006.07.026","volume":"182","author":"J Yuan","year":"2007","unstructured":"Yuan, J., & Mu, Y. (2007). Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption. European Journal of Operational Research, 182(2), 936\u2013944. https:\/\/doi.org\/10.1016\/j.ejor.2006.07.026","journal-title":"European Journal of Operational Research"},{"issue":"6","key":"837_CR21","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1142\/S021759590700153X","volume":"24","author":"J Yuan","year":"2007","unstructured":"Yuan, J., Mu, Y., Lu, L., et al. (2007). Rescheduling with release dates to minimize total sequence disruption under a limit on the makespan. European Journal of Operational Research, 24(6), 789\u2013796. https:\/\/doi.org\/10.1142\/S021759590700153X","journal-title":"European Journal of Operational Research"},{"key":"837_CR22","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1007\/s10878-021-00803-4","volume":"43","author":"X Zhang","year":"2022","unstructured":"Zhang, X., Lin, W. C., & Wu, C. C. (2022). Rescheduling problems with allowing for the unexpected new jobs arrival. Journal of Combinatorial Optimization, 43, 630\u2013645. https:\/\/doi.org\/10.1007\/s10878-021-00803-4","journal-title":"Journal of Combinatorial Optimization"},{"issue":"1","key":"837_CR23","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/j.apm.2009.03.037","volume":"34","author":"C Zhao","year":"2010","unstructured":"Zhao, C., & Tang, H. (2010). Rescheduling problems with deteriorating jobs under disruptions. Applied Mathematical Modelling, 34(1), 238\u2013243. https:\/\/doi.org\/10.1016\/j.apm.2009.03.037","journal-title":"Applied Mathematical Modelling"},{"key":"837_CR24","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s10288-016-0308-0","volume":"14","author":"Q Zhao","year":"2016","unstructured":"Zhao, Q., Lu, L., & Yuan, J. (2016). Rescheduling with new orders and general maximum allowable time disruptions. 4OR, 14, 261\u2013280. https:\/\/doi.org\/10.1007\/s10288-016-0308-0","journal-title":"4OR"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-025-00837-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-025-00837-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-025-00837-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T03:51:10Z","timestamp":1759031470000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-025-00837-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,13]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["837"],"URL":"https:\/\/doi.org\/10.1007\/s10951-025-00837-0","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2025,3,13]]},"assertion":[{"value":"12 January 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2025","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 have no conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}