{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:36:25Z","timestamp":1759667785440,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,4,5]],"date-time":"2018-04-05T00:00:00Z","timestamp":1522886400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"NKFIH","award":["SNN 116095","SNN 116095"],"award-info":[{"award-number":["SNN 116095","SNN 116095"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11671356","11271324"],"award-info":[{"award-number":["11671356","11271324"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11471286"],"award-info":[{"award-number":["11471286"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004895","name":"European Social Fund","doi-asserted-by":"publisher","award":["n\/a"],"award-info":[{"award-number":["n\/a"]}],"id":[{"id":"10.13039\/501100004895","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Szechenyi 2020","award":["EFOP-3.6.1-16-2016-00015"],"award-info":[{"award-number":["EFOP-3.6.1-16-2016-00015"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cent Eur J Oper Res"],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1007\/s10100-018-0536-9","type":"journal-article","created":{"date-parts":[[2018,4,5]],"date-time":"2018-04-05T03:00:39Z","timestamp":1522897239000},"page":"1107-1130","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Tight lower bounds for semi-online scheduling on two uniform machines with known optimum"],"prefix":"10.1007","volume":"27","author":[{"given":"Gy\u00f6rgy","family":"D\u00f3sa","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3637-4066","authenticated-orcid":false,"given":"Armin","family":"F\u00fcgenschuh","sequence":"additional","affiliation":[]},{"given":"Zhiyi","family":"Tan","sequence":"additional","affiliation":[]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[]},{"given":"Krzysztof","family":"W\u0119sek","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,4,5]]},"reference":[{"key":"536_CR1","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 of Computing 29:459\u2013473","journal-title":"SIAM Journal of Computing"},{"key":"536_CR2","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s10951-007-0023-y","volume":"10","author":"E Angelelli","year":"2007","unstructured":"Angelelli E, Speranza MG, Tuza Z (2007) Semi online scheduling on three processors with known sum of the tasks. J Sched 10:263\u2013269","journal-title":"J Sched"},{"key":"536_CR3","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.tcs.2007.12.005","volume":"393","author":"E Angelelli","year":"2008","unstructured":"Angelelli E, Speranza MG, Tuza Z (2008) Semi-online scheduling on two uniform processors. Theoret Comput Sci 393:211\u2013219","journal-title":"Theoret Comput Sci"},{"issue":"1","key":"536_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0304-3975(00)00258-9","volume":"268","author":"Y Azar","year":"2001","unstructured":"Azar Y, Regev O (2001) Online bin-stretching. Theoret Comput Sci 268(1):17\u201341","journal-title":"Theoret Comput Sci"},{"key":"536_CR5","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1006\/jagm.1999.1070","volume":"35","author":"P Berman","year":"2000","unstructured":"Berman P, Charikar M, Karpinski M (2000) On-line load balancing for related machines. Journal of Algorithms 35:108\u2013121","journal-title":"Journal of Algorithms"},{"key":"536_CR6","doi-asserted-by":"crossref","unstructured":"B\u00f6hm M, Sgall J, van Stee R, Vesel\u00fd P (2015) Better algorithms for online bin stretching. In: Proceeding of the 12th international workshop on approximation and online algorithms, (Lecture notes in computer science), vol 8952. Springer, New York, pp 23\u201334","DOI":"10.1007\/978-3-319-18263-6_3"},{"issue":"3","key":"536_CR7","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1007\/s10878-017-0114-4","volume":"34","author":"M B\u00f6hm","year":"2017","unstructured":"B\u00f6hm M, Sgall J, van Stee R, Vesel\u00fd P (2017) A two-phase algorithm for bin stretching with stretching factor 1.5. J Comb Optim 34(3):810\u2013828","journal-title":"J Comb Optim"},{"key":"536_CR8","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/s10951-016-0504-y","volume":"20","author":"M B\u00f6hm","year":"2017","unstructured":"B\u00f6hm M, Sgall J, van Stee R, Vesel\u00fd P (2017) Online bin stretching with three bins. J Sched 20:601\u2013621","journal-title":"J Sched"},{"key":"536_CR9","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.tcs.2004.11.018","volume":"337","author":"TCE Cheng","year":"2005","unstructured":"Cheng TCE, Kellerer H, Kotov V (2005) Semi-on-line multi-processor scheduling with given total processing time. Theor Comput Sci 337:134\u2013146","journal-title":"Theor Comput Sci"},{"issue":"1","key":"536_CR10","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s10100-017-0481-z","volume":"26","author":"G D\u00f3sa","year":"2018","unstructured":"D\u00f3sa G, F\u00fcgenschuh A, Tan Z, Tuza Z, W\u0119sek K (2018) Tight upper bounds for semi-online scheduling on two uniform machines with known optimum. CEJOR 26(1):161\u2013180","journal-title":"CEJOR"},{"key":"536_CR11","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1007\/s10878-009-9265-2","volume":"21","author":"G D\u00f3sa","year":"2011","unstructured":"D\u00f3sa G, Speranza MG, Tuza Z (2011) Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling. J Comb Optim 21:458\u2013480","journal-title":"J Comb Optim"},{"issue":"1","key":"536_CR12","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s00224-013-9451-6","volume":"56","author":"T Ebenlendr","year":"2015","unstructured":"Ebenlendr T, Sgall J (2015) A lower bound on deterministic online algorithms for scheduling on related machines without preemption. Theory Comput Syst 56(1):73\u201381","journal-title":"Theory Comput Syst"},{"key":"536_CR13","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s00236-002-0102-7","volume":"39","author":"L Epstein","year":"2003","unstructured":"Epstein L (2003) Bin stretching revisited. Acta Inform. 39:97\u2013117","journal-title":"Acta Inform."},{"key":"536_CR14","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1002\/jos.60","volume":"4","author":"L Epstein","year":"2001","unstructured":"Epstein L, Noga J, Seiden S, Sgall J, Woeginger GJ (2001) Randomized on-line scheduling on two uniform machines. J Sched 4:71\u201392","journal-title":"J Sched"},{"key":"536_CR15","first-page":"107","volume":"9","author":"U Faigle","year":"1989","unstructured":"Faigle U, Kern W, Tur\u00e1n G (1989) On the performance of on-line algorithm for particular problem. Acta Cybern. 9:107\u2013119","journal-title":"Acta Cybern."},{"key":"536_CR16","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. J Sched 3:343\u2013353","journal-title":"J Sched"},{"key":"536_CR17","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.tcs.2015.07.065","volume":"602","author":"M Gabay","year":"2015","unstructured":"Gabay M, Kotov V, Brauner N (2015) Online bin stretching with bunch techniques. Theoret Comput Sci 602:103\u2013113","journal-title":"Theoret Comput Sci"},{"key":"536_CR18","unstructured":"Gormley T, Reingold N, Torng E, Westbrook J (2000) Generating adversaries for request-answer games. In: Proceeding of the 11th ACM-SIAM symposium on discrete algorithms. Society for industrial and applied mathematics ACM, New York"},{"key":"536_CR19","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 RL (1966) Bounds for certain multiprocessing anomalies. Bell Syst Tech J 45:1563\u20131581","journal-title":"Bell Syst Tech J"},{"issue":"4","key":"536_CR20","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/j.orl.2013.03.005","volume":"41","author":"H Kellerer","year":"2013","unstructured":"Kellerer H, Kotov V (2013) An efficient algorithm for bin stretching. Oper Res Lett 41(4):343\u2013346","journal-title":"Oper Res Lett"},{"issue":"6","key":"536_CR21","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s10951-015-0430-4","volume":"18","author":"H Kellerer","year":"2015","unstructured":"Kellerer H, Kotov V, Gabay M (2015) An efficient algorithm for semi-online multiprocessor scheduling with given total processing time. J Sched 18(6):623\u2013630","journal-title":"J Sched"},{"key":"536_CR22","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/S0167-6377(98)00005-4","volume":"21","author":"H Kellerer","year":"1997","unstructured":"Kellerer H, Kotov V, Speranza MG, Tuza Z (1997) Semi on-line algorithms for the partition problem. Oper Res Lett 21:235\u2013242","journal-title":"Oper Res Lett"},{"key":"536_CR23","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s10951-013-0329-x","volume":"16","author":"K Lee","year":"2013","unstructured":"Lee K, Lim K (2013) Semi-online scheduling problems on a small number of machines. J Sched 16:461\u2013477","journal-title":"J Sched"},{"issue":"8\u201310","key":"536_CR24","doi-asserted-by":"publisher","first-page":"776","DOI":"10.1016\/j.tcs.2008.11.018","volume":"410","author":"CT Ng","year":"2009","unstructured":"Ng CT, Tan Z, He Y, Cheng TCE (2009) Two semi-online scheduling problems on two uniform machines. Theoret Comput Sci 410(8\u201310):776\u2013792","journal-title":"Theoret Comput Sci"},{"key":"536_CR25","volume-title":"Handbook of combinatorial optimization","author":"Z Tan","year":"2013","unstructured":"Tan Z, Zhang A (2013) Online and semi-online scheduling. In: Pardalos PM et al (eds) Handbook of combinatorial optimization. Springer, New York"}],"container-title":["Central European Journal of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-018-0536-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10100-018-0536-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-018-0536-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T07:37:09Z","timestamp":1569397029000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10100-018-0536-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,5]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["536"],"URL":"https:\/\/doi.org\/10.1007\/s10100-018-0536-9","relation":{},"ISSN":["1435-246X","1613-9178"],"issn-type":[{"type":"print","value":"1435-246X"},{"type":"electronic","value":"1613-9178"}],"subject":[],"published":{"date-parts":[[2018,4,5]]},"assertion":[{"value":"5 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}