戴 韜，李軍祥

DAI Tao1,LI Junxiang2

1.東華大學 旭日工商管理學院，上海200051

2.上海理工大學 管理學院，上海200093

1.Glorious Sun School of Management,Donghua University,Shanghai 200051,China

2.Business School,University of Shanghai for Science and Technology,Shanghai 200093,China

1 引言

1.1 背景

呼叫中心（Call Center）作為一種成熟運營模式已廣泛應用于各社會各行業(yè)中，成為各自保持客戶聯(lián)系的關鍵渠道與制勝法寶。多技能指呼叫中心能提供超過一種的服務，其坐席人員也被培訓有一種或多種服務的技能。多技能呼叫中心是呼叫中心發(fā)展的必然形態(tài)。

呼叫中心是典型的技術、勞動力雙重密集型產(chǎn)業(yè)，其運營過程不僅僅依靠計算機、通訊等軟硬件的支持，更需要大量的坐席人員（Agent）參與服務。因此，呼叫中心運營的60%～70%是坐席代表的人工成本，合理的人員排班是實現(xiàn)高效率的呼叫中心運營管理，降低整體運營成本，保證客戶服務質量和服務水平，提高呼叫中心生產(chǎn)力的最重要一環(huán)[1]。

1.2 班次設計的內涵

廣義的人員排班一般分為3 個步驟[2]：

（1）根據(jù)歷史數(shù)據(jù)預測未來一段時間內每個時間段（以15 分鐘或半個小時為單位）的顧客來電量；

（2）按照預測的每個時間段的來電量，在滿足服務水平的前提下，確定各技能的人員數(shù)量；

（3）將坐席人員安排到各備選班次中，不但要滿足第（2）步的人力需求，而且還要考慮到坐席人員的個性化需求。

其中班次設計（Shift Design）是步驟（3）中最重要的基礎性工作，是人力需求預測與計算與后續(xù)人員排班的橋梁。明顯地，一套合理的班次應該很好的符合話務量變化規(guī)律，如果班次設計不合理，再好的人力需求計算也變得沒有價值，后續(xù)的人員排班步驟也沒有了意義。

在班次設計中，每個班次的持續(xù)時間都是相同且已知的，該持續(xù)時間受工人合同、法律法規(guī)等限制，如8 小時工作制。這樣，班次設計的主要內容就是[3]：

（1）確定總的班次數(shù)，以及各班次的開始時間與結束時間；

（2）確定每個班次的休息時間，保證所有上班人員均能享受到必須的休息；

（3）確定每個班次需要的上班人數(shù)，將以時間段（period）為單位的人力需求轉換為以班次（shift）為單位的工作量。

2 文獻綜述

在班次的設計中，主要的困難是班次的不連續(xù)性（因為有休息的時間窗）。若假設所有的班次都是連續(xù)的（從開始一直工作到結束），那么班次矩陣（矩陣的行是時間段，列是備選班次數(shù)）是完全幺模矩陣（totally unimodular）。在該假設下，文獻[4]研究了設計最優(yōu)化班次的方法，并得到了最優(yōu)解；文獻[5]提出了單技能環(huán)境下完整的班次設計模型；文獻[3，6]提出了多技能環(huán)境下班次總體數(shù)目及起始時間的確定模型。

當允許班次中斷后，班次矩陣就不再是幺模的，該問題就變得復雜得多，文獻[7]已經(jīng)證明該問題是一個完全NP 難題。對于該難題的代表性研究分別從建模與算法兩方面展開。在建模方面，文獻[8]提出不要用覆蓋模型來研究這個問題。文獻[9]和文獻[10]將變量分為兩組，一組表示班次的起始時間，另一組表示班次的中斷時間，這樣的變量設置方法就避免了使用覆蓋模型來求解。在算法方面，文獻[11]做了這方面的工作，他將班次設計分為兩個步驟：第一步假設班次是不中斷的，使用網(wǎng)絡流模型得到最優(yōu)解；第二步通過啟發(fā)式的方法往第一步的結果中加入中斷時間，最后得到可行解。文獻[12]也做了這方面的工作，在確定班次矩陣的時候就采用了一些啟發(fā)式的方法使得這個矩陣的規(guī)模不要過于龐大。另外由于覆蓋問題的規(guī)模比較大，通常是幾百行，上千列[7]，很難以全局搜索的方法來找最優(yōu)解，而應該使用模擬退火、遺傳算法等局部搜索的方法，文獻[13]提出了基于鄰域搜索的班次設計算法。

對于班次設計的研究不僅僅局限于呼叫中心領域，文獻[14]綜述了人員排班領域的文獻；文獻[15]研究了多工作點的班次設計問題；文獻[16]研究了醫(yī)療服務行業(yè)的班次設計問題；文獻[17]研究了運輸行業(yè)的班次設計問題。

