Stochastic optimization for real time service capacity allocation under random service demand. (English) Zbl 1254.90136

Dance, Christopher; Gaivoronski, Alexei A.

Ann. Oper. Res. 193, 221-253 (2012).

Summary: The problem of repeated allocation of limited renewable service resources to distributed service centers is considered here. The objective is to assure a given quality of service expressed through percentage of demand which is satisfied during a specified time period. Resource requirements are not fully known at the time when a decision about the service resource distribution is taken. The problem is addressed by formulating a succession of stochastic optimization problems solved at the time of resource allocation. Solutions of these problems are derived by applying duality theory. We pay special attention to the interplay between performance and risk by introducing the concept of a risk budget. Results of numerical experiments confirm the efficiency of the approach.

MSC:

90C15	Stochastic programming
90B22	Queues and service in operations research

Keywords:

stochastic optimization; real time algorithms; resource allocation; risk budgeting

Software:

SQG

References:

[1]	Abdel-Malek, L. L., & Montanari, R. (2005). An analysis of the multi-product newsboy problem with a budget constraint. International Journal of Production Economics, 97, 296–307.
[2]	Aksin, Z., Armony, M., & Mehrotra, V. (2007). The modern call center: A multi-disciplinary perspective on operations management research. Production and Operations Management, 16(6), 665–688.
[3]	Atlason, J., Epelman, M. A., & Henderson, S. G. (2008). Optimizing call center staffing using simulation and analytic center cutting-plane methods. Management Science, 54(2), 295–309. · Zbl 1232.90266
[4]	Auer, P., Cesa-Bianchi, N., & Gentile, C. (2002). Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences, 64(1), 48–75. · Zbl 1006.68162
[5]	Avramidis, A. N., Chan, W., Gendreau, M., L’Ecuyer, P., & Pisacane, O. (2010). Optimizing daily agent scheduling in a multiskill call center. European Journal of Operational Research, 200, 822–832. · Zbl 1177.90262
[6]	Baron, O., & Milner, J. (2009). Staffing to maximize profit for call centers with alternate service-level agreements. Operations Research, 57(3), 685–700. · Zbl 1233.90206
[7]	Bertsekas, D. P. (2007). Dynamic programming and optimal control (3d ed.). Nashua: Athena Scientific. · Zbl 1209.90343
[8]	Birge, J. R., & Louveaux, F. (1997). Introduction to stochastic programming. New York: Springer. · Zbl 0892.90142
[9]	Cesa-Bianchi, N., & Lugosi, G. (2006). Prediction, learning, and games. Cambridge: Cambridge University Press. · Zbl 1114.91001
[10]	Chung, C.-S., Flynn, J., & Kirca, O. (2008). A multi-item newsvendor problem with preseason production and capacitated reactive production. European Journal of Operational Research, 188, 775–792. · Zbl 1144.90364
[11]	Cover, T. M. (1991). Universal portfolios. Mathematical Finance, 1(1), 1–29. · Zbl 0900.90052
[12]	de Farias, D. P., & Van Roy, B. (2006). A cost-shaping linear program for average-cost approximate dynamic programming with performance guarantees. Mathematics of Operations Research, 31(3), 597–620. · Zbl 1278.90422
[13]	Dempster, M. A. H., Lenstra, J. K., & Rinnooy Kan, A. H. G. (Eds.) (1982). Deterministic and stochastic scheduling. Reidel: Dordrecht. · Zbl 0477.00028
[14]	Erlebacher, S. J. (2000). Optimal and heuristic solutions for the multi-item newsvendor problem with a single capacity constraint. Production and Operations Management, 9, 303–318.
[15]	Gaivoronski, A. A. (2005). SQG: Stochastic programming software environment. In S. W. Wallace & W. T. Ziemba (Eds.), Applications of stochastic programming. Philadelphia: SIAM & MPS.
[16]	Gaivoronski, A. A., & Stella, F. (2003). On-line portfolio selection using stochastic programming. Journal of Economic Dynamics & Control, 27, 1013–1043. · Zbl 1178.91177
[17]	Gaivoronski, A. A., Krylov, S., & Van der Wijst, D. (2005). Optimal portfolio selection and dynamic benchmark tracking. European Journal of Operational Research, 163. · Zbl 1066.91040
[18]	Hadley, G., & Whitin, T. (1963). Analysis of inventory systems. Englewood Cliffs: Prentice-Hall. · Zbl 0133.42901
[19]	Harrison, J. M., & Zeevi, A. (2005). A method for staffing large call centers based on stochastic fluid models. Manufacturing & Service Operations Management, 7(1), 20–36.
[20]	Kalai, A., & Vempala, S. (2005). Efficient algorithms for on-line optimization. Journal of Computer and System Sciences, 71(3), 266–290. · Zbl 1093.68048
[21]	Kall, P., & Wallace, S. (1994). Stochastic programming. New York: Wiley. · Zbl 0812.90122
[22]	Konda, V. R., & Tsitsiklis, J. N. (2003). On actor-critic algorithms. SIAM Journal on Control and Optimization, 42(4), 1143–1166. · Zbl 1049.93095
[23]	Lau, H.-S., & Lau, A. H.-L. (1996). The newsstand problem: A capacitated multiple-product single-period inventory problem. European Journal of Operational Research, 94, 29–42. · Zbl 0929.90003
[24]	Megow, N., & Schulz, A. S. (2004). On-line scheduling to minimize average completion time revisited. Operations Research Letters, 32, 485–490. · Zbl 1054.90037
[25]	Milner, J. M., & Olsen, T. L. (2008). Service-level agreements in call centers: Perils and prescriptions. Management Science, 54(2), 238–252. · Zbl 1232.90152
[26]	Patriksson, M. (2008). A survey on the continuous nonlinear resource allocation problem. European Journal of Operational Research, 185, 1–46. · Zbl 1146.90493
[27]	Pereira, M. V. F., & Pinto, L. M. V. G. (1991). Multi-stage stochastic optimization applied to energy planning. Mathematical Programming, 52, 359–375. · Zbl 0749.90057
[28]	Pflug, G. Ch. (1996). Optimization of stochastic models. The interface between simulation and optimization. Boston: Kluwer. · Zbl 0909.90220
[29]	Philpott, A. B., & Guan, Z. (2008). On the convergence of stochastic dual dynamic programming and related methods. Operations Research Letters, 36, 450–455. · Zbl 1155.90437
[30]	Powell, W. B. (2009). What you should know about approximate dynamic programming. Naval Research Logistics, 56, 239–249. · Zbl 1158.90418
[31]	Powell, W. B., Marar, A., Gelfand, J., & Bowers, S. (2002). Implementing real-time optimization models: A case application from the motor carrier industry. Operations Research, 50(4), 571–581. · Zbl 1163.90635
[32]	Robbins, T. R., & Harrison, T. P. (2010). A stochastic programming model for scheduling call centers with global service level agreements. European Journal of Operational Research, 207, 1608–1619. · Zbl 1206.90052
[33]	Ruszczynski, A., & Shapiro, A. (Eds.) (2003). Stochastic programming, handbook in operations research and management science. Amsterdam: Elsevier Science.
[34]	Van Hentenryck, P., Bent, R., Mercier, L., & Vergados, Y. (2009). Online stochastic reservation systems. Annals of Operation Research, 171(1), 101–126. · Zbl 1181.90234
[35]	Zhang, B., & Du, S. (2010). Multi-product newsboy problem with limited capacity and outsourcing. European Journal of Operational Research, 202, 107–113. · Zbl 1173.90397
[36]	Zhang, B., Xu, X., & Hua, Z. (2009). A binary solution method for the multi-product newsboy problem with budget constraint. International Journal of Production Economics, 136–141, 117.