1-1hit |
We consider single machine problems involving both specific and generalized due dates simultaneously. We show that a polynomial time algorithm exists for the problem of minimizing max {Lmax, LHmax}, where Lmax and LHmax are the maximum lateness induced by specific and generalized due dates, respectively. We also show that a simple efficient algorithm exists for the problem of minimizing the maximum lateness induced by due dates which are natural generalization of both specific and generalized due dates. In addition to the algorithmic results above, we show that the problems of minimizing max {LHmax, -Lmin} and max{Lmax, -LHmin} are NP-hard in the strong sense, where Lmin and LHmin are the minimum lateness induced by specific and generalized due dates, respectively.