A revised proof of the optimality for the Kise–Ibaraki–Mine algorithm

For the problem of scheduling n‐jobs on one‐machine with agreeable job release dates and due dates to minimize the number of late jobs, Kise, Ibaraki and Mine (Oper. Res. 26:121–126, 1978) gave an O(n ²)‐time algorithm and proved its optimality by four lemmas. Li et al. (2010) gave a counter‐example to show that one lemma is invalid in some case and therefore the optimality is also invalid. In this paper, we revise the lemma and prove that the algorithm is still valid.