{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:28:35Z","timestamp":1787340515905,"version":"3.56.0"},"reference-count":10,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1986,5]]},"abstract":"<jats:p>The problem of scheduling tasks on m processors to minimize the schedule length (makespan) is NP-complete. Here we study the behavior of list schedules under the assumptions that there are no task precedence constraints and that task times are chosen from a uniform distribution.<\/jats:p>\n                  <jats:p>We show that, given a desired degree of confidence $1 - \\varepsilon $, we can find a minimum sample size N such that if $n \\geqq N$ and the n task times $\\bar X = (X_1 , \\cdots ,X_n )$ are chosen from any uniform distribution, then \\[ {\\bf P}\\left[ {\\frac{{L(\\bar X)}}{{{\\operatorname{OPT}}(\\bar X)}} &lt; 1 + \\frac{{4(m - 1)}}{n}} \\right] &gt; 1 - \\varepsilon \\] where $L(\\bar X)$ is the length of any list schedule and ${\\operatorname{OPT}}(\\bar X)$ is the length of the optimal schedule. Thus for n sufficiently large, the performance of any list schedule can be made arbitrarily close to that of the optimal policy with any desired degree of confidence. For example, for $m = 2$ and $\\varepsilon = 0.01$, the ratio is bounded by 1.11 when $n = 36$ and bounded by 1.03 when $n = 100$.<\/jats:p>","DOI":"10.1137\/0215028","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:28:10Z","timestamp":1109226490000},"page":"409-417","source":"Crossref","is-referenced-by-count":15,"title":["Probabilistic Bounds on the Performance of List Scheduling"],"prefix":"10.1137","volume":"15","author":[{"given":"John L.","family":"Bruno","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter J.","family":"Downey","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RBIR51","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729550"},{"key":"RCOF84","doi-asserted-by":"publisher","DOI":"10.1287\/moor.9.2.260"},{"key":"RCOF85","doi-asserted-by":"publisher","DOI":"10.1287\/opre.33.3.548"},{"key":"RCON80","volume-title":"Practical Nonparametric Statistics","author":"Conover W. J.","year":"1980"},{"key":"RDUR73","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970586"},{"key":"RGAR79","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"RGRA69","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"RGRA76","volume-title":"Computer and Job-Shop Scheduling Theory","author":"Graham R. L.","year":"1976"},{"key":"RMIL56","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1956.10501314"},{"key":"ROWE62","volume-title":"Handbook of statistical tables","author":"Owen D. B.","year":"1962"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0215028","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:48Z","timestamp":1787337468000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0215028"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,5]]},"references-count":10,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1986,5]]}},"alternative-id":["10.1137\/0215028"],"URL":"https:\/\/doi.org\/10.1137\/0215028","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,5]]}}}