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 $j$, the interval is usually written as the half-open interval

$$I_j=[s_j,f_j)$$

where $s_j$ is the start time and $f_j$ is the finish time.

Compatibility

Disjointness

Two intervals $I_i=[s_i,f_i)$ and $I_j=[s_j,f_j)$ are compatible exactly when they do not overlap:

$$I_i\cap I_j=\varnothing ⟺f_i\le s_j\vee f_j\le s_i.$$

Convention

The half-open form $[s_j,f_j)$ means that a job finishing at time $t$ does not overlap a job starting at time $t$. Thus the same machine may process $i$ and then $j$ when

$$f_i\le s_j.$$