利用限制規劃求解客服中心人員排班問題

Solving the Call Center Agent Shift Scheduling Problem by Constraint Programming

鄭雅勻(Ya-Yun Zheng)

指導教授 ： 洪一峯

國立清華大學/工學院/工業工程與工程管理學系/碩士(2007年)

https://doi.org/10.6843/NTHU.2007.00346

摘要

客服中心具有大幅度需求波動的特性。然而，由於人力成本的考量，以及政府法規與公司規定的限制條件下，要提供100%的服務水準來符合隨時間改變的需求是不具經濟效益的。本研究主要探討的是二十四小時客服中心人員排班問題，假設各客服人員效率相同且允許各人員擁有多重技能，並給定各班別類型、各時間區段人數需求、以前各人員排班資料等已知條件下，配合各項政府法規、公司內部規定與員工個人休假安排等限制條件，建構出一個客服人員排班問題的求解方法。
本研究的客服人員排班問題求解方法共分為兩個模組，第一個模組主要以限制規劃的方式將客服中心人員排班問題的模型建構出來，再以限制規劃特有的求解技術，一致性技術、搜尋演算法與限制繁衍機制等來搜尋所有的可行解。在第二個模組中，我們將人員排班階段求解出的班表結果，利用線性規劃的數學模式，分配人員到各時間區段中不同的技能需求。而此線性規劃數學模式中的目標是最小化技能需求的人力不足成本。
為了驗證本研究所提出的方法，我們將利用限制規劃軟體ILOG Solver去執行第一階段的運算，再利用線性規劃軟體ILOG CPLEX執行出線性規劃問題的結果。
最後，由實驗結果得知，本研究所提出之方法可以求解出人員短缺成本最低之最佳排班班表。但是當問題範圍增大時，限制規劃求解的困難度也隨之增加。因此，期望這項問題可以作為未來研究限制規劃求解人員排班問題的一個改進方向。

關鍵字

限制規劃 ； 線性規劃 ； 客服中心 ； 客服人員排班問題

並列摘要

We can observe that the demand of a call center fluctuates greatly. However, it is uneconomical to provide a 100% service level for time-varying demands like a call center because of the cost consideration and the government regulations and company policy. In this study, we investigate the agent shift scheduling problem for a 24-hours call center. We assume that the efficiency is the same for each employee and every employee can be qualified for multiple skills. Given the shift types, the demand of each time period and previous agent shift schedules, we try to find a better method to solve the agent shift scheduling problem in call center. The method must consider the government regulations, company policy and advanced vacation arrangements by agents.
We use two modules to solve the call center agent scheduling problem. The first module use constraint programming to model the agent shift assignment problem. By using the concepts of constraint programming such as consistency checking techniques, searching algorithm and constraint propagation, we are able to find all feasible assignments. In the second module, we use linear program formulation to allocate agents to various skill demands for each time period. The objective of the linear program is to minimize the shortage cost of skill demands.
To validate the proposed method, we will use ILOG Solver, a constraint programming software, to perform the calculation of the first module; also, we will use ILOG CPLEX to perform the computation of the linear program problem.
After validating the modules, we are able to find the optimal schedule for small size problem. But, when the problem scale is getting larger, the number of feasible solutions provided by constraint programming is also getting too huge and it very difficult to solve the whole problem with a reasonable computation. Hence, it may be a good direction for further research.

並列關鍵字

constraint programming ； linear program ； call center ； call center agent scheduling

參考文獻

Atlason, J. and Epelman, M. A and Henderson, S. G (2004), “Call Center Staffing with Simulation and Cutting Plane Methods”, Annals of Operations Research, Vol. 127, pp.333-358.

Aykin , T. (1996), “Optimal Shift Scheduling with Multiple Break Windows”, Management Science, Vol. 42, No.4, pp. 591-602.

Aykin , T. (1998), “A Composite Branch and Cut Algorithm for Optimal Shift Scheduling with Multiple Breaks and Break Windows”, The journal of the Operational Research Society, Vol. 49, No.6, pp. 603-615.

Bailey, J. (1985), “Integrated Days off and Shift Personnel Scheduling”, Computers & Industrial Engineering, Vol. 9, No.4, pp. 395-404.

Beasley , J.E. and Cao, B. (1996), “A tree search algorithm for the crew scheduling problem”, European Journal of Operational Research, Vol. 94, pp. 517-526.