Abstract
Kise, Ibaraki and Mine (Operations Research 26:121–126, 1978) give an O(n 2) time algorithm to find an optimal schedule for the single-machine number of late jobs problem with agreeable job release dates and due dates. Li, Chen and Tang (Operations Research 58:508–509, 2010) point out that their proof of optimality for their algorithm is incorrect by giving a counter-example. In this paper we give a correct proof of optimality for their algorithm.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Baptiste, P. (1999). An O(n 4) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Operations Research Letters, 24, 175–180.
Baptiste, P., Peridy, L., & Pinson, E. (2003). A branch and bound to minimize the number of late jobs on a single machine with release time constraints. European Journal of Operational Research, 144, 1–11.
Dauzere-Peres, A., & Sevaux, M. (2004). An exact method to minimize the number of tardy jobs in single machine scheduling. Journal of Scheduling, 7, 405–420.
Kise, H., Ibaraki, T., & Mine, H. (1978). A solvable case of the one-machine scheduling problem with ready and due times. Operations Research, 26, 121–126.
Lawler, E. L. (1990). A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Annals of Operations Research, 26, 125–133.
Lawler, E. L. (1994). Knapsack-like scheduling problems, the Moore–Hodgson algorithm and the “tower of sets” property. Mathematical and Computer Modelling, 20, 91–106.
Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362.
Li, S., Chen, Z.-L., & Tang, G. (2010). A note on the optimality proof of the Kise–Ibaraki–Mine algorithm. Operations Research, 58, 508–509.
Moore, J. M. (1968). An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15, 102–109.
Pinedo, M. (2002). Scheduling theory, algorithms, and systems (2nd ed.). Upper Saddle River: Prentice Hall.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Li, S., Chen, ZL. & Tang, G. Optimality proof of the Kise–Ibaraki–Mine algorithm. J Sched 15, 289–294 (2012). https://doi.org/10.1007/s10951-010-0210-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-010-0210-0