Job scheduling to minimize expected weighted flowtime on uniform processors (Q1111928): Difference between revisions

We consider a sequencing problem in which there are n jobs to be processed nonpreemptively on m nonidentical processors. The processing time of the j-th processor is exponentially distributed with rate \(\mu_ j\), where \(\mu_ 1\geq \mu_ 2\geq...\geq \mu_ m\). Job i incurs a holding cost at rate \(c_ i\) per unit time while still in the system, where \(c_ 1\geq c_ 2\geq...\geq c_ n\). We show that to minimize total expected holding costs (weighted flowtime), it is optimal to take the fastest (lowest indexed) available processor, say processor j, and assign job k to it if \(k>(\sum^{j}_{i=1}\mu_ i)/\mu_ j-j\geq k-1\). After each assignment the jobs are renumbered (so that job \(k+1\) becomes job k, etc.), and the procedure is repeated with the next fastest available processor, etc. Note that the policy does not depend on the values of the holding costs \(c_ i\). This result is a generalization of the result of \textit{A. K. Agrawala, E. G. Coffman, M. R. Garey} and \textit{S. K. Tripathi} [IEEE Trans. Comput. C-33, 351-356 (1984; Zbl 0528.68022)] for minimizing expected flowtime, i.e., minimizing total holding cost when the holding costs of all the jobs are the same. We give a simpler proof of the more general result.