IEICE TRANSACTIONS on Fundamentals
Single Machine Scheduling to Minimize the Maximum Lateness with Both Specific and Generalized Due Dates
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.3 pp.557-563
- Publication Date
- 1997/03/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Keisuke TANAKA, Milan VLACH, "Single Machine Scheduling to Minimize the Maximum Lateness with Both Specific and Generalized Due Dates" in IEICE TRANSACTIONS on Fundamentals,
vol. E80-A, no. 3, pp. 557-563, March 1997, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_3_557/_p
Copy
@ARTICLE{e80-a_3_557,
author={Keisuke TANAKA, Milan VLACH, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Single Machine Scheduling to Minimize the Maximum Lateness with Both Specific and Generalized Due Dates},
year={1997},
volume={E80-A},
number={3},
pages={557-563},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={March},}
Copy
TY - JOUR
TI - Single Machine Scheduling to Minimize the Maximum Lateness with Both Specific and Generalized Due Dates
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 557
EP - 563
AU - Keisuke TANAKA
AU - Milan VLACH
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 1997
AB - 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.
ER -
English
