Depth (Interval Scheduling)

computation scheduling

Definition

Depth

The depth of an interval instance is the maximum number of intervals that overlap at any time.
For intervals $I_j=[s_j,f_j)$ with $j\in J$, it is

$$d=\underset{t}{\max }|\{j\in J:s_j\le t<f_j\}|.$$

Equivalently, $d$ is the largest number of jobs that are simultaneously active.

Lower bound

Machine lower bound

In the interval partitioning problem, every feasible schedule needs at least $d$ machines, where $d$ is the depth of the instance.

If $d$ intervals overlap at time $t$, then all $d$ jobs are active at the same time. No two of them can run on the same machine, so every schedule needs at least $d$ distinct machines.

Unavoidable Parallelism

Depth measures the unavoidable parallelism of an interval instance. For interval partitioning, it is both a lower bound and the optimum number of machines achieved by the earliest start time first algorithm.