2026-09-23T00:16:40Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/72085 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Liu, Jane W.S. Gillies, Donald William 2014-12-17T20:00:39Z 2014-12-17T20:00:39Z 10000-01-01 1993 1993 In traditional precedence-constrained scheduling a task is ready to execute when all its predecessors are completed. We call such a task an AND task. In many applications there are tasks which are ready to execute when some but not all of their predecessors are complete. We call these tasks OR tasks. The resultant task system, containing both AND and OR tasks, is said to have AND/OR precedence constraints. In this thesis we consider two types of AND/OR scheduling problems: In an "unskipped" problem, all the predecessors of every OR task must eventually be completed, but in a "skipped" problem, some OR predecessors may be left unscheduled. Many classes of AND-only graphs with deadlines can be scheduled in polynomial time in a computer system with 1, 2, or m processors. We show that when OR tasks are present in the task graphs, the aforementioned scheduling problems become NP-hard. We propose approximation algorithms to schedule important subclasses of the AND/OR scheduling problem. For the general problem of minimizing the completion time of an AND/OR/skipped task system on a parallel processor, we propose a class of heuristics that are extensions of our approximation algorithms. The performance of these heuristics is evaluated through simulation. Made available in DSpace on 2014-12-17T20:00:39Z (GMT). No. of bitstreams: 1 9329041.pdf: 5933372 bytes, checksum: 0fe53cfe8bf3509a43aaf54e173d01e6 (MD5) Previous issue date: 1993 Embargo set by: Seth Robbins for item 72253 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs U of I Only 133 p. Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993. http://hdl.handle.net/2142/72085 (UMI)AAI9329041 Mathematics Operations Research Computer Science Algorithms to Schedule Tasks With And/or Precedence Constraints text Computer Science Computer Science University of Illinois at Urbana-Champaign Dissertation Ph.D.