##
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?

##
Implementations

Discrete Optimization Methods (Pascal) (rating 4)

Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 4)

##
Related Problems

Bin Packing

Edge Coloring

Feedback Edge/Vertex Set

Matching

Topological Sorting

Vertex Coloring

Go to the corresponding chapter in the book

About the Book

Send us Mail

Go to Main Page

This page last modified on Tue Jun 03, 1997
.