Schedule (Interval Scheduling)

computation scheduling

Definition

Schedule

A schedule for an interval scheduling instance is a choice of which fixed intervals are processed and, when there is more than one machine, an assignment of those intervals to machines.

For fixed intervals $I_j=[s_j,f_j)$, the schedule does not choose the start or finish time of an accepted job. Those times are already part of the instance.

Single machine

In the interval scheduling problem, there is one machine and not every job must be processed. A schedule is a selected set

$$S\subseteq J$$

such that no two selected intervals overlap:

$$\forall i,j\in S,i\ne j:f_i\le s_j\vee f_j\le s_i.$$

Multiple machines

In the interval partitioning problem, every job must be processed. A schedule is an assignment

$$\mu :J\to \{1,\dots ,k\}$$

where $\mu (j)$ is the machine assigned to job $j$. The assignment is feasible when jobs on the same machine are pairwise compatible:

$$\forall i,j\in J,i\ne j:\mu (i)=\mu (j)⟹(f_i\le s_j\vee f_j\le s_i).$$

Distinction

For general scheduling problems, a schedule may choose both a machine and a start time for each job. For interval scheduling, the intervals are fixed, so the schedule only chooses a compatible subset or a compatible machine assignment.