Single Machine Scheduling to Minimize the Maximum Lateness with Both Specific and Generalized Due Dates (Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems)

概要

論文の詳細を見る
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{L<max>, L^H<max>}, where L<max> and L^H<max> 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{L^H<max>, -L<min>} and max{L<max>, -L^H<min>} are NP-hard in the strong sense, where L<min> and L^H<min> are the minimum lateness induced by specific and generalized due dates, respectively.
社団法人電子情報通信学会の論文
1997-03-25