{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T13:10:30Z","timestamp":1649077830342},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2014,10]]},"abstract":"<jats:p> Batch processing machine scheduling in uncertain environment attracts more and more attention in the last decade. This paper deals with semi-online scheduling on two parallel batch processing machines with non-decreasing processing time of job. Jobs arrive over time in the online paradigm, and the processing time of any batch is equal to the length of the last arrival job in the batch. We study the unbounded model where each processing batch may contain an unlimited number of jobs, and the objective is to minimize the makespan. Given any job J<jats:sub>j<\/jats:sub> together with its following job J<jats:sub>j+1<\/jats:sub>, it is assumed that their processing times satisfy p<jats:sub>j+1<\/jats:sub> \u2265 \u03b1p<jats:sub>j<\/jats:sub> where \u03b1 \u2265 1 is a constant. That is, jobs arrive in a non-decreasing order of processing times. We mainly propose an optimal \u03d5-competitive online algorithm where \u03d5 \u2265 1 is a solution of equation \u03d5<jats:sup>3<\/jats:sup> + (\u03b1-1)\u03d5<jats:sup>2<\/jats:sup> + (\u03b1<jats:sup>2<\/jats:sup> - \u03b1 - 1)\u03d5 - \u03b1<jats:sup>2<\/jats:sup> = 0. <\/jats:p>","DOI":"10.1142\/s0217595914500389","type":"journal-article","created":{"date-parts":[[2014,7,15]],"date-time":"2014-07-15T02:01:56Z","timestamp":1405389716000},"page":"1450038","source":"Crossref","is-referenced-by-count":1,"title":["Optimal Semi-Online Algorithm for Scheduling on Two Parallel Batch Processing Machines"],"prefix":"10.1142","volume":"31","author":[{"given":"Ming","family":"Liu","sequence":"first","affiliation":[{"name":"School of Economics and Management, Tongji University, Shanghai 200092, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feifeng","family":"Zheng","sequence":"additional","affiliation":[{"name":"Glorious Sun School of Business and Management, Donghua University, Shanghai 200092, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhanguo","family":"Zhu","sequence":"additional","affiliation":[{"name":"School of Economics and Management, Nanjing Agricultural University, Nanjing 210095, P. R. China"},{"name":"Laboratoire d'Informatique, Biologie Int\u00e9grative et Syst\u00e8mes Complexes (IBISC), EA 4526, Universit\u00e9 d'Evry Val d'Essonne 91020, Evry Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chengbin","family":"Chu","sequence":"additional","affiliation":[{"name":"Laboratoire G\u00e9nie Industriel, Ecole Centrale Paris, Grande Voie des Vignes, 92295, Ch\u00e2tenay-Malabry Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2014,10,23]]},"reference":[{"key":"rf1","volume-title":"Online Computation and Competitive Analysis","author":"Borodin A.","year":"1998"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1027316504440"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.040"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2007.07.001"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2008.03.004"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijpe.2006.12.061"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-005-6855-5"},{"key":"rf9","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"Pruhs K.","year":"2004"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.02.011"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1002\/nav.5"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1080\/07408170304378"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595914500389","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:24:59Z","timestamp":1565191499000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595914500389"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10]]},"references-count":11,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2014,10,23]]},"published-print":{"date-parts":[[2014,10]]}},"alternative-id":["10.1142\/S0217595914500389"],"URL":"https:\/\/doi.org\/10.1142\/s0217595914500389","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10]]}}}