Earliness-tardiness scheduling problems, II: Deviation of completion times about a restrictive common due date

Earliness-tardiness scheduling problems, II: Deviation of completion times about a restrictive common due date

0.00 Avg rating0 Votes
Article ID: iaor19931346
Country: United States
Volume: 39
Issue: 5
Start Page Number: 847
End Page Number: 856
Publication Date: Sep 1991
Journal: Operations Research
Authors: , ,
Keywords: programming: dynamic
Abstract:

A compansion paper (Part I) considers the problem of minimizing the weighted earliness and tardiness of jobs scheduled on a single machine around a common due date, d, which is unrestrictively late. This paper (Part II) considers the problem of minimizing the unweighted earliness and tardiness of jobs, allowing the possibility that d is early enough to constrain the scheduling decision. The authors describe several optimality conditions. The recognition version of the problem is shown to be NP-complete in the ordinary sense, confirming a well known conjecture. Moreover, this complexity definition is precise, since the authors describe a dynamic programming algorithm which runs in pseudopolynomial time. This algorithm is also extremely efficient computationally, providing an improvement over earlier procedures, of almost two orders of magnitude in the size of instance that can be solved. Finally, the authors describe a special case of the problem which is polynomially solvable.

Reviews

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