Article ID Journal Published Year Pages File Type
1142760 Operations Research Letters 2009 6 Pages PDF
Abstract
We give a direct combinatorial O(n3logn) algorithm for minimizing the number of late jobs on a single machine when jobs have release times and preemptions are allowed. Our algorithm improves the earlier O(n5) and O(n4) dynamic programming algorithms for this problem.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs
Authors
,