Socially and individually optimal routing of stochastic jobs in parallel processor systems

This paper considers a stochastic system where a fixed number of nonpreemptive jobs (no new jobs arrive) are to be processed on multiple nonidentical processors. Each processor has an increasing hazard rate processing time distribution and the processors are ordered in ascending order of their expected processing times. It is shown that the policy which minimizes the total expected delay of all the jobs (flowtime) has a threshold structure. This policy would utilize the fastest available processor only if its mean processing time is less than a critical number. Furthermore, a previously rejected processor must never be utilized at later times. This policy is also individually optimal in the sense that it minimizes the delay of each job subject to the constraint that processor preference is given to jobs at the head of the buffer. This result proves the conjecture of P.R. Kumar and J. Walrand regarding socially and individually optimal policies in parallel routing systems.