Optimality proof of the Kise–Ibaraki–Mine algorithm

Optimality proof of the Kise–Ibaraki–Mine algorithm

0.00 Avg rating—0 Votes
Article ID: iaor20123922
Volume: 15
Issue: 3
Start Page Number: 289
End Page Number: 294
Publication Date: Jun 2012
Journal: Journal of Scheduling
Authors: , ,
Keywords: literature survey
Abstract:

Kise, Ibaraki and Mine (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 (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.

Reviews

Required fields are marked *. Your email address will not be published.