{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T03:22:17Z","timestamp":1778210537935,"version":"3.51.4"},"reference-count":19,"publisher":"Elsevier BV","issue":"5","license":[{"start":{"date-parts":[[2000,12,1]],"date-time":"2000-12-01T00:00:00Z","timestamp":975628800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research Letters"],"published-print":{"date-parts":[[2000,12]]},"DOI":"10.1016\/s0167-6377(00)00053-5","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T21:05:54Z","timestamp":1027631154000},"page":"215-221","source":"Crossref","is-referenced-by-count":81,"title":["Semi-online scheduling with decreasing job sizes"],"prefix":"10.1016","volume":"27","author":[{"given":"Steve","family":"Seiden","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ji\u0159\u0131\u0301","family":"Sgall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerhard","family":"Woeginger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0167-6377(00)00053-5_BIB1","doi-asserted-by":"crossref","unstructured":"S. Albers, Better bounds for online scheduling, Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 130\u2013139.","DOI":"10.1145\/258533.258566"},{"key":"10.1016\/S0167-6377(00)00053-5_BIB2","doi-asserted-by":"crossref","unstructured":"Y. Azar, O. Regev, Online bin stretching, Proceedings of RANDOM, 1998, pp. 71\u201382.","DOI":"10.1007\/3-540-49543-6_7"},{"key":"10.1016\/S0167-6377(00)00053-5_BIB3","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1006\/jcss.1995.1074","article-title":"New algorithms for an ancient scheduling problem","volume":"51","author":"Bartal","year":"1995","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0167-6377(00)00053-5_BIB4","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0020-0190(94)00026-3","article-title":"A better lower bound for on-line scheduling","volume":"50","author":"Bartal","year":"1994","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0167-6377(00)00053-5_BIB5","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0020-0190(94)00110-3","article-title":"A lower bound for randomized on-line scheduling algorithms","volume":"51","author":"Chen","year":"1994","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0167-6377(00)00053-5_BIB6","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0167-6377(94)90071-X","article-title":"New lower and upper bounds for on-line scheduling","volume":"16","author":"Chen","year":"1994","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/S0167-6377(00)00053-5_BIB7","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0167-6377(95)00039-9","article-title":"An optimal algorithm for preemptive on-line scheduling","volume":"18","author":"Chen","year":"1995","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/S0167-6377(00)00053-5_BIB8","first-page":"107","article-title":"On the performance of on-line algorithms for partition problems","volume":"9","author":"Faigle","year":"1989","journal-title":"Acta Cybernet."},{"key":"10.1016\/S0167-6377(00)00053-5_BIB9","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1137\/0222026","article-title":"An online scheduling heuristic with better worst case ratio than Graham's list scheduling","volume":"22","author":"Galambos","year":"1993","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0167-6377(00)00053-5_BIB10","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","article-title":"Bounds for certain multiprocessing anomalies","volume":"45","author":"Graham","year":"1966","journal-title":"Bell Systems Tech. J."},{"key":"10.1016\/S0167-6377(00)00053-5_BIB11","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1137\/0117039","article-title":"Bounds on multiprocessing timing anomalies","volume":"17","author":"Graham","year":"1969","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/S0167-6377(00)00053-5_BIB12","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1006\/jagm.1996.0019","article-title":"A better algorithm for an ancient scheduling problem","volume":"20","author":"Karger","year":"1996","journal-title":"J. Algorithms"},{"key":"10.1016\/S0167-6377(00)00053-5_BIB13","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/S0167-6377(98)00005-4","article-title":"Semi online algorithms for the partition problem","volume":"21","author":"Kellerer","year":"1997","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/S0167-6377(00)00053-5_BIB14","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0167-6377(95)00058-5","article-title":"Ordinal algorithms for parallel machine scheduling","volume":"18","author":"Liu","year":"1996","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/S0167-6377(00)00053-5_BIB15","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF01294261","article-title":"Randomized competitive algorithms for the list update problem","volume":"11","author":"Reingold","year":"1994","journal-title":"Algorithmica"},{"key":"10.1016\/S0167-6377(00)00053-5_BIB16","doi-asserted-by":"crossref","unstructured":"S.S Seiden, Randomized algorithms for that ancient scheduling problem, Proceedings of the Fifth Workshop on Algorithms and Data Structures, 1997, pp. 210\u2013223.","DOI":"10.1007\/3-540-63307-3_61"},{"key":"10.1016\/S0167-6377(00)00053-5_BIB17","doi-asserted-by":"crossref","unstructured":"S.S. Seiden, Randomized online multiprocessor scheduling, Algorithmica, to appear.","DOI":"10.1007\/s004530010014"},{"key":"10.1016\/S0167-6377(00)00053-5_BIB18","doi-asserted-by":"crossref","unstructured":"J. Sgall, On-line scheduling on parallel machines, Ph.D. thesis, Carnegie-Mellon University, 1994","DOI":"10.1007\/3-540-58338-6_65"},{"key":"10.1016\/S0167-6377(00)00053-5_BIB19","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/S0020-0190(97)00093-8","article-title":"A lower bound for randomized on-line multiprocessor scheduling","volume":"63","author":"Sgall","year":"1997","journal-title":"Inform. Process. Lett."}],"container-title":["Operations Research Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167637700000535?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167637700000535?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,4,13]],"date-time":"2023-04-13T16:20:52Z","timestamp":1681402852000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0167637700000535"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,12]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2000,12]]}},"alternative-id":["S0167637700000535"],"URL":"https:\/\/doi.org\/10.1016\/s0167-6377(00)00053-5","relation":{},"ISSN":["0167-6377"],"issn-type":[{"value":"0167-6377","type":"print"}],"subject":[],"published":{"date-parts":[[2000,12]]}}}