{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:49:14Z","timestamp":1778496554775,"version":"3.51.4"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2013,10]]},"DOI":"10.1007\/s10951-012-0288-7","type":"journal-article","created":{"date-parts":[[2012,9,11]],"date-time":"2012-09-11T22:48:11Z","timestamp":1347403691000},"page":"539-547","source":"Crossref","is-referenced-by-count":7,"title":["Lower bounds for online makespan minimization on a small number of related machines"],"prefix":"10.1007","volume":"16","author":[{"given":"\u0141ukasz","family":"Je\u017c","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jarett","family":"Schwartz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ji\u0159\u00ed","family":"Sgall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f3zsef","family":"B\u00e9k\u00e9si","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,9,12]]},"reference":[{"key":"288_CR1","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J. Aspnes","year":"1997","unstructured":"Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., & Waarts, O. (1997). On-line load balancing with applications to machine scheduling and virtual circuit routing. Journal of\u00a0the ACM, 44, 486\u2013504.","journal-title":"Journal of\u00a0the ACM"},{"key":"288_CR2","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1007\/BFb0029569","volume-title":"Online algorithms: the state of\u00a0the art","author":"Y. Azar","year":"1998","unstructured":"Azar, Y. (1998). On-line load balancing. In A. Fiat & G. J. Woeginger (Eds.), Online algorithms: the state of\u00a0the art (pp. 178\u2013195). Berlin: Springer."},{"key":"288_CR3","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1002\/1099-1425(200009\/10)3:5<259::AID-JOS47>3.0.CO;2-3","volume":"3","author":"A. Bar-Noy","year":"2000","unstructured":"Bar-Noy, A., Freund, A., & Naor, J. (2000). New algorithms for related machines with temporary jobs. Journal of\u00a0Scheduling, 3, 259\u2013272.","journal-title":"Journal of\u00a0Scheduling"},{"key":"288_CR4","doi-asserted-by":"crossref","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\u00a0Algorithms, 35, 108\u2013121.","journal-title":"Journal of\u00a0Algorithms"},{"issue":"3","key":"288_CR5","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.dam.2011.10.001","volume":"160","author":"S. Y. Cai","year":"2012","unstructured":"Cai, S. Y., & Yang, Q. F. (2012). Online scheduling on three uniform machines. Discrete Applied Mathematics, 160(3), 291\u2013302.","journal-title":"Discrete Applied Mathematics"},{"key":"288_CR6","doi-asserted-by":"crossref","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":"288_CR7","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/0209007","volume":"9","author":"Y. Cho","year":"1980","unstructured":"Cho, Y., & Sahni, S. (1980). Bounds for list schedules on uniform processors. SIAM Journal on Computing, 9, 91\u2013103.","journal-title":"SIAM Journal on Computing"},{"key":"288_CR8","unstructured":"Ebenlendr, T. (2011). Combinatorial algorithms for online problems: semi-online scheduling on related machines. Ph.D. Thesis, Charles University, Prague."},{"key":"288_CR9","series-title":"Lecture notes in comput. sci.","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1007\/978-3-642-29116-6_9","volume-title":"Proc. 9th international workshop in approximation and online algorithms (WAOA 2011)","author":"T. Ebenlendr","year":"2012","unstructured":"Ebenlendr, T., & Sgall, J. (2012). A lower bound on deterministic online algorithms for scheduling on related machines without preemption. In Lecture notes in comput. sci.: Vol.\u00a07164. Proc. 9th international workshop in approximation and online algorithms (WAOA 2011) (pp. 102\u2013108). Berlin: Springer."},{"key":"288_CR10","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1007\/s00453-008-9235-6","volume":"53","author":"T. Ebenlendr","year":"2009","unstructured":"Ebenlendr, T., Jawor, W., & Sgall, J. (2009). Preemptive online scheduling: optimal algorithms for all speeds. Algorithmica, 53, 504\u2013522.","journal-title":"Algorithmica"},{"key":"288_CR11","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0167-6377(99)00062-0","volume":"26","author":"L. Epstein","year":"2000","unstructured":"Epstein, L., & Sgall, J. (2000). A lower bound for on-line scheduling on uniformly related machines. Operations Research Letters, 26, 17\u201322.","journal-title":"Operations Research Letters"},{"key":"288_CR12","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1002\/jos.60","volume":"4","author":"L. Epstein","year":"2001","unstructured":"Epstein, L., Noga, J., Seiden, S. S., Sgall, J., & Woeginger, G. J. (2001). Randomized on-line scheduling for two uniform machines. Journal of\u00a0Scheduling, 4, 71\u201392.","journal-title":"Journal of\u00a0Scheduling"},{"key":"288_CR13","first-page":"107","volume":"9","author":"U. Faigle","year":"1989","unstructured":"Faigle, U., Kern, W., & Tur\u00e1n, G. (1989). On the performance of\u00a0online algorithms for partition problems. Acta Cybernetica, 9, 107\u2013119.","journal-title":"Acta Cybernetica"},{"key":"288_CR14","doi-asserted-by":"crossref","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). On-line scheduling revisited. Journal of\u00a0Scheduling, 3, 343\u2013353.","journal-title":"Journal of\u00a0Scheduling"},{"key":"288_CR15","doi-asserted-by":"crossref","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":"288_CR16","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R. L. Graham","year":"1966","unstructured":"Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. The Bell System Technical Journal, 45, 1563\u20131581.","journal-title":"The Bell System Technical Journal"},{"key":"288_CR17","doi-asserted-by":"crossref","unstructured":"Han, F., Tan, Z., & Yang, Y. (2011, to appear). On the optimality of\u00a0list scheduling for online uniform machines scheduling. Optimization Letters. doi: 10.1007\/s11590-011-0335-x .","DOI":"10.1007\/s11590-011-0335-x"},{"key":"288_CR18","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/s10951-010-0177-x","volume":"14","author":"A. Musitelli","year":"2011","unstructured":"Musitelli, A., & Nicoletti, J. M. (2011). Competitive ratio of\u00a0list scheduling on uniform machines and randomized heuristics. Journal of\u00a0Scheduling, 14, 89\u2013101.","journal-title":"Journal of\u00a0Scheduling"},{"key":"288_CR19","unstructured":"Rudin, J. F. III (2001). Improved bound for the online scheduling problem. Ph.D. Thesis, The University of\u00a0Texas at Dallas."}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-012-0288-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T20:02:44Z","timestamp":1497988964000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-012-0288-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,12]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["288"],"URL":"https:\/\/doi.org\/10.1007\/s10951-012-0288-7","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,12]]}}}