Control of Parallel Non-observable Queues: Asymptotic Equivalence and Optimality of Periodic Policies

References

• Altman, E., Gaujal, B., and Hordijk, A., Balanced sequences and optimal routing. J. ACM, 47(4):752–775, July 2000. MR1866176Google Scholar
• Altman, E., Gaujal, B., and Hordijk, A., Multimodularity, convexity, and optimization properties. Math. Oper. Res., 25(2):324–347, 2000. MR1853955Link, Google Scholar
• 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.Google Scholar
• Anselmi, J. and Gaujal, B., The price of forgetting in parallel and non-observable queues. Perform. Eval., 68(12):1291–1311, Dec. 2011.Google Scholar
• Asmussen, S., Applied Probability and Queues. Wiley, 1987. MR0889893Google Scholar
• Baccelli, F. and Brémaud, P., Elements of Queueing Theory: Palm Martingale Calculus and Stochastic Recurrences, volume 26. Springer, 2003. MR1957884Google Scholar
• 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. MR1642907Google Scholar
• 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.Link, Google Scholar
• Bhat, U. N., An Introduction to Queueing Theory: Modeling and Analysis in Applications. Birkhauser Verlag, 2008. MR2449481Google Scholar
• 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. MR3002105Google Scholar
• Billingsley, P., Convergence of Probability Measures. Wiley Series in Probability and Statistics, 1999. MR1700749Google Scholar
• Borovkov, A., Stochastic Processes in Queueing Theory. Applications of Mathematics. Springer-Verlag, 1976. MR0391297Google Scholar
• 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.Google Scholar
• Combé, M. B. and Boxma, O. J., Optimization of static traffic allocation policies. Theor. Comput. Sci., 125(1):17–43, 1994. MR1260639Google Scholar
• Doob, J., Stochastic Processes. Wiley Publications in Statistics. John Wiley & Sons, 1953. MR0058896Google Scholar
• 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. MR2204312Google Scholar
• 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.Google Scholar
• 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. MR0819133Google Scholar
• Hajek, B., Extremal splitting of point processes. Math. Oper. Res., 10:543–556, 1986. MR0812813Google Scholar
• 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.Google Scholar
• 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.Google Scholar
• 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. MR2063077Google Scholar
• 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.Google Scholar
• 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.Google Scholar
• 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.Google Scholar
• Lindley, D. V., The theory of queues with a single server. Mathematical Proceedings of the Cambridge Philosophical Society, 48:277–289, 1952. MR0046597Google Scholar
• Liu, Z. and Righter, R., Optimal load balancing on distributed homogeneous unreliable processors. Journal of Operations Research, 46(4):563–573, 1998.Link, Google Scholar
• Loynes, R., The stability of a queue with nonindependent interarrival and service times. Mathematical Proceedings of the Cambridge Philosophical Society, 58:497–520, 1962. MR0141170Google Scholar
• Makowski, A., On an elementary characterization of the increasing convex ordering, with an application. Journal of Applied Probability, 31:834–840, 1994. MR1285521Google Scholar
• Neely, M. J. and Modiano, E., Convexity in queues with general inputs. IEEE Transactions on Information Theory, 51(2):706–714, 2005. MR2236080Google Scholar
• Puterman, M. L., Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, USA, 1st edition, 1994. MR1270015Google Scholar
• Sethuraman, J. and Squillante, M. S., Optimal stochastic scheduling in multiclass parallel queues. SIGMETRICS ’99, pages 93–102, New York, NY, USA, 1999. ACM.Google Scholar
• Shaked, M. and Shanthikumar, J. G., Stochastic Orders and Their Applications. Academic Pr, 1994. MR1278322Google Scholar
• 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. MR1644192Link, Google Scholar
• 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. MR0754339Google Scholar
• Tijdeman, R., Fraenkel’s conjecture for six sequences. Discrete Mathematics, 222(1–3):223–234, 2000. MR1771401Google Scholar
• van der Laan, D., The Structure and Performance of Optimal Routing Sequences. Universiteit Leiden, 2003.Google Scholar
• van der Laan, D., Routing jobs to servers with deterministic service times. Math. Oper. Res., 30(1):195–224, 2005. MR2125144Link, Google Scholar