Modified due-date scheduling heuristic

The modified due date heuristic is used in scheduling tasks to resources (for example, to answer the question "What order should we make sandwiches in, so as to please our customers?").

It assumes that the objective of the scheduling process is to minimise the chances that any one task will be completed late. This strategy is most relevant when completing all tasks carries a certainty that at least some of them will be completed late.

This forms the basis of an algorithm that attempts first to complete tasks early or on time, and second to complete tasks as soon as possible when the requested due date is unattainable: Given a list of tasks, with a range of due dates (d_j), and a range of times it takes to complete the tasks (p_j), then at any moment (t) you should do the task that has the smallest Modified Due Date. The Modified Due Date itself is the highest of either the due date, or the completion date if you started the task now:

mdd_j = max( d_j, t+p_j ).

Thus, if the due date of the PB and J is 5 minutes from now, but its time to complete is 6 minutes, the Modified Due Date of the PB and J is 6 minutes from now. Imagine a second customer is requesting that a Reuben be prepared in 7 minutes from now, but the Reuben takes 5 minutes to complete: in this case, the MDD of the Reuben is 7 minutes; the PB and J has a smaller MDD, and thus you should make the PB and J first, while the second customer waits patiently for the Reuben to be started. In this case, the PB and J is 1 minute late, and the Reuben is 4 minutes late. Both sandwiches are made late, but the total lateness is only 5 minutes. If you had made the Reuben first, the second customer may have gotten the sandwich early, but the first customer would have received their sandwich 6 minutes late.

See also