The authors 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 μj, independent of the other processors. Associated with job i is a weight wi. There are no precedence constraints and any job may be processed on any processor. Assume that μ1≥μ2≥ëëë≥μm and w1≥w2≥ëëë≥wn. Then for certain weighted cost functions, the optimal policy is such that the processors can be partitioned into sets S1,..,SnÅ+1 such that if the fastest available processor is in set Si, i=1,...,n, then job i should be assigned to it, and if it is SnÅ+1, 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 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, say j, if there are more than Kj jobs waiting. Kj will depend on μ1,...,μj but not on μjÅ+1,...,μm. 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. The authors explicitly characterize the optimal poliyc for several specific examples of cost functions, such as weighted flow time, weighted discounted flowtime, and weighted number of tardy jobs.
