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 with , it is

Equivalently, 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 machines, where is the depth of the instance.

If intervals overlap at time , then all jobs are active at the same time. No two of them can run on the same machine, so every schedule needs at least 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.