{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T07:02:33Z","timestamp":1649055753854},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2001,12]]},"abstract":"<jats:p> In this paper, we consider the problem of scheduling independent jobs in partitionable mesh connected systems. The problem is NP-hard, since it includes the multiprocessor scheduling problem as a special case when all jobs request for one processor. We analyze a simple approximation algorithm called A <jats:sub>m<\/jats:sub>. In particular, we show that if the sizes of submeshes requested by jobs are independent and identically distributed (i.i.d.) random variables uniformly distributed in the range [1..M<jats:sub>1<\/jats:sub>]\u00d7[1..M<jats:sub>2<\/jats:sub>], where M<jats:sub>1<\/jats:sub>\u00d7M<jats:sub>2<\/jats:sub> is the size of a partitionable mesh connected system, and task execution times are i.i.d. random variables with finite mean and variance, then the average-case performance ratio E( A <jats:sub>m<\/jats:sub>(L))\/E( OPT (L)) is asymptotically bounded from above by 1.6637594\u2026. The average-case performance ratio improves significantly when jobs request for square submeshes or small submeshes. <\/jats:p>","DOI":"10.1142\/s0129054101000850","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:02:01Z","timestamp":1027767721000},"page":"763-773","source":"Crossref","is-referenced-by-count":1,"title":["AN EFFICIENT JOB SCHEDULING ALGORITHM IN PARTITIONABLE MESH CONNECTED SYSTEMS"],"prefix":"10.1142","volume":"12","author":[{"given":"KEQIN","family":"LI","sequence":"first","affiliation":[{"name":"Department of Computer Science, State University of New York, New Paltz, New York 12561, U.S.A."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212033"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90012-4"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1137\/0603007"},{"key":"p_4","first-page":"87","author":"Coffman E. G.","year":"1992","journal-title":"D. C."},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1137\/0204015"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1137\/0203025"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1137\/0219059"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90024-J"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1109\/71.97898"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90058-K"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321934"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054101000850","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:35:03Z","timestamp":1565192103000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054101000850"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,12]]},"references-count":11,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2001,12]]}},"alternative-id":["10.1142\/S0129054101000850"],"URL":"https:\/\/doi.org\/10.1142\/s0129054101000850","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,12]]}}}