Time Tabling and Scheduling
Next: Frequency Assignment
Up: Sample Applications
Previous: Sample Applications
Many scheduling problems
involve allowing for a number of pairwise restrictions on which jobs
can be done simultaneously. For instance, in attempting to schedule
classes at a university, two courses taught by the same faculty member
cannot be scheduled for the same time slot. Similarly, two course
that are required by the same group of students also should not
conflict. The problem of determining the minimum number of time slots
needed subject to these restrictions is a graph coloring problem.
This problems has been studied by many researchers, including
Leighton [64], Opsu and Roberts [74], and de Werra
[33].
Michael A. Trick
Thu Oct 27 21:43:48 EDT 1994