{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T09:39:12Z","timestamp":1776764352145,"version":"3.51.2"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T00:00:00Z","timestamp":1771200000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T00:00:00Z","timestamp":1771200000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100018222","name":"Universit\u00e4t Siegen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100018222","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We consider the problem of minimizing the total completion time on a single online machine using restarts. Although restarts can potentially be very beneficial in the context of online scheduling, there has been relatively little research on this topic up until now. We present a very simple online algorithm which is better than 1.4568-competitive. The basic rule of the algorithm is to run jobs in order of increasing size. For possible restarts, the algorithm only considers whether the completion time of an incoming job is more than a factor of 1.4568 higher if we first let the running job finish compared to the case where we start the new job immediately. If this is the case, we interrupt the running job and start running the new job. All other existing or past jobs are ignored for this decision. The analysis of the algorithm has become significantly easier and shorter than for the previous best result which was 3\/2. We hope that this result can lead to further research in this interesting topic.<\/jats:p>","DOI":"10.1007\/s00224-026-10267-w","type":"journal-article","created":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T15:38:56Z","timestamp":1771256336000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improved Online Scheduling with Restarts on a Single Machine"],"prefix":"10.1007","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-6912-3344","authenticated-orcid":false,"given":"Aflatoun","family":"Amouzandeh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3664-0865","authenticated-orcid":false,"given":"Rob","family":"van Stee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,16]]},"reference":[{"issue":"3","key":"10267_CR1","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1287\/MOOR.1040.0092","volume":"29","author":"EJ Anderson","year":"2004","unstructured":"Anderson, E.J., Potts, C.N.: Online scheduling of a single machine to minimize total weighted completion time. Math. Oper. Res. 29(3), 686\u2013697 (2004). https:\/\/doi.org\/10.1287\/MOOR.1040.0092","journal-title":"Math. Oper. Res."},{"key":"10267_CR2","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press (1998)"},{"key":"10267_CR3","unstructured":"Chekuri, C., Motwani, R., Natarajan, B., Stein, C.: Approximation techniques for average completion time scheduling. In: Saks, M.E. (ed.) Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5\u20137 January 1997, New Orleans, Louisiana, USA. pp. 609\u2013618. ACM\/SIAM (1997). http:\/\/dl.acm.org\/citation.cfm?id=314161.314396"},{"issue":"1\u20133","key":"10267_CR4","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":"10267_CR5","doi-asserted-by":"crossref","unstructured":"Fiat, A., Woeginger, G.J.: Online algorithms: The state of the art, vol. 1442. Springer (1998)","DOI":"10.1007\/BFb0029561"},{"issue":"2","key":"10267_CR6","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1137\/S089548019936223X","volume":"15","author":"MX Goemans","year":"2002","unstructured":"Goemans, M.X., Queyranne, M., Schulz, A.S., Skutella, M., Wang, Y.: Single machine scheduling with release dates. SIAM J. Discret. Math. 15(2), 165\u2013192 (2002). https:\/\/doi.org\/10.1137\/S089548019936223X","journal-title":"SIAM J. Discret. Math."},{"issue":"9","key":"10267_CR7","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"issue":"3","key":"10267_CR8","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/MOOR.22.3.513","volume":"22","author":"LA Hall","year":"1997","unstructured":"Hall, L.A., Schulz, A.S., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. 22(3), 513\u2013544 (1997). https:\/\/doi.org\/10.1287\/MOOR.22.3.513","journal-title":"Math. Oper. Res."},{"key":"10267_CR9","doi-asserted-by":"publisher","unstructured":"Hoogeveen, H., Vestjens, A.P.A.: Optimal on-line algorithms for single-machine scheduling. In: Cunningham, W.H., McCormick, S.T., Queyranne, M. (eds.) Integer Programming and Combinatorial Optimization, 5th International IPCO Conference, Vancouver, British Columbia, Canada, June 3\u20135, 1996, Proceedings. Lecture Notes in Computer Science, vol. 1084, pp. 404\u2013414. Springer (1996). https:\/\/doi.org\/10.1007\/3-540-61310-2_30","DOI":"10.1007\/3-540-61310-2_30"},{"key":"10267_CR10","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"},{"key":"10267_CR11","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1016\/J.AMC.2015.10.058","volume":"273","author":"R Ma","year":"2016","unstructured":"Ma, R., Tao, J., Yuan, J.: Online scheduling with linear deteriorating jobs to minimize the total weighted completion time. Appl. Math. Comput. 273, 570\u2013583 (2016). https:\/\/doi.org\/10.1016\/J.AMC.2015.10.058","journal-title":"Appl. Math. Comput."},{"key":"10267_CR12","doi-asserted-by":"crossref","unstructured":"Phillips, C., Stein, C., Wein, J.: Scheduling jobs that arrive over time. In: Algorithms and Data Structures: 4th International Workshop, WADS\u201995 Kingston, Canada, August 16\u201318, 1995 Proceedings 4. pp. 86\u201397. Springer (1995)","DOI":"10.1007\/3-540-60220-8_53"},{"key":"10267_CR13","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.) On-Line Algorithms, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, February 11\u201313, 1991. 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":"10267_CR14","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., La Poutr\u00e9, H.: Minimizing the total completion time on-line on a single machine, using restarts. J. Algorithms 57(2), 95\u2013129 (2005)","journal-title":"J. Algorithms"},{"issue":"8\u20139","key":"10267_CR15","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/J.IPL.2010.02.013","volume":"110","author":"J Tao","year":"2010","unstructured":"Tao, J., Chao, Z., Xi, Y., Tao, Y.: An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time. Inf. Process. Lett. 110(8\u20139), 325\u2013330 (2010). https:\/\/doi.org\/10.1016\/J.IPL.2010.02.013","journal-title":"Inf. Process. Lett."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10267-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-026-10267-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10267-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T08:42:22Z","timestamp":1776760942000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-026-10267-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,16]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10267"],"URL":"https:\/\/doi.org\/10.1007\/s00224-026-10267-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,16]]},"assertion":[{"value":"13 March 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2026","order":3,"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 no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"10"}}