Earliness–tardiness scheduling around almost equal due dates

Earliness–tardiness scheduling around almost equal due dates

0.00 Avg rating0 Votes
Article ID: iaor19982704
Country: United States
Volume: 9
Issue: 1
Start Page Number: 92
End Page Number: 99
Publication Date: Dec 1997
Journal: INFORMS Journal On Computing
Authors: ,
Abstract:

The just-in-time concept in manufacturing has aroused interest in machine scheduling problems with earliness–tardiness penalties. In particular, common due date problems, which are structurally less complicated than problems with general due dates, have emerged as an interesting and fruitful field of research. We prove that so-called almost common due date problems, in which the due date dj and processing time pj of each job Jj (J=1, …, n) are such that dj ∈ [D, D + pj] for some constant D, are structurally less complicated also. Our main contribution is an O(n2) time dynamic programming algorithm for the almost common due date problem with large D. The dynamic programming algorithm is interesting in its own right, since the optimality principle behind it applies to other common due date and almost common due date problems as well.

Reviews

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