| Real Time Systems: Notes |
These notes are based on the survey paper "Complexity Results for Multiprocessor Scheduling Under Resource Constraints", by Garey and Johnson, published in 1975.
The problems whose complexity is discussed in this survey paper are all for non-periodic sets of jobs, i.e., where a finite set of jobs arrive at time zero, and the problem is to determine whether they can all be completed by a specified time D.
The periodic scheduling problem is certainly no easier, since the case considered here is equivalent to the special case where all tasks have the same period, D.
These problems are all for nonpreemptive (with respect to CPU) scheduling. However the cases where there are nonpreemptable resources (r > 0) or precedence relations (p nonempty), I believe one can show that it makes no difference whether the CPU can be preempted.
one-processor, one resource, arbitrary times and DEADLINES (Mok, 1983)
MS[n=1, r=1, < empty, arbitrary Ci, TIGHT DEADLINES]
Proof is by showing the 3-PARTITION problem, which is proven elsewhere to be NP-complete, is reducible to the one-processor nonpreemptive scheduling problem.
A 3-PARTITION problem is a triple (m,B,W), where
This problem can be "solved" iff there exists a partition of W into m disjoint sets S(1), ..., S(m) such that the combined weights of the elements in each set is B.
We show how to transform an arbitrary 3-PARTITION problem (m,B,W) into a scheduling problem with 3m+1 periodic jobs J(i).
For each weight w(i), let J(i) be a periodic process of the form
Lock(X);
compute for C(i) time units
Unlock(X);
with period and deadline p(i) = d(i) = mB + m, and compute-time C(i)=w(i).
In addition, let J(0) be a periodic process of the same form, with p(0) = B+1, d(0) = c(0) = 1.
This transformation "obviously takes polynomial time".
J(0) must be run in the intervals [t,t+1], where t=0 (mod B+1).
This leaves m slots of time, each of length B, in [0,mB+m].
|J0|---------|J0|---------|J0|---...----|J0|---------|J0| 0 \___B___/ mB+m
There can be no idle time in any of these slots, since all jobs must complete by time mB+m, and w(1) + ... + w(3m) = mB.
None of the jobs can be split over more than one slot, since that would block J(0) from executing on time.
Thus, a feasible schedule exists for [0,mB+m] iff the 3-PARTITION problem can be solved.
This shows the scheduling problem is NP-hard.
It does not appear to be in NP, so we can't say it is NP-complete.
To see this, suppose we are given an arbitrary scheduling problem X=(n,P,D,C), where P=(p(1),...,p(n)) are the periods, D=(d(1),...,d(n)) are the deadlines, and C=(C(1),...,C(n)) are the compute times of n jobs.
If we guess a schedule for X, the length of the schedule (major cycle) can be as long as p(1)*...*p(n), which is exponentially large with respect to the length of the problem X.
In order to verify that this schedule works, we would need to look at all of it, so it seems we MIGHT need exponential time; at least, this approach does not lead to a polynomial-time algorithm.
The deadline requirement on J(0) in the proof above is absolutely tight. The Liu & Layland results on preemptive periodic scheduling assume that deadline = period. This naturally leads one to wonder whether the proof above can be modified so that all jobs have p(i)=d(i).
(Anyone in the class who does this and turns it in will receive extra credit, equal to a 20% increment in the midterm examination score.)
|
© 1998, 2003 T. P. Baker.
No part of this publication may be reproduced, stored in a retrieval system, or
transmitted in any form or by any means without written permission.
$Id: complexity.html,v 1.2 2008/08/25 11:18:48 baker Exp baker $ |