Interval Partitioning Problem

computation scheduling

Definition

Interval Partitioning Problem

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

$$I_j=[s_j,f_j)$$

and every job must be processed. A feasible schedule assigns each job to a machine so that no two jobs assigned to the same machine overlap.
The objective is to minimise the number of machines used.

Derivation

The interval scheduling problem asks for the largest compatible subset of intervals on one machine. Interval partitioning changes the objective: no interval may be discarded, so incompatibility must be resolved by adding machines.

Let a schedule be a function

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

where $\mu (j)$ is the machine assigned to job $j$. Feasibility means that 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).$$

The optimisation problem is therefore

$$\min k\text{subject to}\mu :J\to \{1,\dots ,k\}\text{ is feasible}.$$

Difference from Interval Scheduling

In interval scheduling, the number of machines is fixed to one and the goal is to select as many compatible jobs as possible.

In interval partitioning, every job must be scheduled and the goal is to minimise the number of machines.

Algorithms

Earliest Start Time First Algorithm

Definition

Earliest Start Time First Algorithm

The earliest start time first algorithm is a greedy algorithm for the interval partitioning problem. It processes jobs in increasing order of start time and assigns each job to an available machine.

For jobs $J=\{1,\dots ,n\}$ with intervals $[s_j,f_j)$, let $d$ be the depth of the instance. The algorithm uses machines $m_1,\dots ,m_d$ and assigns each job to a machine that is free at its start time.

Link to original