Modified due-date scheduling heuristic

The modified due-date (MDD) scheduling heuristic is a greedy heuristic used to solve the single machine total weighted tardiness problem (SMTWTP).
Presentation.
The modified due date scheduling is a scheduling heuristic, created in 1982 by Baker and Bertrand, used to solve the NP-hard single machine total-weighted tardiness problem. This problem is centered around reducing the global tardiness of a list of tasks which are characterized by their processing time, due date and weight by re-ordering them.
Algorithm.
Principle.
This heuristic works the same way as other greedy algorithms. At each iteration, it finds the next job to schedule and add it to the list. This operation is repeated until no jobs are left unscheduled. MDD is similar to the earliest due date (EDD) heuristic except that MDD takes into account the partial sequence of job that have been already constructed, whereas EDD only looks at the jobs' due dates.
Implementation.
Here is an implementation of the MDD algorithm in pseudo-code. It takes in an unsorted list of tasks and return the list sorted by increasing modified due date:
 function mdd(processed, task)
 return max(processed + task.processTime, task.dueDate)
 function mddSort(tasks)
 unsortedTasks = copy(tasks)
 sortedTasks = list
 processed = 0
 while unsortedTasks isn't empty
 bestTask = unsortedTasks.getFirst()
 bestMdd = mdd(processed, bestTask)
 for task in unsortedTasks
 mdd = mdd(processed, task)
 if mdd < bestMdd then
 bestMdd = mdd
 bestTask = task
 sortedTasks.pushBack(bestTask)
 unsortedTasks.remove(bestTask)
 processed += bestTask.processTime
 return sortedTasks
Practical example.
In this example we will schedule flight departures. Each flight is characterized by:
We need to find an order for the flight to take off that will result in the smallest total weighted tardiness. For this example we will use the following values:
In the default order, the total weighted tardiness is 136.
The first step is to compute the modified due date for each flight. Since the current time is 0 and, in our example, we don’t have any flight whose due date is smaller than its processing time, the mdd of each flight is equal to its due date:
The flight with the smallest MDD (Flight n° 3) is then processed, and the new modified due date is computed. The current time is now 5.
The operation is repeated until no more flights are left unscheduled.
We obtain the following results:
In this order, the total weighted tardiness is 92.
This example can be generalized to schedule any list of job characterized by a due date and a processing time.
Performance.
Applying this heuristic will result in a sorted list of tasks which tardiness cannot be reduced by adjacent pair-wise interchange. MDD’s complexity is formula_1.
Variations.
There is a version of MDD called weighted modified due date (WMDD) which takes into account the weights. In such a case, the evaluation function is replaced by:
 function wmdd(processed, task)
 return (1 / task.weight) * max(task.processTime, task.dueDate - processed)