Modified due-date scheduling heuristic: Difference between revisions

Revision as of 15:44, 19 January 2016

Latest revision as of 13:37, 31 August 2023

(11 intermediate revisions by 10 users not shown)

Line 1:

The '''modified due-date''' (MDD) scheduling heuristic is a [[greedy heuristic]] used to solve the {{Lien|fr=SMTWTP|lang=en|trad=Singlesingle-machine scheduling|texte=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 {{Lien|fr=Problème NP-complet|lang=en|trad=NP-hard|texte= [[NP-hard}}]] single machine total-weighted tardiness problem. This problem is centered around reducing the global tardiness of a list of tasks which are characterisedcharacterized by their processing time, due date and weight by re-ordering them.

== Algorithm ==

=== Principle ===

This heuristic works the same way as other {{Lien|fr=Algorithme glouton|lang=en|trad=Greedy algorithm|texte=greedy heuristic}}algorithms. At each iteration, it finds the next job to schedule and add it to the list,. thisThis operation is repeated until no jobs are left unscheduled.</br> 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.

It have a lot in common with [[EDD]] except that it takes into account the partial sequence of job that have been already constructed where EDD only looks at the jobs due dates.

=== Implementation ===

Here is an implementation of the MDD algorithm in pseudo-code.</br> It takes in an unsorted list of tasks and return the list sorted by increasing modified due date:

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'tis 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.</br> Each flight is characterized by:

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.</br> For this example we will use the following values:

For this example we will use the following values:

{| class="wikitable alternance"

Line 68 ⟶ 64:

| 4

| 14

| 166

| 8

|-

Line 74 ⟶ 70:

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 it’sits due date:

{| class="wikitable alternance"

Line 95 ⟶ 92:

|}

The flight with the smallest MDD (Flight n° 3) is then processed, and the new modified due date is computed.</br> The current time is now 5.

The current time is now 5.

{| class="wikitable alternance"

Line 122 ⟶ 118:

| 4

| 14

| 166

| 14

|-

|}

The operation is repeated until no more flights are left unscheduled.</br />

We obtain the following results:

Line 147 ⟶ 143:

| 4

| 14

| 166

|-

| 2

Line 155 ⟶ 151:

|}

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 .<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)</brmath>.

MDD’s complexity is <math>O(n)</math>.

== Variations ==

There is a version of MDD called WMDD (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)

'''return''' (1 / task.weight) * '''max'''(task.processTime, task.dueDate - processed)

== References ==

{{reflist|colwidth=30em}}

==See also==

* [[Scheduling (computing)]]

[[Category:SchedulingOptimal algorithmsscheduling]]

[[Category:Processor scheduling algorithms]]

{{compsci-stub}}