An improved dynamic programming algorithm for the single-machine mean absolute deviation problem with a restrictive common due date

An improved dynamic programming algorithm for the single-machine mean absolute deviation problem with a restrictive common due date

0.00 Avg rating0 Votes
Article ID: iaor19981172
Country: Netherlands
Volume: 17
Issue: 3
Start Page Number: 149
End Page Number: 152
Publication Date: Apr 1995
Journal: Operations Research Letters
Authors: ,
Keywords: programming: dynamic
Abstract:

In 1991, Hall et al. showed that the problem of minimizing the mean earliness and tardiness of n jobs scheduled on a single machine around a restrictive common due date is NP-complete. They proposed a pseudo-polynomial dynamic programming algorithm, called Optcet, for identifying an optimal schedule. This paper points out that two of the three subroutines in Optcet can be eliminated and, consequently, the total computational effort can be reduced significantly.

Reviews

Required fields are marked *. Your email address will not be published.