Control of parallel non-observable queues: asymptotic equivalence and optimality of periodic policies. (English) Zbl 1336.60175

Summary: We consider a queueing system composed of a dispatcher that routes jobs to a set of non-observable queues working in parallel. In this setting, the fundamental problem is which policy should the dispatcher implement to minimize the stationary mean waiting time of the incoming jobs. We present a structural property that holds in the classic scaling of the system where the network demand (arrival rate of jobs) grows proportionally with the number of queues. Assuming that each queue of type \(r\) is replicated \(k\) times, we consider a set of policies that are periodic with period \(k\sum_{r}p_{r}\) and such that exactly \(p_{r}\) jobs are sent in a period to each queue of type \(r\). When \(k\to\infty\), our main result shows that all the policies in this set are equivalent, in the sense that they yield the same mean stationary waiting time, and optimal, in the sense that no other policy having the same aggregate arrival rate to all queues of a given type can do better in minimizing the stationary mean waiting time. This property holds in a strong probabilistic sense. Furthermore, the limiting mean waiting time achieved by our policies is a convex function of the arrival rate in each queue, which facilitates the development of a further optimization aimed at solving the fundamental problem above for large systems.


60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
93E20 Optimal stochastic control
90C25 Convex programming
Full Text: DOI arXiv Euclid


