[PDF][PDF] NP-complete scheduling problems
JD Ullman - Journal of Computer and System sciences, 1975 - core.ac.uk
Journal of Computer and System sciences, 1975•core.ac.uk
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,..., tma x. If 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. The
scheduling problem is to minimize tmax under the constraint that if J~ J', then J'does not …
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,..., tma x. If 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. The
scheduling problem is to minimize tmax under the constraint that if J~ J', then J'does not …
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,..., tma x. If 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. The 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.
core.ac.uk
Showing the best result for this search. See all results