Interval Scheduling Problem

computation scheduling

Definition

Interval Scheduling Problem

The interval scheduling problem is a scheduling problem in which each job $j$ has a fixed half-open interval

$$I_j=[s_j,f_j)$$

with start time $s_j$ and finish time $f_j$.
A feasible schedule is a 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.$$

The objective is to maximise $|S|$.

Derivation

On a single machine, two jobs can both be scheduled exactly when their intervals are disjoint. Hence feasibility depends only on pairwise compatibility, not on where the jobs are placed. The optimisation problem is therefore

$$\underset{S\subseteq J}{\max }|S|\text{subject to}\forall i,j\in S,i\ne j:I_i\cap I_j=\varnothing .$$

A natural first choice is the job that leaves the most remaining time for later jobs. This is the compatible job with minimum finish time. Choosing by earliest start time is not sufficient, since a very early job may occupy the machine for a long time and block many short jobs.

Algorithms

Earliest Due Date First Algorithm

Definition

Earliest Due Date First Algorithm

The earliest due date first algorithm is a greedy algorithm that repeatedly schedules the available job with smallest due date.

In the interval scheduling problem, each job $j$ has fixed interval $[s_j,f_j)$ and its due date is its finish time $f_j$. The algorithm therefore chooses compatible jobs in increasing order of $f_j$.

Link to original