Dynamic load balancing in parallel queueing systems: stability and optimal control. (English) Zbl 1101.90017
Summary: We consider a system of parallel queues with dedicated arrival streams. At each decision epoch a decision-maker can move customers from one queue to another. The cost for moving customers consists of a fixed cost and a linear, variable cost dependent on the number of customers moved. There are also linear holding costs that may depend on the queue in which customers are stored. Under very mild assumptions, we develop stability (and instability) conditions for this system via a fluid model. Under the assumption of stability, we consider minimizing the long-run average cost. In the case of two-servers the optimal control policy is shown to prefer to store customers in the lowest cost queue. When the inter-arrival and service times are assumed to be exponential, we use a Markov decision process formulation to show that for a fixed number of customers in the system, there exists a level \(S\) such that whenever customers are moved from the high cost queue to the low cost queue, the number of customers moved brings the number of customers in the low cost queue to \(S\). These results lead to the development of a heuristic for the model with more than two servers.
MSC:
| 90B22 | Queues and service in operations research |
| 60K25 | Queueing theory (aspects of probability theory) |
| 90C40 | Markov and semi-Markov decision processes |
References:
| [1] | Bharadwaj, V.; Ghose, D.; Mani, V.; Robertazzi, T. G., Scheduling Divisible Loads in Parallel and Distributed Systems (1996), IEEE Press: IEEE Press New York |
| [2] | Boel, R. K.; van Schuppen, J. H., Distributed routing for load balancing, Proceedings of the IEEE, 77, 210-221 (1989) |
| [3] | Dai, J. G., On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models, Annals of Applied Probability, 5, 49-77 (1995) · Zbl 0822.60083 |
| [4] | J.G. Dai, Stability of Fluid and Stochastic Processing Networks, MaPhySto Miscellanea no. 9, 1999.; J.G. Dai, Stability of Fluid and Stochastic Processing Networks, MaPhySto Miscellanea no. 9, 1999. · Zbl 0923.76045 |
| [5] | Dai, J. G.; Meyn, S. P., Stability and convergence of moments for multiclass queueing networks via fluid models, IEEE Transactions on Automatic Control, 40, 1889-1904 (1995) · Zbl 0836.90074 |
| [6] | Eager, D. L.; Lazowska, E. D.; Zahorjan, J., Adaptive load sharing in homogeneous distributed systems, IEEE Transactions on Software Engineering, SE-12, 5, 662-675 (1986) |
| [7] | He, Q.; Neuts, M. F., Two M/M/1 queues with transfer of customers, Queueing Systems, 42, 377-400 (2002) · Zbl 1013.90044 |
| [8] | Koole, G., On the pathwise optimal Bernoulli routing policy for homogeneous parallel servers, Mathematics of Operations Research, 21, 469-476 (1996) · Zbl 0855.60095 |
| [9] | Levine, A.; Finkel, D., Load balancing in a multi-server queueing systems, Computational Operations and Research, 17, 17-25 (1990) · Zbl 0681.90042 |
| [10] | Lewis, M. E., Average optimal policies in a controlled queueing system with dual admission control, Journal of Applied Probability, 38, 2, 369-385 (2001) · Zbl 1127.90412 |
| [11] | Lippman, S., Applying a new device in the optimization of exponential queueing system, Operations Research, 23, 687-710 (1975) · Zbl 0312.60048 |
| [12] | Puterman, M. L., Markov Decision Processes: Discrete Stochastic Dynamic Programming (1994), John Wiley and Sons, Inc.: John Wiley and Sons, Inc. New York · Zbl 0829.90134 |
| [13] | Liu, Z.; Righter, R., Optimal load balancing on distributed homogeneous unreliable processors, Operations Research, 46, 563-573 (1998) · Zbl 0987.90046 |
| [14] | Meyn, S., The policy improvement algorithm for Markov decision processes, IEEE Transactions on Automatic Control, 42, 12, 1663-1680 (1997) · Zbl 0906.93063 |
| [15] | Shirazi, B. A.; Hurson, A. R.; Kavi, K. M., Scheduling and Load Balancing in Parallel and Distributed Systems (1995), IEEE Press: IEEE Press New York |
| [16] | Towsley, D.; Sparaggis, P. D.; Cassandras, C. G., Optimal routing and buffer allocation for a class of finite capacity queueing systems, IEEE Transactions on Automatic Control, 37, 1446-1551 (1993) · Zbl 0768.60090 |
| [17] | Wang, Y.-T.; Morris, R. J.T., Load sharing in distributed systems, IEEE Transactions on Computers, 34, 204-217 (1985) |
| [18] | Xia, C. H.; Michailidis, G.; Bambos, N., Dynamic on-line task scheduling on parallel processors, Performance Evaluation, 46, 219-233 (2001) · Zbl 1013.68038 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