綜上，在呼叫中心領域，雖然已分別有論文研究了多技能連續(xù)性班次的設計方法以及單技能中斷性班次的模型與算法，但結合兩者，即考慮休息時間的多技能班次設計卻鮮見討論。在多技能的環(huán)境中，班次的設計將會變得更加復雜，因為某技能組人員的增減不單單影響本技能組的人員供給，還會交叉影響與其相關的其他技能組的人員供給[1]。

3 模型與算法設計

3.1 基本思路

3.2 連續(xù)性班次設計模型

為了得到簡化的多技能班次設計模型，借鑒文獻[3]提出的“技能穩(wěn)定”（skill frozen）思路，一個多技能的坐席人員雖然可以接聽多種類型的電話，但是在一個時間段里，他僅僅可以根據(jù)當時各類電話的空閑情況以及自身的技能列表，選擇一種進行服務，并且在這個時間段內，不允許再有變化。“技能穩(wěn)定”假設可以便于將多技能坐席人員拆分變成單技能的坐席人員，得到簡化的連續(xù)多技能的班次設計模型（模型1）如下（不考慮休息時間窗）：

模型1多技能連續(xù)班次設計模型

模型1 的目標函數(shù)（1）表示排班周期內總的人力成本最低，其中決策變量Xgi表示技能組為g的坐席人員安排到第i個班次上班的人數(shù)；Cgi為已知量，表示技能組g的坐席人員上i班次的報酬；約束（2）引入了一個中間變量Ygts，表示技能組g的坐席人員在第t時間段以技能s上班的人數(shù)，Ygts與Xgi的關系如約束（2）所示，其中ait=1 表示時間段t是第i班次的工作時間段，等于0 則反之；約束（3）確保了一個多技能坐席人員在一個時間段內只能“扮演”某中特定的單技能坐席人員的角色，并且他所“扮演”的角色是受其技能列表所限的，bgs=1 表示技能組g擁有技能s，等于0 則表示沒有；約束（4）中的表示確定的第t時間段s類型電話的人力需求（通過人力需求計算獲得，屬于班次設計的已知條件），該約束確保了各類型的人力需求都能夠被滿足；約束（5）中的常量ζ是一個大正整數(shù)，該約束保證只要被指派了坐席人員的班次被標記為“使用過”班次；約束（6）表示總的“使用”班次不能超過限定值M；約束（7）則確保變量Xgi和Ygts是個非負整數(shù)，而Zi為0-1變量。

文獻[3]已討論過如何利用該模型，通過逐步放松參數(shù)M 的限制，得到連續(xù)性班次。本文借鑒其方法，不詳細展開討論。

3.3 空閑勞動力計算

模型1 得到了多技能環(huán)境下最合適的M個班次，但這些班次都是連續(xù)工作的，在實際應用中無法接受?？紤]如何在連續(xù)工作的班次中，加入休息時間。

首先，利用已知的M個連續(xù)班次，將把排班周期內的以時間段為單位的人力需求轉化為以班次為單位的人力需求：

模型2人力需求轉換模型（時間段→班次）

模型2 是模型1 在日期維度上的改進和擴展，所有變量與約束的含義均與模型1 相同，除了用確定的班次集M取代了模型1 中的備選班次集I，另外也去掉了原模型中班次總量限制。模型2 雖然時間維度上的規(guī)模變大了，但班次維度問題規(guī)模的縮減和班次總數(shù)約束的去除，仍保證了該模型能夠比較容易求解。

模型2 的主要功能是得到在連續(xù)工作的班次下，空閑的工作能力，有空閑的工作能力存在就說明存在潛在的休息可能性。模型2 中用Sjts表示第j天第t時刻以技能s工作的坐席人員人數(shù)，而變量ΔOjts表示在第j天第t時刻以技能s工作的空閑的坐席人員人數(shù)。

通過模型2 的轉換后，休息時間窗的加入在本質上就變成了一個分配問題（Assignment Problem），其基本思路是以ΔOjts為供給，以坐席休息時間為需求，進行人力分配，直到給所有的坐席人員都安排了休息時間為止。

3.4 休息時間加入

為了表述方便，設定坐席的休息規(guī)則如下：每個班次需3 個休息時間，其中第一個休息時間在班次開始后的2～3.5 h，持續(xù)15 min，記為b1；第二個休息時間是長休息時間（用餐等），在班次開始后的4～5 h，持續(xù)30 min，標記為b2；第三個休息時間在班次開始后第6～7.5 h，持續(xù)15 min，標記為b3（注：該休息規(guī)則僅僅是較有代表性的一種，不同呼叫中心可根據(jù)情況進行調整）。

由模型2 已經(jīng)得到了每時刻多余的人力ΔOjts，這里多余的人力是按照技能類型來分類的，根據(jù)3.3 節(jié)的思路，可以得到多技能的環(huán)境下多余人力與休息時間的分配模型：

