Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs |
| |
| Authors: | Nodari Vakhania |
| |
| Institution: | aScience Faculty, State University of Morelos, Mexico;bInst. of Computational Math., Georgian Academy of Sciences, Georgia |
| |
| 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: | Algorithm Scheduling Release time Late job Time complexity |
| 本文献已被 ScienceDirect 等数据库收录！ |
