{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T18:06:03Z","timestamp":1657562763164},"reference-count":9,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1977,1]]},"abstract":"\n Muntz and Coffman give a level algorithm that constructs optimal preemptive schedules on identical processors when the task system is a tree or when there are only two processors available. Their algorithm is adapted here to handle processors of different speeds. The new algorithm is optimal for independent tasks on any number of processors and for arbitrary task systems on two processors, but not on three or more processors, even for trees. By taking the algorithm as a heuristic on\n m<\/jats:italic>\n processors and using the ratio of the lengths of the constructed and optimal schedules as a measure, an upper bound on its performance is derived in terms of the speeds of the processors. It is further shown that 1.23\u221a\n m<\/jats:italic>\n is an upper bound over all possible processor speeds and that the 1.23\u221a\n m<\/jats:italic>\n bound can be improved at most by a constant factor, by giving an example of a system for which the bound 0.35\u221a\n m<\/jats:italic>\n can be approached asymptotically.\n <\/jats:p>","DOI":"10.1145\/321992.321995","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:13Z","timestamp":1027769173000},"page":"32-43","source":"Crossref","is-referenced-by-count":97,"title":["A Level Algorithm for Preemptive Scheduling"],"prefix":"10.1145","volume":"24","author":[{"given":"Edward C.","family":"Horvath","sequence":"first","affiliation":[{"name":"Computer Science Department, 312 Whitmore Laboratory, The Pennsylvania State University, University Park, PA"}]},{"given":"Shui","family":"Lam","sequence":"additional","affiliation":[{"name":"School of Computer Science, McGill University, Montreal, Canada"}]},{"given":"Ravi","family":"Sethi","sequence":"additional","affiliation":[{"name":"Bell Laboratories, Murray Hill, NJ"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_2","unstructured":"CFFMAN E G JR Ed Computer and Jobshop Scheduhng Theory Wdey New York 1976 CFFMAN E G JR Ed Computer and Jobshop Scheduhng Theory Wdey New York 1976"},{"key":"e_1_2_1_2_2","unstructured":"COFFMAN E G JR AND GRAHAM R.L Optimal scheduling for two processor systems Acta lnformanca 1 3 (1972) 200-213 COFFMAN E G JR AND GRAHAM R.L Optimal scheduling for two processor systems Acta lnformanca 1 3 (1972) 200-213"},{"key":"e_1_2_1_4_2","unstructured":"LAM S AND SETm R Worst case analysis of two scheduhng algorithms (To appear in SlAM J Comptg 1976 ) LAM S AND SETm R Worst case analysis of two scheduhng algorithms (To appear in SlAM J Comptg 1976 )"},{"key":"e_1_2_1_5_2","first-page":"27","volume-title":"North-Holland Pub Co","author":"Lit J","year":"1974"},{"key":"e_1_2_1_6_2","unstructured":"LIU J W S AND YANO A Optimal scheduling of independent tasks on heterogeneous computing systems Proc ACM 1974 Annual Conf. pp 38-45 10.1145\/800182.810377 LIU J W S AND YANO A Optimal scheduling of independent tasks on heterogeneous computing systems Proc ACM 1974 Annual Conf. pp 38-45 10.1145\/800182.810377"},{"key":"e_1_2_1_7_2","first-page":"1","volume":"12","author":"Mc NAUGHTON","year":"1959","journal-title":"Manage Sct"},{"key":"e_1_2_1_8_2","first-page":"1014","volume":"11","author":"MuNlz R R","year":"1969","journal-title":"IEEE Trans Comptrs C-18"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/321574.321586"},{"key":"e_1_2_1_10_2","first-page":"5","volume":"12","author":"Scheduhng","year":"1966","journal-title":"Manage Sct"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/321992.321995","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T15:04:38Z","timestamp":1614697478000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/321992.321995"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977,1]]},"references-count":9,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1977,1]]}},"alternative-id":["10.1145\/321992.321995"],"URL":"http:\/\/dx.doi.org\/10.1145\/321992.321995","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1977,1]]}}}