Files in this item



application/pdf9329041.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF


Title:Algorithms to Schedule Tasks With And/or Precedence Constraints
Author(s):Gillies, Donald William
Doctoral Committee Chair(s):Liu, Jane W.S.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
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.
Issue Date:1993
Description:133 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993.
Other Identifier(s):(UMI)AAI9329041
Date Available in IDEALS:2014-12-17
Date Deposited:1993

This item appears in the following Collection(s)

Item Statistics