University of Illinois Urbana-Champaign

Algorithms to Schedule Tasks With And/or Precedence Constraints

Gillies, Donald William

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/72085

Description

Title
Algorithms to Schedule Tasks With And/or Precedence Constraints
Author(s)
Gillies, Donald William
Issue Date
1993
Doctoral Committee Chair(s)
Liu, Jane W.S.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
  • Mathematics
  • Operations Research
  • Computer Science
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.
  • 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.
Graduation Semester
1993
Type of Resource
text
Permalink
http://hdl.handle.net/2142/72085

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Dept. of Computer Science