AN ALGORITHM FOR OPTIMAL LOAD BALANCING IN A MULTIPLE GI G/1 QUEUING SYSTEM/

The issue of optimal load balancing has been raised in several importa nt engineering fields such as the file management in a data base, the job control in a multiple processor system or the flow assignment in a packet switched data network. By modeling the subsystems as multiple GI/G/1 queues and applying known approximations and decomposition meth ods, the system mean response time is expressed as a function of the l oad allocation. To find the optimal load balancing, the convexity prop erty is first studied with respect to the type of the arrival process of the system. We give then an efficient algorithm which finds for the convex case the global and for the non-convex case a local minimum. S ome important properties of the multiple GI/G/1 queueing system are re vealed with several numerical examples.