Paper Info
Title
Preemptive Scheduling of Two Uniform Machines to Minimize the Number of Late Jobs
Abstract
<P>Suppose that n jobs, each with a specified processing requirement and due date, are to be preemptively scheduled for processing by a number of parallel machines, with the objective of maximizing the number of jobs that are completed by their due dates. It is known that this scheduling problem is NP-hard, even for identical machines, if the number of machines is variable, that is, specified as part of the problem instance. However, if the machine environment consists of a fixed set of uniform machines, the problem can be solved in polynomial time. An O(n3) algorithm is presented for the special case of two uniform machines. The running time of this algorithm becomes O(Wn2), where W is the sum of the job weights, for the more general problem in which it is desired to minimize the weighted number of late jobs. A fully polynomial approximation scheme is also presented for the weighted case.</P>
Year
DOI
Venue
1989
10.1287/opre.37.2.314
Operations Research
Field
DocType
Volume
Mathematical optimization,Preemption,Job shop scheduling,Polynomial,Scheduling (computing),Computer science,Algorithm,Minimisation (psychology),Minification,Time complexity,Special case
Journal
37
Issue
ISSN
Citations 
2
0030-364X
15
PageRank 
References 
Authors
1.91
2
2
Name
Order
Citations
PageRank
E. L. Lawler11102585.42
C. U. Martel2508.19