模型3多技能環(huán)境下多余人力與休息時間的分配模型

模型3 中沒有了日期維度的變量J，因為模型3 是在模型1 得到的連續(xù)性班次基礎上，根據(jù)每天的話務量變化動態(tài)地加入休息時間。若排班周期共J天，需要將模型3 執(zhí)行J次。

目標函數(shù)式（14）中的變量Zt是一指標性的0-1 變量，若t時刻需要休息的人數(shù)大于空閑的人數(shù)（即無法保證所有該休息的坐席得到休息）Zt=1，反之為0；約束（15）是確保所有上班的坐席人員能在班次開始2～3.5 h內安排到休息b1，決策變量表示技能組為g在m班次上班的坐席在bm+8 時刻開始b1休息的人數(shù)，其中bm是班次m的開始時間，已通過模型1 計算得到，變量Xgm是技能組g在m班次上班的總人數(shù)，已通過模型2 得到；同理，約束（16）確保在班次開始4～5 h 內安排到b2休息；約束（17）是確保所有上班的坐席人員能在班次開始6～7.5 h 內安排到b3休息；約束（18）引入了一個新的變量Y′gmts，表示g技能組在m班次以s技能工作的坐席在t時刻休息的人數(shù)，等于3 類休息的人數(shù)匯總；約束（19）限制了空閑的人數(shù)至少不能超過上班的人數(shù)，其中上班人數(shù)Ygmts已經(jīng)由模型2 計算獲得；約束（20）和（21）共同作用，確保在每個時刻t，若休息人數(shù)大于了空閑的人數(shù)，標記Zt為1。

3.5 算法設計

本文涉及到3 個基本模型，每個基本模型均屬于典型的線性整數(shù)規(guī)劃問題，可以直接應用已有成熟的算法或軟件進行求解，這里討論的算法是如何綜合利用3 個模型得到最終帶有休息時間的班次。

從分析模型3 入手，其目標函數(shù)的下限是0（表示所有的時刻t，空閑人數(shù)均大于計劃休息的人數(shù)），即可以在不影響服務水平下，所有坐席均得到應有的休息，這也是最終班次設計的要求。目標函數(shù)值>0，說明至少存在一個時刻待休息的人數(shù)大于空閑人數(shù)，即在給定的連續(xù)性班次和上班人數(shù)下，無法保證每人都能滿足休息需求。因此，只有通過增加上班人數(shù)來保證所有人均得到休息，增加的方法是：

（1）找出Zt值為1 的所有時刻t；

（2）檢查變量Zts=1，找到具體是哪一技能坐席的人員不足；

（3）對Zts=1 的時刻t，構造“虛擬”人力需求即在原實際坐席人力需求rts+1，再重新進行模型2 的計算，迭代，直到模型3 的目標函數(shù)=0 為止。

需要注意，模型3 僅僅得到是1 天的班次安排，對于周期為J天的排班過程，需要將模型3 迭代J個過程。綜上，得到最終的算法示意如圖1 所示。

由圖1 可知，本文的班次設計算法是兩階段的。第一階段得到連續(xù)性的班次，第二階段在此基礎上加入休息時間，最終得到的班次使得每個班次中上班的人員均能保證得到該有的休息。不僅于此，由于模型3 是每天獨立運行的，在保證總班次數(shù)不增加的前提下（管理的方便），每個班次的休息時間能根據(jù)當天話務量的變化動態(tài)調整。另外，除了班次表之外，可以得到以班次為單位的人力需求，相比以時刻為單位的人力需求，更有助于后續(xù)的人員排班。

圖1 兩階段班次設計算法示意圖

4 算例實驗

4.1 算例假設

本文的算例跟文獻[3]中的一致，其結構如圖2所示。

圖2 某呼叫中心結構圖

該呼叫中心一共處理3 種類型的電話(S=3)，共有4 個技能組的坐席人員(G=4)，每15 min 為一個時間段(T=96)，時間段內電話的到達率、服務率甚至是多技能坐席人員處理的電話類型都是不變的，設定班次只能在半點或者整點的時候開始，備選的班次總共有48 個(I=48)，班次的持續(xù)時間都是8 h。

由圖2，可以得知各技能組擁有的技能，組成技能矩陣：矩陣中的元素bgs=1 表示技能組g擁有技能s。

假設處理同種電話，不同技能組的服務率是相同的，以時刻為單位的3 類電話的人力需求已知；不同技能組上不同的班次給予不同的酬勞，具體的酬勞已知。

4.2 算例求解

將4.1 節(jié)中的已知條件代入到模型1 中進行求解，通過逐步限定班次總數(shù)M，得到最優(yōu)連續(xù)性班次如表1。文獻[3]已詳述過程，不再贅述。

