{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:34:27Z","timestamp":1787340867850,"version":"build-2736575974"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1995,8]]},"abstract":"<jats:p>In traditional precedence-constrained scheduling a task is ready to execute when all its predecessors are complete. We call such a task an AND task. In this paper we allow certain tasks to be ready when just one of their predecessors is complete. These tasks are known as OR tasks. We analyze the complexity of two types of real-time AND\/OR task scheduling problems. In the first type of problem, all the predecessors of every OR task must eventually be completed, but in the second type of problem, some OR predecessors may be left unscheduled. We show that most problems involving tasks with individual deadlines are NP-complete, and then present two priority-driven heuristic algorithms to minimize completion time on a multiprocessor. These algorithms provide the same level of worst-case performance as some previous priority-driven algorithms for scheduling AND-only task systems.<\/jats:p>","DOI":"10.1137\/s0097539791218664","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:42:53Z","timestamp":1109227373000},"page":"797-810","source":"Crossref","is-referenced-by-count":44,"title":["Scheduling Tasks with AND\/OR Precedence Constraints"],"prefix":"10.1137","volume":"24","author":[{"given":"Donald W.","family":"Gillies","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jane W.-S.","family":"Liu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","unstructured":"P.R. Chang, Ph.D. Thesis,  Parallel algorithms and VLSI architectures for robotics and assembly scheduling, Department of Electrical Engineering, Purdue University, West Lafayette, IN,  1988"},{"key":"R2","volume-title":"Computer and job-shop scheduling theory","author":"Coffman, Jr. E. G.","year":"1976"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1109\/12.57057"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288885"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1109\/70.54734"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0206029"},{"key":"R7","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0210018"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"D. W. Gillies, J. W.S. Liu,  Greed in resource scheduling,  Proc. IEEE Real-Time Systems Symposium, Vol. 10,  1989,  285\u2013294","DOI":"10.1109\/REAL.1989.63581"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261655"},{"key":"R11","unstructured":"D. W. Gillies, J. W.S. Liu,  Scheduling Tasks with AND\/OR Precedence Constraints, Tech. report, UIUCDCS-R-90-1627(UIUC-ENG-1766), Department of Computer Science, University of Illinois, Urbana, IL,  1991"},{"key":"R12","unstructured":"D. W. Gillies, Ph.D. Thesis,  Algorithms to schedule tasks with AND\/OR precedence constraints, Department of Computer Science, University of Illinois, Urbana, IL,  1993"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1287\/opre.9.6.841"},{"key":"R15","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. J. Rinnooy Kan, D. B. Shmoys,  Sequencing and Scheduling: Algorithms and Complexity, Tech. report, BS-R8908, Department of Operations Research, Statistics, and System Theory, Centre for Mathematics and Computer Science, Amsterdam, Holland,  1989"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.1988.51109"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.15.1.102"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676931"},{"key":"R19","unstructured":"V. Saletore, L. V. Kale,  Obtaining first solution faster in AND and OR parallel execution of logic programs,  North American Conference on Logic Programming, Vol. 1,  1989,  390\u2013406"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539791218664","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:53:33Z","timestamp":1787338413000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539791218664"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,8]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,8]]}},"alternative-id":["10.1137\/S0097539791218664"],"URL":"https:\/\/doi.org\/10.1137\/s0097539791218664","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,8]]}}}