{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:59:11Z","timestamp":1780783151201,"version":"3.54.1"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032277312","type":"print"},{"value":"9783032277329","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-27732-9_4","type":"book-chapter","created":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:55Z","timestamp":1780780495000},"page":"45-59","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Minimizing the\u00a0Weighted Makespan with\u00a0Restarts on\u00a0a\u00a0Single Machine"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-6912-3344","authenticated-orcid":false,"given":"Aflatoun","family":"Amouzandeh","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8358-6796","authenticated-orcid":false,"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-4984-3696","authenticated-orcid":false,"given":"Lis","family":"Pirotton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3664-0865","authenticated-orcid":false,"given":"Rob","family":"van Stee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-4820-9017","authenticated-orcid":false,"given":"Corinna","family":"Wambsganz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,7]]},"reference":[{"key":"4_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/3-540-45253-2_39","volume-title":"Algorithms - ESA 2000","author":"M van den Akker","year":"2000","unstructured":"van den Akker, M., Hoogeveen, H., Vakhania, N.: Restarts can help in the on-line minimization of the maximum delivery time on a single machine. In: Paterson, M.S. (ed.) ESA 2000. LNCS, vol. 1879, pp. 427\u2013436. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-45253-2_39"},{"key":"4_CR2","doi-asserted-by":"publisher","unstructured":"Amouzandeh, A., van Stee, R.: Improved online scheduling with restarts on a single machine. In: Bie\u0144kowski, M., Englert, M. (eds.) Approximation and Online Algorithms. WAOA 2024. LNCS, vol. 15269. Springer, Cham (2025). https:\/\/doi.org\/10.1007\/978-3-031-81396-2_2","DOI":"10.1007\/978-3-031-81396-2_2"},{"key":"4_CR3","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis, Cambridge University Press (1998)"},{"key":"4_CR4","doi-asserted-by":"publisher","unstructured":"Chai, X., Lu, L., Li, W., Zhang, L.: Best-possible online algorithms for single machine scheduling to minimize the maximum weighted completion time. Asia Pac. J. Oper. Res. 35(6), 1850048:1\u20131850048:11 (2018). https:\/\/doi.org\/10.1142\/S0217595918500483","DOI":"10.1142\/S0217595918500483"},{"issue":"4","key":"4_CR5","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0167-6377(97)00040-0","volume":"21","author":"B Chen","year":"1997","unstructured":"Chen, B., Vestjens, A.: Scheduling on identical machines: How good is LPT in an on-line setting? Oper. Res. Lett. 21(4), 165\u2013169 (1997). https:\/\/doi.org\/10.1016\/S0167-6377(97)00040-0","journal-title":"Oper. Res. Lett."},{"issue":"6","key":"4_CR6","doi-asserted-by":"publisher","first-page":"1709","DOI":"10.1137\/S0097539704446608","volume":"36","author":"M Chrobak","year":"2007","unstructured":"Chrobak, M., Jawor, W., Sgall, J., Tich\u00fd, T.: Online scheduling of equal-length jobs: randomization and restarts help. SIAM J. Comput. 36(6), 1709\u20131728 (2007). https:\/\/doi.org\/10.1137\/S0097539704446608","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"4_CR7","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/S0304-3975(02)00488-7","volume":"299","author":"L Epstein","year":"2003","unstructured":"Epstein, L., van Stee, R.: Lower bounds for on-line single-machine scheduling. Theor. Comput. Sci. 299(1\u20133), 439\u2013450 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(02)00488-7","journal-title":"Theor. Comput. Sci."},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029561","volume-title":"Online Algorithms: The State of the Art","year":"1998","unstructured":"Fiat, A., Woeginger, G.J. (eds.): Online Algorithms: The State of the Art. LNCS, vol. 1442. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0029561"},{"issue":"11","key":"4_CR9","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1016\/j.ipl.2010.04.008","volume":"110","author":"R Fu","year":"2010","unstructured":"Fu, R., Cheng, T.C.E., Ng, C.T., Yuan, J.: Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan. Inf. Process. Lett. 110(11), 444\u2013450 (2010). https:\/\/doi.org\/10.1016\/j.ipl.2010.04.008","journal-title":"Inf. Process. Lett."},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287\u2013326 (1979)","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"4_CR11","doi-asserted-by":"publisher","unstructured":"Komm, D.: An Introduction to Online Computation - Determinism, Randomization, Advice. Texts in Theoretical Computer Science. An EATCS Series. Springer (2016). https:\/\/doi.org\/10.1007\/978-3-319-42749-2","DOI":"10.1007\/978-3-319-42749-2"},{"issue":"1","key":"4_CR12","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/S10479-024-06386-7","volume":"351","author":"Y Laalaoui","year":"2025","unstructured":"Laalaoui, Y., M\u2019Hallah, R.: Enhancing the best-first-search F with incremental search and restarts for large-scale single machine scheduling with release dates and deadlines. Ann. Oper. Res. 351(1), 303\u2013332 (2025). https:\/\/doi.org\/10.1007\/S10479-024-06386-7","journal-title":"Ann. Oper. Res."},{"key":"4_CR13","doi-asserted-by":"publisher","unstructured":"Li, W.: A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completion time. Asia Pac. J. Oper. Res. 32(4), 1550030:1\u20131550030:10 (2015). https:\/\/doi.org\/10.1142\/S021759591550030X","DOI":"10.1142\/S021759591550030X"},{"issue":"1","key":"4_CR14","doi-asserted-by":"publisher","first-page":"2518","DOI":"10.3934\/math.2024124","volume":"9","author":"X Liang","year":"2024","unstructured":"Liang, X., Lu, L., Sun, X., Yu, X., Zuo, L.: Online scheduling on a single machine with one restart for all jobs to minimize the weighted makespan. AIMS Math. 9(1), 2518\u20132529 (2024)","journal-title":"AIMS Math."},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Liu, H.L., Lu, X.W.: Online scheduling on a parallel batch machine with delivery times and limited restarts. J. Operat. Res. Soc. China, 1\u201319 (2022)","DOI":"10.1007\/s40305-021-00356-7"},{"key":"4_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-030-93176-6_9","volume-title":"Algorithmic Aspects in Information and Management","author":"L Lu","year":"2021","unstructured":"Lu, L., Zhang, L., Ou, J.: Single machine scheduling with\u00a0rejection to\u00a0minimize the\u00a0weighted makespan. In: Wu, W., Du, H. (eds.) AAIM 2021. LNCS, vol. 13153, pp. 96\u2013110. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-93176-6_9"},{"key":"4_CR17","unstructured":"Qi, F., Jinjiang, Y.: Np-hardness of a multicriteria scheduling on two families of jobs. Operat. Res. Trans., 121\u2013126 (2007)"},{"key":"4_CR18","doi-asserted-by":"publisher","unstructured":"Shmoys, D.B., Wein, J., Williamson, D.P.: Scheduling parallel machines on-line. In: McGeoch, L.A., Sleator, D.D. (eds.) DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 7, pp. 163\u2013166. DIMACS\/AMS (1991). https:\/\/doi.org\/10.1090\/DIMACS\/007\/13","DOI":"10.1090\/DIMACS\/007\/13"},{"issue":"2","key":"4_CR19","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/J.JALGOR.2004.10.001","volume":"57","author":"R van Stee","year":"2005","unstructured":"van Stee, R., Poutr\u00e9, J.A.L.: Minimizing the total completion time on-line on a single machine, using restarts. J. Algorithms 57(2), 95\u2013129 (2005). https:\/\/doi.org\/10.1016\/J.JALGOR.2004.10.001","journal-title":"J. Algorithms"},{"issue":"3","key":"4_CR20","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/s10878-024-01118-w","volume":"47","author":"R Sun","year":"2024","unstructured":"Sun, R.: Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines. J. Comb. Optim. 47(3), 34 (2024). https:\/\/doi.org\/10.1007\/s10878-024-01118-w","journal-title":"J. Comb. Optim."},{"issue":"4","key":"4_CR21","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s40305-014-0060-0","volume":"2","author":"J Tian","year":"2014","unstructured":"Tian, J., Fu, R., Yuan, J.: Online over time scheduling on parallel-batch machines: a survey. J. Operat. Res. Soc. China 2(4), 445\u2013454 (2014)","journal-title":"J. Operat. Res. Soc. China"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-27732-9_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:57Z","timestamp":1780780497000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-27732-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032277312","9783032277329"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-27732-9_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"7 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Clermont-Ferrand","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2026.limos.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}