Earliest Start Time First Algorithm

computation scheduling

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.

Principle

In interval partitioning, every job must be scheduled. A machine is available for job $j$ exactly when the last job assigned to that machine finishes no later than $s_j$.

Processing jobs by increasing start time makes the decision local: when job $j$ is considered, all jobs that could already occupy a machine at time $s_j$ have already been seen.

Algorithm

Fixed intervals

Given jobs $J=\{1,\dots ,n\}$ with intervals $[s_j,f_j)$:

sort jobs by increasing s[j];
machines = priority queue ordered by finish time;
 
for (j in jobs) {
    m = machine with minimum finish time;
 
    if (m exists && finish[m] <= s[j]) {
        assign j to m;
        finish[m] = f[j];
        update m in machines;
    } else {
        open new machine m_new;
        assign j to m_new;
        finish[m_new] = f[j];
        insert m_new into machines;
    }
}

The invariant is that the priority queue stores one key per open machine, namely the finish time of the last job assigned to that machine.

Feasibility

The algorithm never needs more than $d$ machines

Let $d$ be the depth of the interval instance. The earliest start time first algorithm can always assign the next job to one of $d$ machines.

Contradiction $j$ with start time $s_j$ because all $d$ machines are in use.

Assume, toward a contradiction, that the algorithm fails when assigning some job

Since jobs are processed by increasing start time, each job currently occupying one of the $d$ machines has start time at most $s_j$.
Since each of those machines is unavailable for $j$, each occupying job has finish time greater than $s_j$.

Thus, for each occupied machine, there is a job whose interval contains $s_j$ in the half-open sense:

$$s_i\le s_j<f_i.$$

Together with job $j$, this gives $d+1$ jobs active at time $s_j$:

$$|\{i\in J:s_i\le s_j<f_i\}|\ge d+1.$$

This contradicts that the depth is $d$. Therefore, some machine is always available among $m_1,\dots ,m_d$. $\square$

Optimality

Optimality for interval partitioning

Earliest start time first uses the minimum possible number of machines.

Depth lower bound depth, every feasible schedule needs at least $d$ machines.

By the lower bound from

By feasibility, earliest start time first uses at most $d$ machines.
Therefore it uses exactly $d$ machines, which is optimal. $\square$

Scope

Earliest start time first is optimal for interval partitioning with fixed intervals and objective of minimising the number of machines. It is not the same problem as selecting a maximum compatible subset on one machine.

Complexity

Sorting by start time takes $O(n\log n)$. Each priority queue operation takes $O(\log n)$, and there is a constant number of priority queue operations per job. Thus the total running time is

$$O(n\log n)$$