在全球化及企業高度競爭的環境下，客服中心逐漸成為顧客與企業間最直接也是最重要的溝通方式。由於客服中心主要為勞力密集的經營模式，因此在資訊科技發展快速的今日，硬體設備不再是客服中心的主要支出。目前客服中心有60%至80%的成本主要用於人員僱用，故在目標為最小化人員僱用成本下，要能同時滿足一定程度的服務水準(service level)，已成為客服中心最主要探討的問題。近年來針對具有隨機限制式之模擬最佳化問題發展出許多求解方法，其中拉氏乘數法為一種可以有效處理具有限制式之最佳化問題的方法，並能求得近似最佳解。

一般處理客服中心問題的方式即是將人員需求問題及排班問題分為二階段進行求解，而近年來則是逐漸發展出許多方法用來同步求解人員需求及排班問題，因此本研究以拉氏乘數法為演算法架構，配合Pot et al.[36]之區域搜尋法(型Ⅰ區域搜尋)及Zhang et al.[41]中演算法之概念(型Ⅱ區域搜尋)，發展出四種模擬最佳化演算法，分別為同步式型Ⅰ區域搜尋、同步式型Ⅱ區域搜尋、二階段式型Ⅰ區域搜尋、二階段式型Ⅱ區域搜尋，並加入Batur and Kim[10]之多重可行性驗證程序(Multiple Feasibility Check Procedure; MFCP)，應用於具有多重隨機限制式之離散型最佳化問題，針對單一技能之客服中心規劃各輪班之人員數目，以滿足各週期之最小需求人員數及達到所設定之服務水準目標，並最小化總排班成本，使具有輪班限制下之人員配置問題達到最佳化。

We propose four Lagrange-based simulation algorithms, the Synchronous Type Ⅰ Local Search Algorithm, Synchronous Type Ⅱ Local Search Algorithm, Two-Stage Type Ⅰ Local Search Algorithm, and Two-Stage Type Ⅱ Local Search Algorithm, to solve the agent staffing and scheduling problem in a single-skill call center. This problem aims to minimize the total costs of agents subject to shift constraints and service-level requirements that are estimated by simulation. These algorithms combine the Lagrange method, integer programming, local search and Multiple Feasibility Check Procedure (MFCP). In our numerical experiments with realistic problem instances, the Two-Stage Type Ⅱ Local Search Algorithm performs better under most scenarios. We also show that the two-stage approach, which is the commonly used method for solving this problem, sometimes yields solutions that are suboptimal and inferior to the synchronous approach.

[1] 鄧浚宏，以模擬演算法解決考慮服務水準下之客服中心人員配置問題。國立成功大學工業與資訊管理學系碩士論文(2012)。

[2] Z. Aksin, M. Armony, V. Mehrotra, The modern call center: a multi-disciplinary perspective on operations management research. Production and Operations Management 16 (2007) 665-688.

[3] S. Andradóttir, Simulation optimization with countably infinite feasible regions: Efficiency and convergence. ACM Transactions on Modeling and Computer Simulation 16 (2006) 357-374.

[4] S. Andradóttir, S. H. Kim, Fully sequential procedures for comparing constrained systems via simulation. Naval Research Logistics 57 (2010) 403-421.

[5] J. Atlason, M. A. Epelman, S. G. Henderson, Call center staffing with simulation and cutting plane methods. Annals of Operations Research 127 (2004) 333-358.

[6] J. Atlason, M. A. Epelman, S. G. Henderson, Optimizing call center staffing using simulation and analytic center cutting-plane methods. Management Science 54 (2008) 295-309.

[7] A. N. Avramidis, A. Deslauriers, P. LʼEcuyer, Modeling daily arrivals to a telephone call center. Management Science 50 (2004) 896-908.

[8] A. N. Avramidis, W. Chan, P. L'Ecuyer, Staffing multi-skill call centers via search methods and a performance approximation. IIE Transactions 41 (2009) 483-497.

[9] A. N. Avramidis, W. Chan, M. Gendreau, P. L'Ecuyer, O. Pisacane, Optimizing daily agent scheduling in a multiskill call center. European Journal of Operational Research 200 (2010) 822-832.

[10] D. Batur, S. H. Kim, Finding feasible systems in the presence of constraints on multiple performance measures. ACM Transactions on Modeling and Computer Simulation 20 (2010) 1-26.

[11] R. E. Bechhofer, A single-sample multiple decision procedure for ranking means of normal populations with known variances. Annals of Mathematical Statistics 25 (1954) 16-39.

[12] S. Bhulai, G. Koole, A. Pot, Simple methods for shift scheduling in multi-skill call centers. Manufacturing & Service Operations Management 10 (2008) 421-428.

[13] S. Borst, A. Mandelbaum, M. Reiman, Dimensioning large call centers. Operations Research 52 (2004) 17-34.

[14] L. Brown, N. Gans, A. Mandelbaum, A. Sakov, H. Shen, S. Zeltyn, L. Zhao, Statistical analysis of a telephone call center: a queueing-science perspective. Journal of the American Statistical Association 100 (2005) 36-50.

