限制機理技術應用於粒子群最佳化演算法改良之研究─以客服中心人員排班為例

Using Constraint-Based Reasoning and Particle Swarm Optimization Approach in Call Center Staff Rostering

蔡燿燦(Yao-Tsan Tsai)

指導教授 ： 邱昭彰

元智大學/資訊學院/資訊管理學系/碩士(2007年)

摘要

本研究嘗試粒子群最佳化演算法在初始化粒子與演化過程中與將限制推理機制中的前向檢驗法作結合。演化過程，本研究提出了選擇策略讓粒子群最佳化演算法在演化過程中，能有效的提昇問題適性值並朝最佳解邁進。在初始化過程與演化過程時，可以藉由限制推理機制的前向檢驗法技術，來減少粒子搜尋不必要的解空間，以加快求解效率。本研究利用客服人員的排班問題來進行驗證。透過本研究的機制，在建構客服人員班表的過程中，能夠有效且彈性的處理各類限制式之特性，如各項法規、公司政策及各時段人員需求量為已知的條件下，以客服中心現有的人力來產生較佳的排班班表，達到人力成本最小化及公平性最大化。根據最後的實驗結果顯示限制推理粒子群最佳化演算法在解決較複雜的最佳化問題上有很好的結果。

關鍵字

限制推理粒子群最佳化演算法；客服人員排班問題；限制推理機制；前向檢驗法；選擇策略

並列摘要

This paper presents a new improve method combining the particle swarm optimization (PSO) with the constraint-based reasoning during the stage of the initialization and evolution in the PSO. We call it constraint-based particle swarm optimization (CBPSO). CBPSO can reduce the search space which violates pre-defined constraints through forward checking. After generates a whole particle using forward checking, this particle is a feasible solution. Then we propose a select strategy in CBPSO and use forward checking for the stage of the evolution. We can use this select strategy to select the partial particle for improving the fitness value of the whole particle. We use the Call Center Staff Rostering Problem to prove our method and this result shows that CBPSO has better efficiency than PSO in the evolution’s time and fitness value.

並列關鍵字

Constraint-based reasoning；particle swarm optimization； forward checking；select strategy； Scheduling Problem； Call Center Staff Rostering

參考文獻

[2]Angeline, P., “Evolutionary Optimization versus Particle Swarm Optimization: Philosophy and Performance Differences,” Proceedings of the Evolutionary Programming, Vol. 1447, pp. 601-610, 1998.

[3]Azmat, C. S. and Widmer, M., “A Case Study of Single Shift Planning and Scheduling under Annualized Hours: A Simple Three-Approach,” European Journal of Operational Research, Vol. 153, pp. 148-175, 2004.

[4]Azaiez, M. N. and Sharif, S. S., “A 0-1 Goal Programming Model for Nurse Scheduling,” Computer & Operations Research, Vol. 32, pp. 491-507, 2005.

[5]Baker, K. R., “Scheduling a Full-Time Workforce to Meet Cyclic Staffing Requirements,” Management Science, Vol. 20, pp. 1561-1568, 1974.

[6]Baker, K. R., “Workforce Allocation in Cyclical Scheduling Problems: A Survey,” Operational Research. Quarterly, Vol. 27, No. 1, pp. 155-167, 1976.