R.R. Weber, IEEE Trans. Auto. Control 38 166-169, 1993.
Abstract
A difficult queueing control problem concerns jobs that arrive to a buffer in a Poisson process and are to be assigned to $m$ processors of different speeds. These processors operate in parallel, and processing times are independent and exponentially distributed. Once a job is assigned to a free processor, it occupies that processor until completed and may not be reassigned to a faster processor if one becomes free. A reasonable conjecture, that remains unproven for more than two processors is that the policy that minimizes the mean waiting time is of threshold type --- meaning that if it assigns a job to the fastest available processor when the buffer has $k$ jobs, then it also does so if the processors are identically occupied and there are $k+1$ jobs in the buffer. This note discusses the conjecture, and shows that whether or not a job should be assigned to a processor can depend not only on the number in the queue and the speed of the fastest-available processor, but also on whether slower processors are busy or idle. A strengthened form of the conjecture is proposed.