Earliest Due Date First Algorithm

computation scheduling

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$.

Principle

For fixed intervals, accepting a job consumes the machine until its finish time. If two candidate jobs are both currently compatible and

$$f_i\le f_j,$$

then choosing $i$ leaves at least as much time for every later compatible job as choosing $j$. This is the local reason why the earliest finishing job is safe.

Algorithm

Fixed intervals

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

sort jobs by increasing f[j];
S = {};
t = -infinity;
 
for (j in jobs) {
    if (s[j] >= t) {
        S.add(j);
        t = f[j];
    }
}

The invariant is that $t$ is the finish time of the last selected job, and $S$ is a compatible set.

Correctness

Optimality for interval scheduling

For the interval scheduling objective $\max |S|$, earliest due date first returns an optimal solution.

Exchange argument $G=(g_1,\dots ,g_k)$ be the greedy solution. Let $O=(o_1,\dots ,o_t)$ be an optimal compatible solution, ordered by increasing finish time.

Let

Consider the first position $r$ where $G$ and $O$ differ, after replacing earlier positions so that $g_i=o_i$ for $i<r$.
At this point, both $g_r$ and $o_r$ are compatible with the common prefix. Since the algorithm chooses the compatible job with earliest due date,

$$f_{g_r}\le f_{o_r}.$$

Replace $o_r$ by $g_r$. Every later job in $O$ starts after $f_{o_r}$, and therefore also starts after $f_{g_r}$. The replacement preserves feasibility and does not change the number of jobs.

Repeating this exchange transforms some optimal solution into one whose prefix is the greedy solution. When the greedy algorithm stops, no job remains that is compatible with its prefix. Hence no optimal continuation can contain more jobs, so $|G|=|O|$. $\square$

Complexity

Sorting by due date takes $O(n\log n)$. The greedy scan takes $O(n)$, so the total running time is

$$O(n\log n).$$

Limitation

Scope

Earliest due date first is optimal for unweighted interval scheduling with fixed intervals and objective $\max |S|$. Different scheduling objectives, such as minimising maximum lateness or maximising total weight, require different proofs or different algorithms.