On the complexity of generalized due date scheduling problems (Q1175769)

A generalized due date scheduling problem is a problem for which due dates are not associated with the individual jobs, but are specified according to the position in which a job is completed. The authors define the generalized due date counterpart of most of the well-known single and multiple machine scheduling problems. The complexity of several of these problems is determined. Surprisingly some of the NP-hard problems become polynomially solvable in the case of generalized due dates. The paper contains a list of the complexity results and also a list of problems with open complexity status.