Modified due-date scheduling heuristic: Difference between revisions

Revision as of 23:48, 12 June 2021

Latest revision as of 13:37, 31 August 2023

(One intermediate revision by one other user not shown)

Line 1:

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,<ref>Kenneth R. Baker, J.W.M. Bertrand, ''A dynamic priority rule for scheduling against due-dates'', Journal of Operations Management Vol. 3, p37-42p 37–42, 1982.</ref> 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 ==

Line 18:

sortedTasks = list

processed = 0

'''while''' unsortedTasks '''isn'tis not empty'''

bestTask = unsortedTasks.getFirst()

bestMdd = mdd(processed, bestTask)

Line 156:

== Performance ==

Applying this heuristic will result in a sorted list of tasks which tardiness cannot be reduced by adjacent pair-wise interchange.<ref>J.C. Nyirenda, ''Relationship between the modified due date rule and the heuristic of Wilkerson and Irwin'', ORiON Vol. 17, p101-111p 101–111, 2001.</ref> MDD’s complexity is <math>O(n)</math>.

== Variations ==

There is a version of MDD called weighted modified due date (WMDD)<ref>John J. Kanet, Xiaoming Li, ''A Weighted Modified Due Date Rule For Sequencing To Minimize Weighted Tardiness'', Journal of Scheduling N° 7, p261-276p 261–276, 2004.</ref> which takes into account the weights. In such a case, the evaluation function is replaced by:

'''function''' wmdd(processed, task)