On a conjecture about assigning jobs to processors of differing speeds

摘要

A difficult control problem concerning jobs that arrive to a buffer in a Poisson process and are to be assigned to m processors of different speeds is treated. The 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 unproved for more than two processors is that the policy that minimizes the mean waiting time is of threshold type. This conjecture is discussed, and it is shown 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.