Inbook,
Scheduling jobs on heterogeneous processors
29, page 587--601. Springer Netherlands, (December 1991)
Abstract
We consider the problem of scheduling n jobs nonpreemptively on m processors to
minimize various weighted cost functions of job completion times. The time it takes processor
j to process a job is distributed exponentially with rate parameter/z j, independent of the
other processors. Associated with job i is a weight w t. There are no precedence constraints
and any job may be processed on any processor. Assume that /t1 >__/L2 > --- >/t,, and
w 1 > w 2 >__ --- > w n. Then for certain weighted cost functions, the optimal policy is such that
the processors can be partitioned into sets S 1 ..... Sn+ ~ such that if the fastest available
processor is in set St, i=l ..... n, then job i should be assigned to it, and if it is S~+l, it will
never be used. After each assignment the jobs are renumbered (so that job i + 1 becomes job i
if job i is assigned to a processor). The partitioning is independent of the job weights and the
states (busy or idle) of the processors. The optimal policy can be determined in at most
maxm, n steps. If all the weights are identical, the optimal policy reduces to a simple
threshold rule such that a job should be assigned to the fastest available processor, say j, if
there are more than Kj jobs waiting. Kj will depend on /~l ..... t~y but not on #j+l ..... /~,,.
The optimal policy is also individually optimal in the sense that it minimizes the cost for each
job i subject to the constraint that processors will first be offered to the jobs in the order
1, 2 ..... n.
We explicitly characterize the optimal policy for several specific examples of cost functions,
such as weighted flow time, weighted discounted flowtime, and weighted number of tardy
jobs.
