PREEMPTIVE SCHEDULING ALGORITHMS WITH NESTED PROCESSING SET RESTRICTION
We consider the problem of preemptively scheduling n independent jobs {J(1),J(2), ..., J(n)} on m parallel machines {M(1),M(2), ..., M(m)}, where each job J(j) can only be processed on a prespecified subset M(j) of machines called its processing set. The machines are linearly ordered, and the processing set of J(j) is specified by two machine indexes a(j) and b(j); i.e., M(j) = {M(aj),M(aj+1), ..., M(bj)}. The processing sets are nested; i.e., for i not equal j, we have M(i) subset of M(j), or M(j) subset of M(i),or M(j) boolean AND M(i) = phi..Our goal is to minimize the makespan. We first give an O(n logn)-time algorithm to find an optimal schedule. We then give an O(mn + nlogn)-time algorithm to find a maximal schedule, where a schedule is said to be maximal if it processes as much work as any other schedule in any time interval [0, t], t>0.
preemptive scheduling nested processing set inclusive processing set makespan minimization polynomial-time algorithms