[15] J. Butler, D. J. Morrice, P. W. Mullarkey, A multiple attribute utility theory approach to ranking and selection. Management Science 47 (2001) 800-816.

[16] M. T. Cezik, P. L'Ecuyer, Staffing multiskill call centers via linear programming and simulation. Management Science 54 (2008) 310-323.

[17] N. Gans, G. M. Koole, A. Mandelbaum, Telephone call centers: tutorial, review, and research prospects. Manufacturing & Service Operations Management 5 (2003) 79-141.

[18] O. Garnett, A. Mandelbaum, M. Reiman, Designing a call center with impatient customers. Manufacturing & Service Operations Management 4 (2002) 208-227.

[19] L. Green, P. Kolesar, J. Soares, Improving the SIPP approach for staffing service systems that have cyclic demands. Operations Research 49 (2001) 549-564.

[20] S. S. Gupta, On a decision rule for a problem in ranking means. Mimeograph Series No. 150, Institute of Statistics, University of North Carolina, Chapel Hill, North Carolina, 1956.

[21] I. Gurvich, J. Luedtke, T. Tezcan, Staffing call-centers with uncertain demand forecasts: a chance-constraints approach. Management Science 56 (2010) 1093-1115.

[22] S. Halfin, W. Whitt, Heavy-traffic limits for queues with many exponential servers. Operations Research 29 (1981) 567-588.

[23] L. J. Hong, B. L. Nelson, A brief introduction to optimization via simulation. In Proceedings of 2009 Winter Simulation Conference. IEEE Computer Society, Washington, DC (2009) 75-85.

[24] A. Ingolfsson, M. Haque, A. Umnikov, Accounting for time-varying queueing effects in workforce scheduling. European Journal of Operational Research
139 (2002) 585-597.

[25] A. Ingolfsson, F. Campelloa, X. Wub, E. Cabralc, Combining integer
programming and the randomization method to schedule employees.
European Journal of Operations Research 202 (2010) 153-163.

[26] J. P. C. Kleijnen, W. van. Beers, I. van. Nieuwenhuyse, Constrained optimization in expensive simulation: novel approach. European Journal of Operational Research 202 (2010) 164-174.

[27] G. M. Koole, A. Mandelbaum, Queueing models of call centers: An introduction. Annals of Operations Research 113 (2002) 41-59.

[28] H. J. Kushner, E. Sanvicente, Stochastic approximation of constrained systems with system and constraint noise. Automatica 11 (1975) 375-380.

[29] H. J. Kushner, D. S. Clark, Stochastic approximation methods for constrained and unconstrained systems, Springer-Verlag, New York, 1978.

[30] J. Li, A. Sava, X. Xie, Simulation-based discrete optimization of stochastic discrete event systems subject to non closed-form constraints. IEEE Transactions on Automatic Control, 54 (2009) 2900-2904.

[31] Y. Luo, E. Lim, Simulation-based optimization over discrete sets with noisy constraints. IIE Transactions 45 (2013) 699-715.

[32] A. Mandelbaum, S. Zeltyn, B. Hefley, W. Murphy, Service engineering of call centers: Research, teaching, practice. Service Science, Management and Engineering Education for the 21st Century, Springer, New York, 2008.

[33] A. Mandelbaum, Call centers (centres): Research bibliography with abstracts, Version 6. Faculty of Industrial Engineering and Management, Technion, Haifa, Israel, 2004.

[34] A. Mason, D. Ryan, D. Panton, Integrated simulation, heuristic and optimisation approaches to staff scheduling. Operations Research 46 (1998) 161-175.

[35] V. Mehrotra, J. Fama, Call center simulation modeling: methods, challenges, and opportunities. In Proceedings of the 2003 Winter Simulation Conference. IEEE, New Orleans, LA (2003) 135-143.

[36] S. A. Pot, S. Bhulai, G. M. Koole, A simple staffing method for multiskill call centers. Manufacturing & Service Operations Management 10 (2008) 421-428.

[37] T. Robbins, T. Harrison, A stochastic programming model for scheduling call centers with global service level agreements. European Journal of Operational Research 207 (2010) 1608-1619.

[38] T. J. Santner, A. C. Tamhane, Designing experiments for selecting a normal population with a large mean and a small variance. T. J. Santner, A. C. Tamhane (Eds.), Design of Experiments: Ranking and Selection, Marcel Dekker, New York (1984) 179-198.

[39] J. Tien, A. Kamiyama, On manpower scheduling algorithms. SIAM Review 24 (1982) 275-287.

[40] J. E. Whitney, L. I. Solomon, S. D. Hill, Constrained optimization over discrete sets via SPSA with application to nonseparable resource allocation. In Proceedings of the 2001 Winter Simulation Conference. IEEE, Piscataway, NJ (2001) 313-317.

[41] Y. Zhang, M. L. Puterman, M. Nelson, D. Atkins, A simulation optimization approach to long-term care capacity planning. Operations Research 60 (2012) 249-261.