Scheduling jobs on heterogeneous processors

We consider the problem of schedulingn jobs nonpreemptively onm processors to minimize various weighted cost functions of job completion times. The time it takes processorj to process a job is distributed exponentially with rate parameter_j, independent of the other processors. Associated with jobi is a weightw_i. There are no precedence constraints and any job may be processed on any processor. Assume that_{1 2}...µ_m andw₁w₂...w_n. Then for certain weighted cost functions, the optimal policy is such that the processors can be partitioned into setsS₁, ...,S_n+1 such that if the fastest available processor is in setS_i,i=1, ...,n, then jobi should be assigned to it, and if it isS_n+1, it will never be used. After each assignment the jobs are renumbered (so that jobi+1 becomes jobi if jobi 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 max {m, 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, sayj, if there are more thanK_j jobs waiting.K_j will depend on₁, ...,_j but not on_j+1, ...,µ_m. The optimal policy is also individually optimal in the sense that it minimizes the cost for each jobi 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.