{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T13:19:49Z","timestamp":1791206389851,"version":"4.1.0"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,8]]},"abstract":"<jats:p>The problem of scheduling a partially ordered set of unit length tasks on m identical processors is known to be NP-complete. There are efficient algorithms for only a few special cases of this problem. In this paper we analyze the effect of the structure of the precedence graph and the availability of the processors on the construction of optimal schedules. We prove that to find an optimal schedule it suffices to consider at each step only initial tasks which belong to the $m - 1$ highest components of the precedence graph. This result reduces the number of cases we have to check during the construction of an optimal schedule. Our method leads to polynomial algorithms if the number of processors is fixed and the precedence graph has a certain form. In particular, if the precedence graph contains only intrees and outtrees, this result leads to linear algorithms for finding an optimal schedule on two or three processors.<\/jats:p>","DOI":"10.1137\/0214047","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"638-657","source":"Crossref","is-referenced-by-count":26,"title":["Scheduling Flat Graphs"],"prefix":"10.1137","volume":"14","author":[{"given":"Danny","family":"Dolev","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manfred","family":"Warmuth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,2]]},"reference":[{"key":"R1","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"J. Bruno,  Deterministic and stochastic scheduling problems with treelike precedence constraints,  NATO Conference, Durham, England,  1981, July","DOI":"10.1007\/978-94-009-7801-0_22"},{"key":"R3","volume-title":"Computer and job-shop scheduling theory","author":"Coffman, Jr. E. G.","year":"1976"},{"key":"R4","volume-title":"Operating Systems Theory","author":"Coffman, Jr. E. G.","year":"1973"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288685"},{"key":"R6","unstructured":"D. Dolev,  Scheduling wide graphs, Technical Report, STAN-CS-80-832, Dept. Computer Science, Stanford Univ., Stanford, CA,  1980, December"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90039-7"},{"key":"R8","unstructured":"D. Dolev, M. K. Warmuth,  Scheduling flat graphs, IBM Research Report, RJ3398,  1982, May"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0606066"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90069-7"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322335"},{"key":"R12","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0604011"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"R15","unstructured":"D. K. Goyal,  Scheduling series parallel structured tasks on multiprocessor computing systems, Technical Report, CS-76-034, Dept. Computer Science, Washington State Univ., Pullman,  1976, September"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1287\/opre.9.6.841"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.1.22"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804393"},{"key":"R19","unstructured":"E. W. Mayr,  Well structured parallel programs are not easier to schedule, Technical Report, STAN-CS-81-880, Dept. Computer Science, Stanford Univ., Stanford, CA,  1981, September"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0208031"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80008-0"},{"key":"R22","unstructured":"M. K. Warmuth, Ph.D. Thesis,  Scheduling on profiles of constant breadth, Dept. Computer Science, Univ. Colorado, Boulder,  1981, August"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214047","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:12Z","timestamp":1787337552000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214047"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,8]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1985,8]]}},"alternative-id":["10.1137\/0214047"],"URL":"https:\/\/doi.org\/10.1137\/0214047","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,8]]}}}