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 is not 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:
a due date: The time after which the plane is expected to have taken off a processing time: The amount of time the plane takes to take off a weight: An arbitrary value to specify the priority of the flight. 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 O ( n ) {\displaystyle O(n)} .
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)
References
See also Scheduling (computing)
