戴 韜，李軍祥

DAI Tao1,LI Junxiang2

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

2.上海理工大學(xué) 管理學(xué)院，上海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ùn)營(yíng)模式已廣泛應(yīng)用于各社會(huì)各行業(yè)中，成為各自保持客戶(hù)聯(lián)系的關(guān)鍵渠道與制勝法寶。多技能指呼叫中心能提供超過(guò)一種的服務(wù)，其坐席人員也被培訓(xùn)有一種或多種服務(wù)的技能。多技能呼叫中心是呼叫中心發(fā)展的必然形態(tài)。

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

1.2 班次設(shè)計(jì)的內(nèi)涵

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

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

（2）按照預(yù)測(cè)的每個(gè)時(shí)間段的來(lái)電量，在滿(mǎn)足服務(wù)水平的前提下，確定各技能的人員數(shù)量；

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

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

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

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

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

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

2 文獻(xiàn)綜述

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

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

對(duì)于班次設(shè)計(jì)的研究不僅僅局限于呼叫中心領(lǐng)域，文獻(xiàn)[14]綜述了人員排班領(lǐng)域的文獻(xiàn)；文獻(xiàn)[15]研究了多工作點(diǎn)的班次設(shè)計(jì)問(wèn)題；文獻(xiàn)[16]研究了醫(yī)療服務(wù)行業(yè)的班次設(shè)計(jì)問(wèn)題；文獻(xiàn)[17]研究了運(yùn)輸行業(yè)的班次設(shè)計(jì)問(wèn)題。

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

3 模型與算法設(shè)計(jì)

3.1 基本思路

3.2 連續(xù)性班次設(shè)計(jì)模型

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

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

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

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

3.3 空閑勞動(dòng)力計(jì)算

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

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

模型2人力需求轉(zhuǎn)換模型（時(shí)間段→班次）

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

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

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

3.4 休息時(shí)間加入

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

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

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

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

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

3.5 算法設(shè)計(jì)

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

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

（1）找出Zt值為1 的所有時(shí)刻t；

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

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

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

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

圖1 兩階段班次設(shè)計(jì)算法示意圖

4 算例實(shí)驗(yàn)

4.1 算例假設(shè)

本文的算例跟文獻(xiàn)[3]中的一致，其結(jié)構(gòu)如圖2所示。

圖2 某呼叫中心結(jié)構(gòu)圖

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

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

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

4.2 算例求解

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

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

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

圖3 某天電話(huà)3 人力需求與供給

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

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

其余各班次也得到類(lèi)似的結(jié)果。通過(guò)算例也發(fā)現(xiàn)了兩個(gè)不甚滿(mǎn)意的地方：

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

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

5 結(jié)論

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

由于算法是分步進(jìn)行的，每次僅得到局部的最優(yōu)，特別是在連續(xù)性班次下人員供給曲線(xiàn)與需求曲線(xiàn)切合得較好的區(qū)域，為了能得到足夠的空余人力保證休息時(shí)間，需要不斷增加額外的上班人數(shù)，不單因?yàn)榈螖?shù)過(guò)多影響了求解速度，與全局最優(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.