{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T08:46:09Z","timestamp":1770972369969,"version":"3.50.1"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2014,8]]},"abstract":"<jats:p> In this paper we study an online minimum makespan scheduling problem with a reordering buffer. We obtain the following results: (i) for m &gt; 51 identical machines, we give a 1.5-competitive online algorithm with a buffer of size \u23081.5m\u2309; (ii) for three identical machines, we give an optimal online algorithm with a buffer size six, better than the previous nine; (iii) for m uniform machines, using a buffer of size m, we improve the competitive ratio from 2 + \u03b5 to 2 \u2212 1\/m+ \u03b5, where \u03b5 &gt; 0 is sufficiently small and m is a constant. <\/jats:p>","DOI":"10.1142\/s0129054114500191","type":"journal-article","created":{"date-parts":[[2014,8,29]],"date-time":"2014-08-29T09:11:47Z","timestamp":1409303507000},"page":"525-536","source":"Crossref","is-referenced-by-count":10,"title":["ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER"],"prefix":"10.1142","volume":"25","author":[{"given":"NING","family":"DING","sequence":"first","affiliation":[{"name":"Software School, Dalian University of Technology, P. R., China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YAN","family":"LAN","sequence":"additional","affiliation":[{"name":"Software School, Dalian University of Technology, Dalian Neusoft Institute of Information, P. R., China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"XIN","family":"CHEN","sequence":"additional","affiliation":[{"name":"Software School, Dalian University of Technology, P. R., China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"GY\u00d6RGY","family":"D\u00d3SA","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Pannonia, Veszpr\u00e9m, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HE","family":"GUO","sequence":"additional","affiliation":[{"name":"Software School, Dalian University of Technology, P. R., China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"XIN","family":"HAN","sequence":"additional","affiliation":[{"name":"Software School, Dalian University of Technology, P. R., China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2014,8,29]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797324874"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1074"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1070"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.07.014"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.10.019"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(02)00179-7"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1002\/1099-1425(200011\/12)3:6<343::AID-JOS54>3.0.CO;2-2"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1137\/0216037"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1137\/0217033"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0019"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(98)00005-4"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.007"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403438"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0381"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.03.007"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2007.06.004"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00006-9"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054114500191","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:29:42Z","timestamp":1565123382000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054114500191"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":18,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2014,8,29]]},"published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.1142\/S0129054114500191"],"URL":"https:\/\/doi.org\/10.1142\/s0129054114500191","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8]]}}}