Scheduling with Unary Resources: the Bridge Problem

A unary resource is a resource with capacity one. Scheduling with unary resources is a very special case of scheduling. Indeed, the fact that any two activities requiring a common unary resource cannot overlap implies that these two activities must be put in order: one of the two activities must execute before the other simply because their common unary resource is a unit and thus cannot be used in two ways at a time.

More generally, if n activities A1, A2, ...., An require the same unary resource, and if none of these activities Ai can be started and interrupted for the benefit of another activity Aj, then in any problem solution, the n activities A1, A2, ...., An must be totally ordered.

In other words, when faced with that kind of problem, you will simply use Scheduler to write an algorithm that puts the activities in order, and that algorithm will actually find a solution to the problem simply by putting the activities to schedule in order.

Indeed, as soon as decisions are made regarding the order in which activities sharing a resource must execute, these decisions apply as additional precedence constraints. When all the necessary ordering decisions have been made--whether by the nature of the problem or by an algorithm that you write for the purpose--the resource constraints are guaranteed to hold, and the residual problem consists merely of temporal constraints, for which constraint propagation is known to be complete.

The earliest and latest start and end times of activities under the chosen order are fully determined: they are feasible start and end times.

For this reason, scheduling under temporal and unary resource constraints is often known as "sequencing," "disjunctive scheduling," or "disjunctive," conveying the idea that for each pair {A B} of activities that share a resource, either A must be performed before B, or B must be performed before A.

This chapter shows how Scheduler can be used to solve a disjunctive scheduling problem efficiently.