{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72085"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72085","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Algorithms to Schedule Tasks With And/or Precedence Constraints","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Gillies, Donald William"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Liu, Jane W.S."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-17T20:00:39Z","date_published":"2014-12-17T20:00:39Z","updated_at":"2026-07-22T22:26:06Z","subjects":["Mathematics","Operations Research","Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI9329041"],"render_values":[{"text":"(UMI)AAI9329041","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/72085","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Liu, Jane W.S."]},{"key":"dc:creator","label":"Author","values":["Gillies, Donald William"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-17T20:00:39Z","10000-01-01","1993"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Operations Research","Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72085","(UMI)AAI9329041"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:title","label":"Title","values":["Algorithms to Schedule Tasks With And/or Precedence Constraints"]}]}],"canonical_facts":{"dc:contributor":["Liu, Jane W.S."],"dc:creator":["Gillies, Donald William"],"dc:date":["2014-12-17T20:00:39Z","10000-01-01","1993"],"dc:description":["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."],"dc:identifier":["http://hdl.handle.net/2142/72085","(UMI)AAI9329041"],"dc:subject":["Mathematics","Operations Research","Computer Science"],"dc:title":["Algorithms to Schedule Tasks With And/or Precedence Constraints"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:06Z"}