{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T10:47:35Z","timestamp":1649069255575},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[1995,9]]},"abstract":"<jats:p> Job scheduling on multiprocessor systems is studied here as a special case of oriented two-dimensional orthogonal bin packing. Each job has subtasks which can be processed in parallel, requiring multiple processors to be allocated to each job. Then each job corresponds to a rectangle with sides equal to the processor requirement and the processing time. We study two classes of algorithms: (i) Longest processing time first (LPT) algorithms, and (ii) Largest processor requirement first (LPR) algorithms. We obtain improved asymptotic upper bounds for these algorithms compared to the bounds of the corresponding algorithms for the general two-dimensional packing problem. This is due to the discrete nature of the processor requirement (dimension) of jobs. We find that the LPR algorithms have better asymptotic upper bound on the makespan compared to the LPT algorithms. Specifically, the bound is 7\/4 for the LPR algorithms whereas it is 2 for the LPT algorithms. Moreover, LPR algorithms are found to be more suited for dynamic job scheduling. <\/jats:p>","DOI":"10.1142\/s0129626495000321","type":"journal-article","created":{"date-parts":[[2004,11,10]],"date-time":"2004-11-10T11:14:37Z","timestamp":1100085277000},"page":"343-355","source":"Crossref","is-referenced-by-count":0,"title":["PERFORMANCE BOUNDS FOR STATIC MULTIPROCESSOR SCHEDULING OF MULTI-TASK JOBS"],"prefix":"10.1142","volume":"05","author":[{"given":"S.","family":"MAHESH","sequence":"first","affiliation":[{"name":"Tata Information Systems Ltd., Bangalore - 560 017, India"}]},{"given":"C. SIVA RAM","family":"MURTHY","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology, Madras - 600 036, India"}]},{"given":"C. PANDU","family":"RANGAN","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology, Madras - 600 036, India"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626495000321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T16:18:03Z","timestamp":1565108283000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626495000321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":0,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1995,9]]}},"alternative-id":["10.1142\/S0129626495000321"],"URL":"https:\/\/doi.org\/10.1142\/s0129626495000321","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}