On a conjecture about assigning jobs to processors of different speeds

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.

back to list of papers