{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T17:32:45Z","timestamp":1649093565648},"reference-count":14,"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":[[2015,10]]},"abstract":"<jats:p> This paper addresses online scheduling of malleable parallel jobs to minimize the maximum completion time, i.e., makespan. It is assumed that the execution time of a job J<jats:sub>j<\/jats:sub> with processing time p<jats:sub>j<\/jats:sub> is p<jats:sub>j<\/jats:sub>\/k + (k-1)c if the job is assigned to k machines, where c &gt; 0 is a constant setup time. We consider online algorithms for the scheduling problem on two identical machines. Namely, the job J<jats:sub>j<\/jats:sub> can be processed on one machine with execution time p<jats:sub>j<\/jats:sub> or alternatively two machines in parallel with execution time p<jats:sub>j<\/jats:sub>\/2+c. For the asymptotical competitive ratio, we provide an improved online algorithm with makespan no more than (3\/2)C* +c\/2, where C* is the optimal makespan. For the strict competitive ratio, we propose an online algorithm with competitive ratio of 1.54, which is close to the lower bound of 1.5. <\/jats:p>","DOI":"10.1142\/s0217595915500347","type":"journal-article","created":{"date-parts":[[2015,4,13]],"date-time":"2015-04-13T22:42:16Z","timestamp":1428964936000},"page":"1550034","source":"Crossref","is-referenced-by-count":0,"title":["Improved Algorithms for Online Scheduling of Malleable Parallel Jobs on Two Identical Machines"],"prefix":"10.1142","volume":"32","author":[{"given":"Hao","family":"Zhou","sequence":"first","affiliation":[{"name":"Department of Basic Science, Zhejiang Shuren University, Hangzhou 310015, P. R. China"}]},{"given":"Ping","family":"Zhou","sequence":"additional","affiliation":[{"name":"School of Humanities, Zhejiang Business College, Hangzhou 310053, P. R. China"}]},{"given":"Yiwei","family":"Jiang","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou 310018, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2015,10,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2006.58"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.07.005"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.258"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2010.03.005"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.10.010"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.06.064"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2007.06.001"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.05.033"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1078-6"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.04.003"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-006-8497-6"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.02.023"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-007-0032-x"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9125-x"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595915500347","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T23:39:57Z","timestamp":1565134797000},"score":1,"resource":{"primary":{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595915500347"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10]]},"references-count":14,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2015,10,20]]},"published-print":{"date-parts":[[2015,10]]}},"alternative-id":["10.1142\/S0217595915500347"],"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1142\/s0217595915500347","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10]]}}}