We develop a gradient-based simulation optimization algorithm, dabbed KWiQ-H, for joint pricing and staffing problems in single-server queues with heavy-tailed service time distributions. Our algorithm is designed based on the well-known Kiefer-Wolfowitz algorithm so that it is applicable tomore general and practical settings where customer’s behavior is unknown to service providers in prior. We first establish a convergence result for KWiQ-H when the service times have a finite fifth moment. Then, we show that under a stronger condition with a finite seventh moment, KWiQ-H could achieve sample complexity with the same asymptotic order as in the case when service times are light-tailed in Chen et al. (Oper Res, 2023). Complementing the theoretic results, we carry out comprehensive numerical experiments to test the efficiency and robustness of KWiQ-H in a variety of model settings.
[1] Abate, J., Whitt, W.: Transient behavior of the M/G/1 workload process. Oper. Res. 42(4), 750-764(1994)
[2] Asmussen, S.: Applied Probability and Queues. Springer, New York (2003)
[3] Asmussen, S., Glynn, P.W.: Stochastic simulation: algorithms and analysis, vol. 57. Springer, New York (2007)
[4] Besbes, O., Zeevi, A.: On the (surprising) sufficiency of linear models for dynamic pricing with demand learning. Manage. Sci. 61(4), 723-739(2015)
[5] Broadie, M., Cicek, D., Zeevi, A.: General bounds and finite-time improvement for the KieferWolfowitz stochastic approximation algorithm. Oper. Res. 59(5), 1211-1224(2011)
[6] Broder, J., Rusmevichientong, P.: Dynamic pricing under a general parametric choice model. Oper. Res. 60(4), 965-980(2012)
[7] Brown, L., Gans, N., Mandelbaum, A., Sakov, A., Shen, H., Zeltyn, S., Zhao, L.: Statistical analysis of a telephone call center: a queueing-science perspective. J. Am. Stat. Assoc. 100(469), 36-50(2005)
[8] Chen, X., Liu, Y., and Hong, G. An online learning approach to dynamic pricing and capacity sizing in service systems. Operations Research (2023a). https://doi.org/10.1287/opre.2020.612
[9] Chen, X., Liu, Y., and Hong, G. Online learning and optimization for queues with unknown demand curve and service distribution (2023b). arXiv:2303.03399
[10] Chong, E.K.P., Ramadge, P.J.: Optimization of queues using an infnitesimal perturbation analysisbased stochastic algorithm with general update times. SIAM J. Control. Optim. 31, 698-732(1993)
[11] Fu, M.C.: Convergence of a stochastic approximation algorithm for the GI/G/1 queue using infinitesimal perturbation analysis. J. Optim. Theory Appl. 65, 149-160(1990)
[12] Glasserman, P.: Stationary waiting time derivatives. Queueing Syst. 12, 369-390(1992)
[13] Harchol-Balter, M. The effect of heavy-tailed job size distributions on computer system design. In: Proc. of ASA-IMS Conf. on Applications of Heavy Tailed Distributions in Economics, Engineering and Statistics, 19D99
[14] Hong, L.J., Li, C., Luo, J.: Finite-time regret analysis of Kiefer-Wolfowitz stochastic approximation algorithm and nonparametric multi-product dynamic pricing with unknown demand. Naval Res. Logist. 67(5), 368-379(2020)
[15] Nair, J., Wierman, A., Zwart, B.: Provisioning of large scale systems: the interplay between network effects and strategic behavior in the user base. Manag. Sci. 62(6), 1526-5501(2016)
[16] Keskin, N.B., Zeevi, A.: Dynamic pricing with an unknown demand model: Asymptotically optimal semi-myopic policies. Oper. Res. 62(5), 1142-1167(2014)
[17] Kiefer, J., Wolfowitz, J.: Stochastic estimation of the maximum of a regression function. Ann. Math. Stat. 23, 462-466(1952)
[18] Kim, J., Randhawa, R.S.: The value of dynamic pricing in large queueing systems. Oper. Res. 66(2), 409-425(2018)
[19] Kumar, S., Randhawa, R.S.: Exploiting market size in service systems. Manuf. Serv. Oper. Manag. 12(3), 511-526(2010)
[20] Latouchet, G., Pearce, C.E., Taylor, P.G.: Invariant measures for quasi-birth-and-death processes. Stoch. Model. 14(1-2), 443-460(1998)
[21] L’Ecuyer, P., Glynn, P.W.: Stochastic optimization by simulation: convergence proofs for the GI/GI/1 queue in steady state. Manage. Sci. 40(11), 1562-1578(1994)
[22] L’Ecuyer, P., Giroux, N., Glynn, P.W.: Stochastic optimization by simulation: numerical experiments with the M/M/1 queue in steady-state. Manage. Sci. 40(10), 1245-1261(1994)
[23] Maglaras, C., Zeevi, A.: Pricing and capacity sizing for systems with shared resources: approximate solutions and scaling relations. Manage. Sci. 49(8), 1018-1038(2003)
[24] Maglaras, C., Zeevi, A.: Pricing and design of differentiated services: approximate analysis and structural insights. Oper. Res. 53(2), 242-262(2003)
[25] Mahani, A., Kavian, Y.S., Naderi, M., Rashvand, H.F.: Heavy-tail and voice over internet protocol traffic: queueing analysis for performance evaluation. IET Commun. 5(18), 2736-2743(2011)
