1.3.9 Job Scheduling
INPUT OUTPUT
Input Description:
A directed acyclic graph G=(V,E), where the vertices represent
jobs and the the edge (u,v) that task u must be completed
before task v.
Problem:
What schedule of tasks to completes the job using the minimum
amount of time or processors?
Excerpt from
The Algorithm Design Manual:
Devising a proper schedule to satisfy a set of constraints is fundamental to many applications. A critical
aspect of any parallel processing system is the algorithm mapping tasks to processors. Poor scheduling can
leave most of the expensive machine sitting idle while one bottleneck task is performed. Assigning people to
jobs, meetings to rooms, or courses to final exam periods are all different examples of scheduling problems.
Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of
schedule desired. For this reason, several other catalog problems have a direct application to various kinds
of scheduling.
We focus on precedence-constrained scheduling problems for directed acyclic graphs. These problems are often
called PERT/CPM, for Program Evaluation and Review Technique/Critical Path Method. Suppose you have
broken a big job into a large number of smaller tasks. For each task you know how long it should take (or
perhaps an upper bound on how long it might take). Further, for each pair of tasks you know whether it is
essential that one task be performed before another. The fewer constraints we have to enforce, the better our
schedule can be. These constraints must define a directed acyclic graph, acyclic because a cycle in the
precedence constraints represents a Catch-22 situation that can never be resolved.
Recommended Books
Related Links
PATAT conference
Related Problems
This page last modified on 2008-07-10
.
www.algorist.com
Scheduling Algorithms
Handbook of Scheduling: Algorithms, Models, and Performance Analysis
Scheduling: Theory, Algorithms, and Systems
Intelligent Scheduling
