NP-Complete Scheduling Problems* - Montana State University
JOURNAL OF COMPUTER AND SYSTEM SCIENCES 10, 384--393 (1975)
NP-Complete Scheduling Problems*
J. D. ULLMAN
Department of Electrical Engineering, Princeton University,~ Princeton, New Jersey 08540
Received May 16, 1973
We show that the problem of finding an optimal schedule for a set of jobs is NP-
complete even in the following two restricted cases. (1) All jobs require one time unit. (2) All jobs require one or two time units, and there are only two processor
resolving (in t h e negative a conjecture o f R. L. G r a h a m , Proc. SJCC, 1972,
pp. 205-218). As a consequence, the general preemptive scheduling problem is also NP-complete. These results are tantamount to showing that the scheduling problems mentioned are intractable.
I. INTRODUCTION
The scheduling problem is the following. We are given (1) a set S ~ {.[1 ,..., J~} of jobs, (2) a partial order -~ on S, (3) a weighting function W from S to the positive integers, giving the number of
time units required by each job, and (4) a number of processors, k. Informally, we may "execute" up to k jobs at each time unit t = 0, 1,..., tmax . I f job J is first executed at time t, then we assume it is executed at times t, t -}- 1,..., t + W ( J ) - 1, and at no other times. T h e scheduling problem is to minimize tmax under the constraint that if J ~ J', then J' does not begin execution until at least W(J) time units after f begins execution. The reader is referred to [1] for a survey of results on the scheduling problem.
* Work supported by NSF Grants GJ 474 and GJ 35570. A preliminary version of this paper
appeared in Operating Systems Review, October, 1973.
? Part of this work was done while the author was on leave at the University of California, Berkeley.
384
Copyright 9 1975 by Academic Press, Inc. All rights of reproduction in any form reserved.
NP-cOMPLETE SCHEDULING PROBLEMS
385
Following [2, 3], the class of problems known as NP-complete problems has received
heavy attention recently. A survey of results in this area can be found in [4], and some papers discussing problems closely related to scheduling are [5-7]. Informally, a problem is in ~V'~a if it is accepted by a nondeterministic T u r i n g machine in polynomial time. Many apparently hard combinatorial problem such as the "traveling
salesman" problem are in ./ff~a. An NP-complete problem P0 is one which enjoys the
following property. If P0 has a deterministic polynomial time algorithm, then so does every problem in JV'~a. Since for no N P - c o m p l e t e problem has a less than exponential time algorithm been found, showing a given problem to be NP-complete is tantamount to a proof that it has no polynomial time algorithm, and in fact, likely requires exponential time. For rigorous statements of the above, see [2-4].
Since a Turing machine may only accept or reject a tape, problems in ,Ug a are normally couched in a way that requires a yes-no answer. We may therefore express the time scheduling problem as follows.
(P1): General scheduling problem. Given a set S of n jobs, a partial order ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- unit 2 lesson 2 practice problems wishkah valley elementary high school
- name homework problems algebra 1 unit 2 complete the required problem
- 23 2 1 math 2 unit 2 2 quadratic word problems name 1 5 4 3 2 1
- the unit circle germanna community college
- np complete scheduling problems montana state university
- unit 2 narrative essays cengage
- grade 7 unit 2 practice problems open up resources rusd math
- bridges in mathematics grade 5 unit 2 module 3 math learning center
- grade 8 unit 2 practice problems open up resources rusd math
- social problems ii crisis conflicts challenges nuvhs
Related searches
- illinois state university online courses
- illinois state university programs
- illinois state university bachelor degrees
- illinois state university degree programs
- illinois state university online degree
- illinois state university online masters
- illinois state university summer schedule
- illinois state university summer classes
- illinois state university phd programs
- illinois state university online program
- illinois state university online degrees
- illinois state university masters programs