An O(n4) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs

An O(n4) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs

0.00 Avg rating—0 Votes
Article ID: iaor20021193
Country: Netherlands
Volume: 24
Issue: 4
Start Page Number: 175
End Page Number: 180
Publication Date: May 1999
Journal: Operations Research Letters
Authors:
Keywords: combinatorial analysis
Abstract:

We study the problem of minimizing, the preemptive case, the number of late jobs on a single machine (1 |pmtn,rj| Σ Uj). This problem can be solved by Lawler's algorithm whose time and space complexities are respectively O(n5) and O(n3). We propose a new dynamic programming algorithm whose complexities are respectively O(n4) and O(n2).

Reviews

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