表1 連續(xù)性班次及需求人數(shù)

根據(jù)圖1所示算法，得到連續(xù)性的班次后，將其作為已知代入到模型2 得到各時刻下的空閑人力。以類型3電話為例，得到某天電話3 的人力需求與供給如圖3。

圖3 某天電話3 人力需求與供給

模型3 的迭代過程即是以圖3 中陰影表示的空閑人力為供給，保證表1 內9 個班次的坐席人員均能按要求享受到休息。根據(jù)本文設計的算法，可得到最終帶有休息時間的班次，以表1 中的班次3 為例，最后的班次安排如表2。

表2 帶休息的班次表（班次3）

其余各班次也得到類似的結果。通過算例也發(fā)現(xiàn)了兩個不甚滿意的地方：

（1）由于空閑人力緊張，休息b1被拆分成了6 個時間段進行休息，不利于現(xiàn)場管理。

（2）為了有更多的空閑人力保證足夠的休息，班次3由原來的上班38 人增長為40 人。分步優(yōu)化可能偏離了全局最優(yōu)解。

5 結論

班次設計是呼叫中心人員排班的基礎性工作，尤其在多技能的環(huán)境下，是完全NP-hard 問題。本文根據(jù)分步優(yōu)化的思想，設計了相應模型與兩階段算法，先計算連續(xù)性班次，再通過改進的指派模型將休息時間安排到班次中，得到可行解，并通過班次的設計，將原以時刻為單位的人力需求轉化為以班次（跨越N個時刻，一般N≥30）為單位的人力需求，使得后續(xù)的人員指派步驟規(guī)模縮小N倍，便于后續(xù)指派模型的求解。

由于算法是分步進行的，每次僅得到局部的最優(yōu)，特別是在連續(xù)性班次下人員供給曲線與需求曲線切合得較好的區(qū)域，為了能得到足夠的空余人力保證休息時間，需要不斷增加額外的上班人數(shù)，不單因為迭代次數(shù)過多影響了求解速度，與全局最優(yōu)解的差距也在加大，因此算法的速度及其收斂性是本文后續(xù)研究方向。

[1] Gans N，Koole G，Mandelbaum A.Telephone call centers：tutorial，review，and research prospects[J].Manufacturing &Service Operations Management，2003，5（2）：79-141.

[2] Ernst A T，Jiang H，Krishnamoorthy M，et al.Staあscheduling and rostering：A review of applications，methods and models[J].European Journal of Operational Research，2004，153（1）：3-27.

[3] Dai T，Huo J.A research on shift scheduling in multi-skill call center[C]//Proceeding of 2008 IEEE International Conference on Service Operations and Logistics，and Informatics，2008：655-658.

[4] Nemhauser G L，Wolsey L A.Integer and combinatorial optimization[M].[S.l.]：Wiley InterScience，1988.

[5] Brusco M J，Jacobs L W.Starting-time decisions in labor tour scheduling：An experimental analysis and case study[J].European Journal of Operational Research，2001，131：459-475.

[6] Bhulai S，Koole G，Pot A.Simple methods for shift scheduling in Multiskill call centers[J].Manufacturing & Service Operations Management，2008，10（3）：411-420.

[7] Caprara A，Monaci M，Toth P.Models and algorithms for a staff scheduling problem[J].Mathematic Programming：Series B，2003，98：445-476.

[8] Thompson G M.Improved implicit optimal modeling of the labor shift scheduling problem[J].Management Science，1995，41：595-607.

[9] Aykin T.Optimal shift scheduling with multiple break windows[J].Management Science，1996，42：591-602.

[10] Brusco M J，Jacobs L W.Optimal models for meal-break and start-time flexibility in continuous tour scheduling[J].Management Science，2000，46：1630-1641.

[11] Segal M.The operator-scheduling problem：A network-flow approach[J].Operations Research，1974，24：808-823.

[12] Henderson W B，Berry W L.Heuristic methods for telephone operator shift scheduling：an experimental analysis[J].Management Science，1976，22：1372-1380.

[13] Quimper C G，Rousseau L M.A large neighborhood search approach to the multi-activity shift scheduling problem[J].Journal of Heuristics，2010，16（3）：373-392.

[14] den Bergh J V，Belien J，Bruecker P，et al.Personnel scheduling：A literature review[J].European Journal of Operation Research，2013，226：367-385.

[15] Al-Yakoob S M，Sherali H D.A column generation approach for an employee scheduling problem with multiple shifts and work locations[J].Journal of the Operational Research Society，2008，59：34-43.

[16] Brunner J O，Bard J F，Kolisch R.Flexible shift scheduling of physicians[J].Health Care Management Science，2009，37（12）：285-305.

[17] Knust S，Schumacher E.Shift scheduling for tank trucks[J].Omega-International Journal of Management Science，2011，39：513-521.