Interval (Scheduling)

computation scheduling

Definition

Interval

An interval in scheduling is the fixed time window during which a job occupies a machine.

For a job , the interval is usually written as the half-open interval

where is the start time and is the finish time.

Compatibility

Disjointness

Two intervals and are compatible exactly when they do not overlap:

Convention

The half-open form means that a job finishing at time does not overlap a job starting at time . Thus the same machine may process and then when