{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T20:17:02Z","timestamp":1777148222975,"version":"3.51.4"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T00:00:00Z","timestamp":1748476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T00:00:00Z","timestamp":1748476800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["DFG BR 2272\/11-1"],"award-info":[{"award-number":["DFG BR 2272\/11-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"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>We explore lower bounds concerning the makespan of any online scheduling algorithm for the parallel processor scheduling problem with four processors. We prove that any online algorithm exhibits a makespan of at least <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\sqrt{3}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msqrt>\n                    <mml:mn>3<\/mml:mn>\n                  <\/mml:msqrt>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> times that of an optimal offline schedule, minus an additional constant of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$2-\\sqrt{3}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mn>3<\/mml:mn>\n                    <\/mml:msqrt>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, thus yielding an asymptotic competitive ratio of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\sqrt{3}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msqrt>\n                    <mml:mn>3<\/mml:mn>\n                  <\/mml:msqrt>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. Moreover, specific absolute competitive ratios <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\sqrt{3}-\\epsilon _r$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msqrt>\n                      <mml:mn>3<\/mml:mn>\n                    <\/mml:msqrt>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>\u03f5<\/mml:mi>\n                      <mml:mi>r<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, where <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\epsilon _r&gt;0$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>\u03f5<\/mml:mi>\n                      <mml:mi>r<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>&gt;<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> depends on the number of tasks that have to be scheduled, are established for scenarios involving a finite number of tasks.<\/jats:p>","DOI":"10.1007\/s10951-025-00843-2","type":"journal-article","created":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T15:22:55Z","timestamp":1748532175000},"page":"529-544","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Lower bounds for online scheduling on four processors"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5155-3033","authenticated-orcid":false,"given":"O.","family":"Braun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Chung","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R. L.","family":"Graham","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,29]]},"reference":[{"key":"843_CR1","doi-asserted-by":"crossref","unstructured":"Albers, S. (2002). On randomized online scheduling. In Proceedings of 34th Symposium. Theory of Computing (STOC) (pp. 134\u2013143).","DOI":"10.1145\/509907.509930"},{"key":"843_CR2","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1137\/S0097539797324874","volume":"29","author":"S Albers","year":"1999","unstructured":"Albers, S. (1999). Better bounds for online scheduling. SIAM Journal on Computing, 29, 459\u2013473.","journal-title":"SIAM Journal on Computing"},{"key":"843_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2018.11.005","volume":"102","author":"J Balogh","year":"2019","unstructured":"Balogh, J., Bekesi, J., Dosa, G., Sgall, J., & van Stee, R. (2019). The optimal absolute ratio for online bin packing. Journal of Computer and System Sciences, 102, 1\u201317.","journal-title":"Journal of Computer and System Sciences"},{"key":"843_CR4","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1006\/jcss.1995.1074","volume":"51","author":"Y Bartal","year":"1995","unstructured":"Bartal, Y., Fiat, A., Karloff, H., & Vohra, R. (1995). New algorithms for an ancient scheduling problem. Journal of Computer and System Sciences, 51, 359\u2013366.","journal-title":"Journal of Computer and System Sciences"},{"key":"843_CR5","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0020-0190(94)00026-3","volume":"50","author":"Y Bartal","year":"1994","unstructured":"Bartal, Y., Karloff, H., & Rabani, Y. (1994). A better lower bound for on-line scheduling. Information Processing Letters, 50, 113\u2013116.","journal-title":"Information Processing Letters"},{"key":"843_CR6","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s10951-013-0342-0","volume":"17","author":"O Braun","year":"2014","unstructured":"Braun, O., Chung, F., & Graham, R. L. (2014). Single-processor scheduling with time restrictions. Journal of Scheduling, 17, 399\u2013403.","journal-title":"Journal of Scheduling"},{"key":"843_CR7","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/s00291-016-0431-5","volume":"38","author":"O Braun","year":"2016","unstructured":"Braun, O., Chung, F., & Graham, R. L. (2016). Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions. OR Spectrum, 38, 531\u2013540.","journal-title":"OR Spectrum"},{"key":"843_CR8","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0167-6377(94)90071-X","volume":"16","author":"B Chen","year":"1994","unstructured":"Chen, B., Van Vliet, A., & Woeginger, G. J. (1994). New lower and upper bounds for on-line scheduling. Operations Research Letters, 16, 221\u2013230.","journal-title":"Operations Research Letters"},{"key":"843_CR9","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BFb0029568","volume-title":"Online algorithms: The state of the art","author":"J Csirik","year":"1998","unstructured":"Csirik, J., & Woeginger, G. J. (1998). On-line packing and covering problems. In A. Fiat & G. J. Woeginger (Eds.), Online algorithms: The state of the art (pp. 147\u2013177). Springer."},{"key":"843_CR10","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1287\/ijoc.7.2.191","volume":"7","author":"M Dell\u2019Amico","year":"1995","unstructured":"Dell\u2019Amico, M., & Martello, S. (1995). Optimal scheduling of tasks on identical parallel processors. INFORMS Journal on Computing, 7, 191\u2013200.","journal-title":"INFORMS Journal on Computing"},{"key":"843_CR11","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s10951-018-0567-z","volume":"21","author":"L Epstein","year":"2018","unstructured":"Epstein, L. (2018). A survey on makespan minimization in semi-online environments. Journal of Scheduling, 21, 269\u2013284.","journal-title":"Journal of Scheduling"},{"key":"843_CR12","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.dam.2022.07.003","volume":"321","author":"L Epstein","year":"2022","unstructured":"Epstein, L. (2022). Open-end bin packing: New and old analysis approaches. Discrete Applied Mathematics, 321, 220\u2013239.","journal-title":"Discrete Applied Mathematics"},{"key":"843_CR13","first-page":"107","volume":"9","author":"U Faigle","year":"1989","unstructured":"Faigle, U., Kern, W., & Turan, G. (1989). On the performance of on-line algorithms for partition problems. Acta Cybernetica, 9, 107\u2013119.","journal-title":"Acta Cybernetica"},{"key":"843_CR14","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/1099-1425(200011\/12)3:6<343::AID-JOS54>3.0.CO;2-2","volume":"3","author":"R Fleischer","year":"2000","unstructured":"Fleischer, R., & Wahl, M. (2000). Online scheduling revisited. Journal of Scheduling, 3, 343\u2013353.","journal-title":"Journal of Scheduling"},{"key":"843_CR15","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1137\/0222026","volume":"22","author":"G Galambos","year":"1993","unstructured":"Galambos, G., & Woeginger, G. J. (1993). An on-line scheduling heuristic with better worst case ratio than Graham\u2019s list scheduling. SIAM Journal on Computing, 22, 349\u2013355.","journal-title":"SIAM Journal on Computing"},{"key":"843_CR16","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1287\/opre.26.1.3","volume":"26","author":"MR Garey","year":"1978","unstructured":"Garey, M. R., Graham, R. L., & Johnson, D. S. (1978). Performance guarantees for scheduling algorithms. Operations Research, 26, 3\u201321.","journal-title":"Operations Research"},{"key":"843_CR17","unstructured":"Graham, R. L. (2012). Personal communication, noted on a whiteboard in 2012."},{"key":"843_CR18","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. (1966). Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45, 1563\u20131581.","journal-title":"Bell System Technical Journal"},{"key":"843_CR19","unstructured":"Karp, R. M. (1992). On-line algorithms versus off-line algorithms: How much is it worth to know the future? Technical Report ICSI, TR-92-044 (pp. 1\u201312)."},{"key":"843_CR20","volume-title":"Handbook of scheduling algorithms, models, and performance analysis","author":"K Pruhs","year":"2004","unstructured":"Pruhs, K., Sgall, J., & Torng, R. (2004). Online scheduling. In J.Y.-T. Leung (Ed.), Handbook of scheduling algorithms, models, and performance analysis.  (Vol. 15). CRC Press."},{"key":"843_CR21","unstructured":"Rudin III, J. F. (2001). Improved bounds for the on-line scheduling problem, Ph.D. Thesis, The University of Texas at Dallas."},{"key":"843_CR22","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1137\/S0097539702403438","volume":"32","author":"JF Rudin III","year":"2003","unstructured":"Rudin, J. F., III., & Chandrasekaran, R. (2003). Improved bounds for the online scheduling problem. SIAM Journal on Computing, 32, 717\u2013735.","journal-title":"SIAM Journal on Computing"},{"key":"843_CR23","doi-asserted-by":"crossref","unstructured":"Tan, Z., & Li, R. (2015). Pseudo lower bounds for online parallel machine scheduling. Operations Research Letters, 43, 489\u2013494.","DOI":"10.1016\/j.orl.2015.07.002"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-025-00843-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-025-00843-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-025-00843-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T03:51:14Z","timestamp":1759031474000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-025-00843-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,29]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["843"],"URL":"https:\/\/doi.org\/10.1007\/s10951-025-00843-2","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,29]]},"assertion":[{"value":"17 March 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}