{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T00:52:50Z","timestamp":1649119970255},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p> We consider two semi-online scheduling problems on a single batch (processing) machine with jobs' nondecreasing processing times and jobs' nonincreasing processing times, respectively. Our objective is to minimize the makespan. A batch processing machine can handle up to B jobs simultaneously. We study an unbounded model where B = \u221e. The jobs that are processed together construct a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Jobs arrive over time. Let p<jats:sub>j<\/jats:sub> denote the processing time of job J<jats:sub>j<\/jats:sub>. Given job J<jats:sub>j<\/jats:sub> and its following job J<jats:sub>j + 1<\/jats:sub>, we assume that p<jats:sub>j + 1<\/jats:sub> \u2265 \u03b1 p<jats:sub>j<\/jats:sub>, where \u03b1 \u2265 1 is a constant number, for the first problem with jobs' nondecreasing processing times. For the second problem, we assume that p<jats:sub>j + 1<\/jats:sub> \u2264 \u03b1 p<jats:sub>j<\/jats:sub>, where 0 &lt; \u03b1 &lt; 1 is a constant number. We propose an optimal algorithm for both problems with a competitive ratio [Formula: see text] for the first problem and [Formula: see text] for the second problem. <\/jats:p>","DOI":"10.1142\/s1793830909000178","type":"journal-article","created":{"date-parts":[[2009,7,2]],"date-time":"2009-07-02T11:53:30Z","timestamp":1246535610000},"page":"219-226","source":"Crossref","is-referenced-by-count":0,"title":["OPTIMAL SEMI-ONLINE ALGORITHM FOR SCHEDULING ON A BATCH PROCESSING MACHINE"],"prefix":"10.1142","volume":"01","author":[{"given":"MING","family":"LIU","sequence":"first","affiliation":[{"name":"School of Management, Xi'an Jiaotong University, Xi'an, Shaanxi Province, 710049, P. R. China"},{"name":"Laboratoire G\u00e9nie Industriel, Ecole Centrale Paris, Grande Voie des Vignes, 92295 Ch\u00e2tenay-Malabry Cedex, France"}]},{"given":"YINFENG","family":"XU","sequence":"additional","affiliation":[{"name":"School of Management, Xi'an Jiaotong University, Xi'an, Shaanxi Province, 710049, P. R. China"}]},{"given":"CHENGBIN","family":"CHU","sequence":"additional","affiliation":[{"name":"School of Management, Xi'an Jiaotong University, Xi'an, Shaanxi Province, 710049, P. R. China"},{"name":"Laboratoire G\u00e9nie Industriel, Ecole Centrale Paris, Grande Voie des Vignes, 92295 Ch\u00e2tenay-Malabry Cedex, France"}]},{"given":"LU","family":"WANG","sequence":"additional","affiliation":[{"name":"Shanghai Vocational School of CAAC, Shanghai, 200232, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","volume-title":"Online Computation and Competitive Analysis","author":"Borodin A.","year":"1998"},{"key":"rf2","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"Pruhs K.","year":"2004"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1287\/opre.40.4.764"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1080\/002075499192020"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1002\/nav.5"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1023\/A:1027316504440"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-005-6855-5"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.040"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2007.07.001"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijpe.2006.12.061"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830909000178","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:57:56Z","timestamp":1565193476000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830909000178"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":10,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1142\/S1793830909000178"],"URL":"https:\/\/doi.org\/10.1142\/s1793830909000178","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]}}}