Minimize Lateness with EDD Scheduling

1. Defining Lateness and the Objective Function

Before we introduce the rule, we need to define our terms precisely. We are still in a single-machine environment where all jobs are available at time zero. However, each job j now has two key parameters:

• A processing time, $p_j$
• A due date, $d_j$, which is the time by which the job is expected to be completed.

It's important to distinguish a due date from a deadline. A deadline is typically hard; if a job misses its deadline, the order may be canceled. A due date is softer; missing it is undesirable and may incur costs, but the job is still required. Our focus here is on due dates.

From these parameters, we derive the following performance measures:

• Completion Time ($C_j$): The time at which job j finishes processing.
• Lateness ($L_j$): The difference between a job's completion time and its due date.
  $L_j=C_j-d_j$
  Lateness can be positive (the job is late), negative (the job is early), or zero (the job is on time).
• Maximum Lateness ($L_{max}$): The largest lateness value among all jobs. Our goal is to minimize this value.
  $L_{max}={\max }_j\{L_j\}$

In standard notation, this problem is written as 1 | | $L_{max}$.

The following image and video provide a clear introduction to these concepts and the problem we aim to solve.

2. The Earliest Due Date (EDD) Rule

The optimal solution to the 1 | | Lmax problem is found by applying the Earliest Due Date (EDD) rule, first established by James R. Jackson in 1955. The rule is as intuitive as its name suggests:

To minimize the maximum lateness, process the jobs in non-decreasing order of their due dates.

This greedy strategy prioritizes jobs that are due the soonest, regardless of how long they take to process.

The following segment of the video you just started will walk you through an example, transforming a suboptimal schedule into an optimal one using the EDD rule.

3. Proof of Optimality for the EDD Rule

Given your goal of writing a thesis, understanding the theoretical underpinnings of these classical results is essential. The optimality of the EDD rule can be proven using the same powerful technique we used for the SPT rule: the pairwise interchange argument.

The logic is as follows:

1. Assume there is an optimal schedule that is not an EDD schedule.
2. If it's not an EDD schedule, it must contain at least one pair of adjacent jobs, say i followed immediately by j, where job i has a later due date than job j ($d_i>d_j$). This is called an inversion.
3. We then show that by swapping jobs i and j, the maximum lateness of the schedule does not increase (and may even decrease).
4. By repeatedly swapping such inverted pairs, we can transform any optimal schedule into an EDD schedule without worsening the objective value.
5. Therefore, an EDD schedule must be optimal.

The following reading from the textbook by Böhm provides a formal, step-by-step proof of this theorem.

For a more visual and narrated explanation of a similar proof based on inversions, you can review the final section of the MisterCode video (from 07:20 onwards). Another excellent, in-depth explanation of the exchange argument is provided in the video "Greedy Exchange Arguments" (LINK), which you may find useful for a deeper dive.

4. Complexity and Related Objectives

• Computational Complexity: Just like the SPT rule, the EDD rule's main computational step is sorting the n jobs. This can be done in $O(n\log n)$ time. Thus, the 1 | | Lmax problem is efficiently solvable and belongs to the complexity class P.

• Maximum Tardiness ($T_{max}$): A closely related objective is minimizing maximum tardiness, where $T_j=\max (0,L_j)$. Since the tardiness function is non-decreasing with completion time, the same logic holds: the EDD rule is also optimal for minimizing maximum tardiness (1 | | Tmax). You can find a brief discussion of this in Section 2.6.1 of the "Chapter 2" text (LINK).

• Lawler's Algorithm: The EDD rule is a special case of a more general procedure called Lawler's Algorithm, which can solve problems of the form 1 | | g_max, where g_max is the maximum of some arbitrary non-decreasing cost functions of the completion times. This provides a broader theoretical context for why such greedy, backward-scheduling approaches work.

Conclusion

In this lesson, we have explored another fundamental single-machine scheduling problem. By simply changing the objective from total completion time to maximum lateness, a different priority rule—Earliest Due Date—emerged as optimal.

Key Takeaways:

• The problem of minimizing maximum lateness (1 | | Lmax) is a key scheduling objective focused on meeting deadlines.
• The optimal solution is found by applying the Earliest Due Date (EDD) rule: sequence jobs in non-decreasing order of their due dates.
• The EDD rule's optimality is rigorously proven using a pairwise interchange argument, showing that any schedule with an "inversion" can be improved or at least not worsened.
• The problem is polynomially solvable with a complexity of $O(n\log n)$.

Preview of the next lesson:
So far, we have addressed problems with simple, elegant greedy solutions. However, most real-world scheduling problems, including the FJSP you are researching, do not have such rules. To solve them, we need more powerful and general techniques. In the next lesson, we will make a significant step in that direction by learning how to formulate a single-machine scheduling problem as a Mixed-Integer Linear Program (MILP). This will be our first introduction to mathematical modeling for scheduling, a critical skill for your thesis work.