[1] Altman, E., Gaujal, B., and Hordijk, A., Balanced sequences and optimal routing. J. ACM , 47(4):752-775, July 2000. · Zbl 1327.68180 · doi:10.1145/347476.347482
[2] Altman, E., Gaujal, B., and Hordijk, A., Multimodularity, convexity, and optimization properties. Math. Oper. Res. , 25(2):324-347, 2000. · Zbl 0977.90005 · doi:10.1287/moor.25.2.324.12230
[3] Anselmi, J. and Gaujal, B., Optimal routing in parallel, non-observable queues and the price of anarchy revisited. In International Teletraffic Congress , pages 1-8, 2010.
[4] Anselmi, J. and Gaujal, B., The price of forgetting in parallel and non-observable queues. Perform. Eval. , 68(12):1291-1311, Dec. 2011.
[5] Asmussen, S., Applied Probability and Queues . Wiley, 1987. · Zbl 0624.60098
[6] Baccelli, F. and Brémaud, P., Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences , volume 26. springer, 2003. · Zbl 1021.60001
[7] Bar-Noy, A., Bhatia, R., Naor, J., and Schieber, B., Minimizing service and operation costs of periodic scheduling (extended abstract). In H. J. Karloff, editor, SODA , pages 11-20. ACM/SIAM, 1998. · Zbl 0929.68011
[8] Bell, C. H. and Stidham, S., Individual versus social optimization in the allocation of customers to alternative servers. Management Science , 29(7):831-839, 1983. · Zbl 0514.90029 · doi:10.1287/mnsc.29.7.831
[9] Bhat, U. N., An Introduction to Queueing Theory: Modeling and Analysis in Applications . Birkhauser Verlag, 2008. · Zbl 1152.60001
[10] Bhulai, S., Farenhorst-Yuan, T., Heidergott, B., and van der Laan, D., Optimal balanced control for call centers. Annals OR , 201(1):39-62, 2012. · Zbl 1260.90116 · doi:10.1007/s10479-012-1215-1
[11] Billingsley, P., Convergence of Probability Measures . Wiley Series in Probability and Statistics, 1999. · Zbl 0944.60003
[12] Borovkov, A., Stochastic Processes in Queueing Theory . Applications of Mathematics. Springer-Verlag, 1976. · Zbl 0319.60057
[13] Borst, S. C., Optimal probabilistic allocation of customer types to servers. ACM SIGMETRICS ’95/PERFORMANCE ’95, pages 116-125, New York, NY, USA, 1995. ACM. · Zbl 0845.68012
[14] Combé, M. B. and Boxma, O. J., Optimization of static traffic allocation policies. Theor. Comput. Sci. , 125(1):17-43, 1994. · Zbl 0795.68024 · doi:10.1016/0304-3975(94)90292-5
[15] Doob, J., Stochastic Processes . Wiley Publications in Statistics. John Wiley & Sons, 1953. · Zbl 0053.26802
[16] Gaujal, B., Hyon, E., and Jean-Marie, A., Optimal routing in two parallel queues with exponential service times. Discrete Event Dynamic Systems , 16:71-107, January 2006. · Zbl 1121.90035 · doi:10.1007/s10626-006-6179-3
[17] Gun, L., Jean-Marie, A., Makowski, A. M., and Tedijanto, T., Convexity results for parallel queues with bernoulli routing. Technical Report, TR 1990-52. University of Maryland, USA, 1990.
[18] Hajek, B., The proof of a folk theorem on queuing delay with applications to routing in networks. J. ACM , 30(4):834-851, Oct. 1983. · Zbl 0627.68035 · doi:10.1145/2157.322409
[19] Hajek, B., Extremal splitting of point processes. Math. Oper. Res. , 10:543-556, 1986. · Zbl 0581.60090 · doi:10.1287/moor.10.4.543
[20] Harchol-Balter, M., Scheller-Wolf, A., and Young, A. R., Surprising results on task assignment in server farms with high-variability workloads. In SIGMETRICS/Performance , pages 287-298. ACM, 2009.
[21] Hordijk, A., Koole, G. M., and Loeve, J. A., Analysis of a customer assignment model with no state information. In Probability in the Engineering and Informational Sciences , volume 8, pages 419-429, 1994.
[22] Hordijk, A. and van der Laan, D., Periodic routing to parallel queues and billiard sequences. Mathematical Methods of Operations Research , 59(2):173-192, 2004. · Zbl 1138.90361 · doi:10.1007/s001860300322
[23] Humblet, P., M. I. of Technology, Laboratory for Information, and D. Systems, Determinism Minimizes Waiting Time in Queues . LIDS-P-. Laboratory for Information and Decision Systems, 1982.
[24] Javadi, B., Kondo, D., Vincent, J.-M., and Anderson, D. P., Discovering statistical models of availability in large distributed systems: An empirical study of seti@home. IEEE Trans. Parallel Distrib. Syst. , 22(11):1896-1903, 2011.
[25] Javadi, B., Thulasiraman, P., and Buyya, R., Cloud resource provisioning to extend the capacity of local resources in the presence of failures. In HPCC-ICESS , pages 311-319. IEEE Computer Society, 2012.
[26] Lindley, D. V., The theory of queues with a single server. Mathematical Proceedings of the Cambridge Philosophical Society , 48:277-289, 1952. · Zbl 0046.35501 · doi:10.1017/S0305004100027638
[27] Liu, Z. and Righter, R., Optimal load balancing on distributed homogeneous unreliable processors. Journal of Operations Research , 46(4):563-573, 1998. · Zbl 0987.90046 · doi:10.1287/opre.46.4.563
[28] Loynes, R., The stability of a queue with nonindependent interarrival and service times. Mathematical Proceedings of the Cambridge Philosophical Society , 58:497-520, 1962. · Zbl 0203.22303 · doi:10.1017/S0305004100036781
[29] Makowski, A., On an elementary characterization of the increasing convex ordering, with an application. Journal of Applied Probability , 31:834-840, 1994. · Zbl 0821.60024 · doi:10.2307/3215161
[30] Neely, M. J. and Modiano, E., Convexity in queues with general inputs. IEEE Transactions on Information Theory , 51(2):706-714, 2005. · Zbl 1308.90050 · doi:10.1109/TIT.2004.840859
[31] Puterman, M. L., Markov Decision Processes: Discrete Stochastic Dynamic Programming . John Wiley & Sons, Inc., New York, NY, USA, 1st edition, 1994. · Zbl 0829.90134
[32] Sethuraman, J. and Squillante, M. S., Optimal stochastic scheduling in multiclass parallel queues. SIGMETRICS ’99, pages 93-102, New York, NY, USA, 1999. ACM.
[33] Shaked, M. and Shanthikumar, J. G., Stochastic Orders and Their Applications . Academic Pr, 1994. · Zbl 0806.62009
[34] Shanthikumar, J. G. and Xu, S. H., Asymptotically optimal routing and service rate allocation in a multiserver queueing system. Operations Research , 45:464-469, 1997. · Zbl 0891.90077 · doi:10.1287/opre.45.3.464
[35] Stoyan, D. and Daley, D., Comparison Methods for Queues and Other Stochastic Models . Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. Wiley, 1983. · Zbl 0536.60085
[36] Tijdeman, R., Fraenkel’s conjecture for six sequences. Discrete Mathematics , 222(1-3):223-234, 2000. · Zbl 1101.11314 · doi:10.1016/S0012-365X(99)00411-2
[37] van der Laan, D., The Structure and Performance of Optimal Routing Sequences . Universiteit Leiden, 2003.
[38] van der Laan, D., Routing jobs to servers with deterministic service times. Math. Oper. Res. , 30(1):195-224, 2005. · Zbl 1082.90043 · doi:10.1287/moor.1040.0131
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.