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:
* 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)$.

Variations

There is a version of MDD called weighted modified due date (WMDD)John J. Kanet, Xiaoming Li, ''A Weighted Modified Due Date Rule For Sequencing To Minimize Weighted Tardiness'', Journal of Scheduling N° 7, p261-276, 2004. 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

{{reflist, colwidth=30em

See also

* Scheduling (computing)

Optimal scheduling
Processor scheduling algorithms