ADAPTIVE OPTIMAL LOAD BALANCING IN A NONHOMOGENEOUS MULTISERVER SYSTEM WITH A CENTRAL JOB SCHEDULER

We consider a model comprising several servers, with possibly different service speeds, each equipped with its own queue. Each server receives a dedicated arrival stream of jobs; there is also a stream of generic jobs that arrive to a job scheduler and can be individually allocated to any of the servers. We show that if the arrival streams are all Poisson, and all jobs have the same exponentially distributed service requirements, then the probabilistic splitting of the generic stream that minimizes the average job response time is such that it balances the server idle times in a weighted least squares sense, where the weighting coefficients are related to the service speeds of the servers. The corresponding result holds for nonexponentially distributed service times, if the service speeds are all equal. We use this result to develop adaptive quasi-static algorithms for allocating jobs in the generic arrival stream, when the load parameters (arrival rates, mean service times) are unknown. The algorithms utilize server idle time measurements which are sent periodically to the central job scheduler. We develop a model for these measurements, and use the result mentioned above to cast the problem into one of finding a projection of the root of an affine function, when only noisy values of the function can be observed. We use standard techniques to develop algorithms for this latter problem, and use simulations to demonstrate their performance in the original queueing problem. © 1990 IEEE