胡修武,徐 悅,王秀利

(南京理工大學(xué)經(jīng)濟管理學(xué)院,江蘇南京210094)

1 引 言

呼叫中心(Call Center/Contact Center)是通過電話等電信媒介手段為顧客提供產(chǎn)品售后支持、訂購交易等服務(wù)的組織實體.呼叫中心屬于勞動密集型行業(yè),人力成本占運營成本的70%左右;呼叫中心人力運作管理引起了學(xué)術(shù)界廣泛研究興趣[1,2].近年來,隨著更多制造商專注于核心業(yè)務(wù)能力提升而愿意把產(chǎn)品售后電話服務(wù)外包出去,國內(nèi)從事呼叫服務(wù)業(yè)務(wù)的呼叫中心企業(yè)越來越多,行業(yè)規(guī)模擴展迅速[3].實際調(diào)研發(fā)現(xiàn),呼叫中心企業(yè)面臨著年輕員工自我意識強、對工作條件及環(huán)境要求較高和離職率居高不下等情況.坐席人力排班時,企業(yè)除了考慮勞動法規(guī)合同要求,越來越注重納入人性化管理因素來提高員工滿意度,從而有助于提升服務(wù)效率.

呼叫中心人力運作管理研究大致可分為人力需求計算、路由策略和人力排班.人力需求計算或路由策略研究成果很多,而呼叫中心排班問題研究相對較少[4?7].最近,Defraeyen和van Nieuwenhuyse對呼叫中心排班問題研究成果進行綜述[7].一些呼叫中心排班問題研究假設(shè)計劃周期為日期,考慮日內(nèi)各種實際場景因素,如坐席人員多技能[8,9]、區(qū)段人力需求隨機動態(tài)性[10]、各班次不同成本及交叉培訓(xùn)成本[11]、或連續(xù)區(qū)段人力需求關(guān)聯(lián)性[12]等,構(gòu)建坐席人員排班問題(隨機)整數(shù)規(guī)劃模型,并分別提出最優(yōu)算法以及啟發(fā)式或智能算法.這些研究因計劃周期是日期,不涉及員工休班及不同日期班次關(guān)聯(lián)等決策問題.也有少數(shù)學(xué)者研究計劃周期為單周的呼叫中心排班問題,構(gòu)建整數(shù)規(guī)劃模型并提出優(yōu)化算法[13,14].與行業(yè)內(nèi)文獻[13,14]不同,本文研究明確納入了雙休日休班公平性考慮,并通過同班次用工約束來保證員工上班規(guī)律性.我們注意到,近些年來其它行業(yè)(如醫(yī)療[15?17]、運輸物流[18,19]和零售[20]等)的人力排班研究中,考慮了雙休日休班或其它方式的排班公平性.不難看出,呼叫中心行業(yè)在用工規(guī)定、業(yè)務(wù)需求分布和人力班次結(jié)構(gòu)等方面與這些行業(yè)不同.盡管本文排班問題也同樣納入雙休日休班公平性等因素,但呼叫行業(yè)本身特點決定了研究模型方法不同于這些行業(yè)人力排班問題.

與國外同行業(yè)普遍周薪制不同,國內(nèi)呼叫中心通常實行月薪制,通過編制月度排班表對坐席人力進行計劃管理.班表編制時,通過保證雙休日休班公平和周內(nèi)同班次當班來體現(xiàn)企業(yè)人性化管理理念.針對該實際排班場景,本文給出了制定排班方案的優(yōu)化模型和方法,并且量化分析了這些人性化管理因素對人力成本控制的影響.本文創(chuàng)新性體現(xiàn)在兩方面,一是通過分析推導(dǎo),取得了反映排班問題優(yōu)化規(guī)律的一些理論結(jié)果;二是在借鑒已有研究成果基礎(chǔ)上,通過利用問題本身結(jié)構(gòu)和優(yōu)化性質(zhì),提出了求解排班方案的優(yōu)化模型和算法.實例計算驗證了排班模型和算法的有效性;研究表明在兼顧休班公平性和上班規(guī)律性情況下,仍能夠?qū)ε虐嗳肆Τ杀具M行有效控制.

2 坐席人員排班模型

研究的排班問題中,假設(shè)用工制度除了反映國內(nèi)勞動法規(guī)要求,還包括以下兩點體現(xiàn)人性化管理的約束因素.首先,基于生活、社交和子女教育等原因,大多數(shù)員工愿意雙休日休班.為了照顧員工生活方便性及體現(xiàn)公平性,排班時在班表周期內(nèi)要保證每個員工雙休日休班不少于規(guī)定次數(shù).其次,由于坐席人員排班的復(fù)雜性,手工排班經(jīng)常致使周內(nèi)當班班次不同的員工占比偏高.當班班次頻繁切換對員工工作及生活具有很大負面影響.為了保證工作時間規(guī)律性,規(guī)定每個員工周內(nèi)工作日同班次當班.

本文排班問題具體描述為,在滿足服務(wù)水平指標要求和企業(yè)用工制度約束情況下,確定連續(xù)4周內(nèi)坐席人員當班與休班日期,以及當班日期班次,使得坐席人員使用數(shù)量最少(即優(yōu)化人力成本).具體說明如下.

呼叫服務(wù)系統(tǒng)可用排隊論模型來描述,其中假設(shè)顧客電話到達率服從泊松分布,坐席人員服務(wù)率服從指數(shù)分布.服務(wù)水平指標通常采用隊列中顧客呼入電話在給定等待時間內(nèi)接通的百分率(Telephone Service Factor,TSF)刻畫.給定服務(wù)指標TSF,使用排隊論方法Erlang C可計算出達到指標TSF需要的最少坐席人員數(shù)量[1,2,7].目前,Erlang C 因簡單易用,仍然是最為廣泛使用的人力需求計算方法.該方法由于沒有考慮服務(wù)隊列中的棄話現(xiàn)象,計算的人力需求往往偏大.若考慮隊列棄話現(xiàn)象并假設(shè)顧客耐心時間服從指數(shù)分布,就是模型Erlang A.很多學(xué)者推薦使用Erlang A來計算坐席人力需求[2,7,14].本文采用Erlang A計算坐席人力需求,用計算出的最少坐席人員需求數(shù)量來刻畫服務(wù)指標TSF要求.

企業(yè)用工制度既反映國內(nèi)勞動法規(guī)合同要求,也體現(xiàn)企業(yè)自身管理偏好.本文假設(shè)用工制度包括,S1:員工每周當班天數(shù)不應(yīng)超過5天,每天最多1 個班次當班.S2:員工4 周內(nèi)至少1 個雙休日休班.S3:員工雙休日兩天要么全當班,要么全休班.S4:員工周內(nèi)工作日當班班次相同,不同周當班班次可以不同.約束S1反映國內(nèi)勞動法規(guī)對員工休班天數(shù)的規(guī)定.在4周排班表中,由于每周雙休日總需要安排部分員工當班來提供呼入話務(wù)服務(wù),盡管大多數(shù)員工愿意雙休日休班,客觀上只能安排部分員工雙休日休班.規(guī)定S2通過保證每個員工至少1個雙休日休班來體現(xiàn)周末休班公平性.規(guī)定S3既反映員工雙休日完整休班意愿,又方便企業(yè)安排更多員工雙休日休班.其它行業(yè)人力排班研究中也考慮了用工規(guī)定S2 和S3(如見綜述文獻[19]).規(guī)定S4保證員工周內(nèi)上班時間規(guī)律性,有助于提升員工服務(wù)效率.計劃周期假設(shè)為4個連續(xù)完整周,利用上述排班問題優(yōu)化解,適當補充改動后很容易獲得月度排班優(yōu)化方案.為了方便問題模型和算法描述,定義的參數(shù)與決策變量符號見表1.

表1 參數(shù)和決策變量說明Table 1 The description of parameters and decision variables

下面構(gòu)建坐席人員排班優(yōu)化問題的整數(shù)線性規(guī)劃模型(ILP1)

其中式(1)描述達到指標TSF要求的區(qū)段當班坐席人力.式(2)表示S1規(guī)定的員工每天最多1個班次當班.式(3)和式(4)描述決策變量之間關(guān)系.式(5)表示S1規(guī)定的員工周內(nèi)當班天數(shù)限制.式(6)表示最優(yōu)解方案中員工4周內(nèi)至少當班1天.式(7)表示S3規(guī)定的員工雙休日要么全休班,要么全當班.式(8)(結(jié)合式(7))描述S2規(guī)定的4 周內(nèi)員工至少1個雙休日休班.式(9)描述S4規(guī)定的員工在周內(nèi)工作日同班次當班約束,式中M0取充分大正整數(shù).每個員工e在周w內(nèi)的工作日是否當班和周內(nèi)當班班次均為決策變量,這意味著規(guī)定S4蘊含著可能出現(xiàn)的25|S|種同班次當班情況.對每個員工e,式(9)通過包含的5|S|個具體約束式(s ∈S和d′=1,2,...,5)來刻畫所有同班次當班情況.在5|S|個約束式中,至少存在1個式子以條件”某個班次當班天數(shù)不少于當班總天數(shù)”成立,來保證員工e滿足規(guī)定S4;而其它式子會因右邊第2項取充分小負整數(shù),在邏輯上成立但不起約束作用.反之,如果員工e在周內(nèi)當班班次不同,則在5|S|個約束式中總存在不能成立的式子.

3 問題分析

本節(jié)首先給出人力需求計算方法,然后分析坐席人力需求特征和推導(dǎo)問題優(yōu)化性質(zhì).本文人力需求泛指基于呼入話務(wù)量的當班人力需求或納入用工制度約束后的坐席人員數(shù)量需求.

3.1 人力需求計算

呼叫服務(wù)系統(tǒng)中,呼入電話到達率或坐席人員處理時間都是隨機變量.當話務(wù)處理時間相對區(qū)段長度較短情況下,則系統(tǒng)在區(qū)段內(nèi)會很快進入穩(wěn)定狀態(tài).在該情況下,可把每個區(qū)段的呼叫服務(wù)過程看作獨立馬爾科夫生滅過程(Markovian birth-death process),即滿足SIPP(stationary independent period-by-period)條件[1,2,14].若假設(shè)日期d內(nèi)區(qū)段t的呼入電話到達率服從數(shù)學(xué)期望為λtd的泊松分布,std個坐席人員話務(wù)處理時間和顧客耐心時間分別服從數(shù)學(xué)期望為htd(服務(wù)率μtd=1/htd)和b的指數(shù)分布,則可用排隊論模型Erlang A 來近似計算坐席人力需求.

在馬爾科夫生滅過程中,令Ptd(n)表示在日期d的區(qū)段t內(nèi),呼叫服務(wù)系統(tǒng)有n個顧客的狀態(tài)概率,則下列關(guān)系式成立,即

式(10)和式(11)表明,隨著n增大,該生滅過程中的電話死亡率會逐漸超過出生率(到達率),從而會導(dǎo)致狀態(tài)概率以超過幾何速度變小.為了能夠顯式表達狀態(tài)概率,可在規(guī)定誤差范圍內(nèi),忽略高階狀態(tài)概率.把顧客等待隊列長度限定在上界為N的狀態(tài)空間內(nèi),使得被截去隊列長度大于N的狀態(tài)概率之和不會超過給定誤差ε.令ρ=λtd/{std/htd+(N ?std)/b},考慮如下關(guān)系式

式(12)意味著只要確定充分大N,則能夠使得被截去狀態(tài)概率之和小于ε.確定N后,在隊列長度為0至N的狀態(tài)空間內(nèi),可重新歸一化計算概率(n),使得

在馬爾科夫生滅過程X={X(t)|t0}中,令Pr{W > τ|X=n}表示系統(tǒng)中有n個顧客情況下,顧客等待時長W超過給定時間τ的概率.Pr{W >τ|X=n}可根據(jù)下列定理計算.

定理1(見文獻[21])在馬爾科夫生滅系統(tǒng)中,對任意給定的τ >0,有

成立.

設(shè)Ltd表示日期d內(nèi)區(qū)段t的服務(wù)指標TSF,即所有等待顧客在不超過時長τ內(nèi)接通電話的百分占比.根據(jù)以上分析,則有

給定TSF指標Ltd,可計算需要最少坐席人員數(shù)量rtd如下:初始化,設(shè)坐席人員數(shù)rtd=和確定狀態(tài)概率截斷誤差ε(如10?5),計算出TSF指標L′td.若L′td

3.2 優(yōu)化性質(zhì)

由于考慮休班和同班次等用工約束,問題模型ILP1求出的員工數(shù)量可能多于班表具體日期內(nèi)所需要的坐席人力數(shù)量.下面首先通過構(gòu)建整數(shù)規(guī)劃模型界定為了滿足話務(wù)服務(wù)指標要求而每日需要的最少坐席人力,然后通過分析每日最少坐席人力需求與排班周期內(nèi)用工制度約束之間的關(guān)系,推導(dǎo)出問題ILP1下界.

令Q?wd表示在周w的日期d達到日內(nèi)話務(wù)服務(wù)指標要求所需要的最少坐席人力,這里w=1,2,3,4和d=1,2,...,7.給定日內(nèi)區(qū)段人力需求,則Q?wd可由下列整數(shù)規(guī)劃模型(ILP2)求出,即

令A(yù)w6=Q?w6和Aw7=Q?w7.設(shè)Aw表示周w雙休日需要的最少當班坐席人員數(shù)量.考慮用工制度規(guī)定S3,則有Aw= max{Aw6,Aw7}.模型ILP2描述的日排班調(diào)度問題盡管與問題ILP1不同,但容易看出,模型ILP1最優(yōu)解方案在周末日期d的排班結(jié)果也是該日期模型ILP2的可行解,從這個意義來說,模型ILP2求出的最優(yōu)員工數(shù)量是模型ILP1的下界.進一步分析,根據(jù)用工制度規(guī)定S2,每個雙休日除了要安排一些員工當班來滿足日內(nèi)所有區(qū)段人力需求,還可能要安排部分員工休班.同時考慮排班周期內(nèi)4周雙休日當班和休班人力情況,可給出排班問題下界.

引理1問題最優(yōu)目標值V ?滿足下列條件:

1)V ?max{A1,A2,A3,A4};

2)V ?(A1+A2+A3+A4)/3,這里表示不小于“·”的最小整數(shù).

證明1) 結(jié)論顯然成立.2) 令uw表示最優(yōu)解中周w雙休日休班坐席人員數(shù)量.則對于w= 1,2,3,4,有V ?Aw+uw成立.故4V ?(A1+u1)+···+(A4+u4) = (A1+···+A4)+(u1+···+u4)成立.根據(jù)用工制度規(guī)定S2,則有u1+···+u4V ?成立.于是有3V ?A1+···+A4.考慮到V ?為整數(shù),故結(jié)論2)成立.證畢.

若僅考慮每周內(nèi)具體工作日人力需求,令Bwd表示周w工作日d需要的最少當班坐席人員數(shù)量,則Bwd=Q?wd,這里w= 1,2,3,4 和d= 1,2,...,5.由于規(guī)定S1要求每個員工周內(nèi)雙休日或工作日至少休班2 天,同時考慮每周工作日當班和休班人力情況,可導(dǎo)出如下結(jié)論.

引理2問題最優(yōu)目標值V ?滿足下列條件:

1)V ?max{Bwd|w=1,2,3,4;d=1,2,...,5};

2)V ?[2Aw+(Bw1+···+Bw5)]/5,其中w=1,2,3,4.

證明1) 結(jié)論顯然成立.下面證明結(jié)論2).在問題最優(yōu)解中,令uw和vw分別表示周w雙休日或工作日休班的坐席人員數(shù)量; 令uwd表示周w工作日d休班的坐席人員數(shù)量.對所有日期d= 1,2,...,5,V ?Bwd+uwd成立.于是,成立.注意到和V ?Aw+uw,有7V ?成立.考慮到每個坐席人員周內(nèi)至少休班2天,且要么在雙休日休班,要么在工作日休班,故V ?uw+vw成立.因此,成立.注意到V ?,Aw和Bwd均為非負整數(shù),故結(jié)論2)成立.證畢.

由模型ILP2求出最優(yōu)解Aw6,Aw7和Bwd后,這里w= 1,2,3,4 和d= 1,2,...,5,根據(jù)引理1和引理2,可確定問題ILP1的下界,記為M.

如果不要求坐席人員周內(nèi)工作日當值班次相同,即松弛用工制度S4,稱之為原問題ILP1的松弛問題.在模型ILP1中,去掉約束條件式(9)后,即為松弛問題整數(shù)規(guī)劃模型描述,記為SILP1.對于松弛問題SILP1,有如下結(jié)論.

定理2松弛問題SILP1最優(yōu)解需要坐席人員數(shù)量為M.

證明明顯的,松弛問題SILP1的最優(yōu)解中員工數(shù)量不會少于M.若M個員工可生成松弛問題SILP1的一個可行解,則結(jié)論成立.具體分析如下.

不失一般性,假設(shè)問題ILP1的下界M在第1周取得.考慮下列4種所有可能的情況:i)M=A1; ii)M=1+A2+A3+A4/3;iii)M=B1d,這里d ∈D1和iv)M=[2A1+(B1,1+···+B1,5)]/5.

i)當M=A1時

該情況下,可安排所有M個員工在本周雙休日當班; 而在其它3周雙休日分別安排M ?A2,M ?A3和M ?A4個員工休班.于是,所有員工在4周雙休日休班的次數(shù)為(M ?A2)+(M ?A3)+(M ?A4)=3M ?(A2+A3+A4).由引理1可知,M(A1+A2+A3+A4)/3,注意到M=A1,則有A2+A3+A42M.于是,有(M ?A2)+(M ?A3)+(M ?A4)M.該式意味著能夠保證M個員工每人在4周內(nèi)至少有1 個雙休日休班.

由引理2可知,M(2A1+B1,1+···+B1,5)/5.注意到M=A1,于是,有B1,1+···+B1,53M.該情況下,考慮到員工均在本周雙休日當班,則本周5個工作日中需要安排2M個休班日期.由于周內(nèi)工作日需要當班班次總數(shù)為B1,1+···+B1,5,而5M ?(B1,1+···+B1,5)2M,于是,M個員工每人可在工作日安排至少2天休班.另一方面,安排2M個休班日期之后,員工在周內(nèi)工作日仍可當值3M個班次.由于本周人力需求B1,1+···+B1,53M,故總可以滿足周內(nèi)工作日人力需求.所以,該情況下M個員工可生成本周內(nèi)可行解方案.

ii)當M=(A1+A2+A3+A4)/3時

該情況下,4周雙休日可安排休班員工數(shù)依次為M ?A1,M ?A2,M ?A3和M ?A4.于是,在雙休日休班的員工總數(shù)為4M?(A1+A2+A3+A4).考慮到A1+A2+A3+A43M,則4M?(A1+A2+A3+A4)M.該式意味著能夠保證M個員工每人至少有1個雙休日休班.

該情況下,本周5個工作日中需要安排2A1個休班日期.由引理2可知,M(2A1+B1,1+···+B1,5)/5,即5M ?(B1,1+···+B1,5)2A1成立.該式意味著本周5個工作日內(nèi)可安排另外2A1個日期休班.另一方面,安排2A1個休班日期之后,員工在周內(nèi)工作日仍可當值5M ?2A1個班次.由于本周人力需求B1,1+···+B1,55M ?2A1,故總可滿足本周內(nèi)工作日人力需求.所以,M個員工可生成本周內(nèi)可行解方案.

針對情況iii)和iv),通過與情況ii)相似分析,可以說,M個員工能夠生成松弛問題SILP1本周內(nèi)的可行解方案.對于第2周、第3周或第4周,通過與第1 周情況相似分析,可以斷定M個員工能夠生成該周內(nèi)可行解方案.于是,結(jié)論成立.證畢.

由引理1和引理2可知,問題ILP1最優(yōu)解方案至少需要M個坐席人員.由定理2可以推斷,若在用工制度S4約束下,M個坐席人員也能生成問題ILP1可行解,則得到其最優(yōu)解方案.一般情況下用工制度規(guī)定S4可能導(dǎo)致問題ILP1需要更多坐席人力.

定理2保證M個坐席人員可生成松弛問題SILP1最優(yōu)解.不難找出1個問題實例,使得M個坐席人員是問題ILP1的最優(yōu)解;也就是說,問題ILP1的下界M是最大下界.在問題ILP1 最優(yōu)解中,有的坐席人員可能不止1個雙休日休班.在算法設(shè)計中,如果能夠合理利用最大下界M,則可以有效避免雙休日休班過量指派.M個坐席人員排班需要同時考慮用工制度約束S2和S4;而其它坐席人員均可安排在雙休日休班,在工作日當班只要滿足約束S4即可.

4 啟發(fā)式算法

基于上節(jié)分析,啟發(fā)式算法可采用結(jié)構(gòu)分解技巧.一是基于松弛問題SILP1最優(yōu)解是問題ILP1最大下界,可把候選坐席人員列表從數(shù)量上分為一定或僅可能屬于最優(yōu)解兩部分;針對兩類坐席人員采用不同指派策略.二是把表征人力需要的待指派班次分為屬于雙休日或工作日兩部分,分別采用不同指派策略.在工作日班次指派中,無論當班日期或班次選擇都進行局部優(yōu)化和體現(xiàn)貪婪搜索思想.提出的啟發(fā)式算法描述如下.

啟發(fā)式算法H

步驟1由模型ILP2分別計算問題下界Aw和Bwd;并由引理1和引理2確定最大下界M.設(shè)定坐席人員列表集E1={1,2,...,M}.

步驟2對E1中員工進行雙休日班次指派.對w= 1,2,3,4,設(shè)mw=M ?Aw和ˉmw= ˉmw?1+mw,這里=0.對w=1,2,3,4,依次進行下列操作:

2–1 設(shè)k0=0和b0=0.確定kw和bw,使得ˉmw=kwM+bw成立,這里0bw 0,則把員工1,2,...,mw安排在本周雙休日休班.iii)若kw=kw?1+1,則把員工Aw+1,Aw+2,...,M安排在本周雙休日休班.

2–2 在模型ILP2分別求出的周六和周日最優(yōu)解中,針對個相同當班班次(即滿足x?w6es=x?w7es=1)需求,把E1中未安排休班的個員工指派到這些雙休日班次當班.

2–3 對Aw6?個其它當班班次,把E1中尚未指派的Aw6?個員工指派到周六這些班次當班;對Aw7?個其它當班班次,把E1中尚未指派的Aw7??個員工指派到周日這些班次當班.

2–4 若Aw6Aw7,則把在周日尚未指派的Aw6?Aw7個員工,安排與其周六相同班次當班.

步驟3對w=1,2,3,4,把E1分為E′w={iw,1,iw,2,...,iw,M?Aw}和E′′w={iw,M?Aw+1,iw,M?Aw+2,...,iw,M}兩個子集,其中,E′w中員工在本周雙休日休班,而E′′w中員工雙休日當班.設(shè)Uw=(rwdt)5×ˉt為周w工作日區(qū)段人力需求矩陣;對工作日d=1,2,...,5,設(shè)Uwd=(rwd1,rwd2,...,rwdˉt)T為周w日期d的區(qū)段人力需求向量.

步驟4對w=1,2,3,4,就E′w和E′′w中員工工作日進行班次指派.對員工e=iw,1,iw,2,...,iw,M?Aw和員工e=iw,M?Aw+1,iw,M?Aw+2,...,iw,M,依次進行下列操作:

4–1 在Uw中選擇區(qū)段(d′,t′),使得rwd′t′=max{rwdt|t ∈T,d=1,2,...,5}成立;若有多個t′使得rwd′t′相同,則選擇使集{rwdt′|d=1,2,...,5}含正整數(shù)元素最多的區(qū)段(d′,t′);

4–2 若e ∈E′w,則令當班日期集D′w=Dw{6,7},轉(zhuǎn)入步驟4–3;若e ∈E′′w,則確定當班日期集如下:

4–3 設(shè)?S={si|si ∈S,asit′=1}和={rwdt1,rwdt2,...,rwdtc}表示由Uwd中c個最大值組成的子集.對每個si ∈和d ∈D′w,定義指標ζw(si,d)={rwdt|asit=1,rwdt ∈,rwdt >0}為班次si覆蓋中非零元素的子集.

4–5 對所有d ∈D′w和班次覆蓋區(qū)段t,如果rwdt >0,則令rwdt ←rwdt?1;使用新rwdt更新替換Uw和Uwd中相應(yīng)位置元素.

4–6 當Uw >0時,區(qū)分以下情況:i)若e=iw,k且k 0成立,則令e ←iw+1,1,轉(zhuǎn)入步驟4–1;否則,轉(zhuǎn)入步驟5.iii)若e=iw,M且w= 4,轉(zhuǎn)入步驟5.

當Uw=0時,則令E′w和E′′w中e之后的所有員工在本周工作日休班;若存在下個周w使得Uw>0成立,則令e ←iw+1,1,轉(zhuǎn)入步驟4–1;否則,則由E1中坐席人員已生成解方案,結(jié)束.

步驟5設(shè)e=M+1和E2={e},進行下列操作:

5–1 對所有的Uw1,...,Uwh >0,安排員工e在這些周的雙休日休班,并通過與步驟4–1至步驟4–5 相似的操作,把員工e指派到這些周工作日當班;同時,對其它滿足Uw=0 的周,安排員工e該周內(nèi)休班.

5–2 若存在至少1個周使得Uw >0成立,則令e ←e+1和E2=E2∪{e},轉(zhuǎn)向步驟5–1;否則,則由E1∪E2中坐席人員已生成解方案,結(jié)束.

在假設(shè)工作區(qū)段數(shù)ˉt和班次數(shù)ˉs給定情況下,排班問題規(guī)?？捎萌肆π枨筝斎?yún)?shù)

來刻畫.容易看出,步驟4的每個員工指派過程中,至少存在1個周,使得該周工作日當班班次至少覆蓋1個區(qū)段的有效人力需求(即指派后該區(qū)段剩余人力需求滿足rwdt ?10);另一方面,每個員工4 周內(nèi)當班/休班指派的計算時間不會超過O(max{4×52×,4×5×ˉs}),其中大括號內(nèi)前項計算確定員工當班日期(步驟4–1 和步驟4–2),而后項確定當班班次(步驟4–3和步驟4–4).考慮到ˉt和ˉs是問題常數(shù),所以說,步驟4 的計算時間為O(rsum).相似分析可推斷步驟5的計算時間也不超過O(rsum).另外,其它步驟2和步驟3計算時間并不占優(yōu).因此,在步驟1 使用模型ILP2求出最大下界M之后,算法H中步驟2 至步驟5 的計算時間復(fù)雜度為O(rsum).

在算法H中,步驟2在每個周w雙休日總是指派Aw個坐席人員當班.無論周六或周日需要當班員工數(shù)不會超過Aw,因此,生成解能夠滿足雙休日人力需求.在每個周w的工作日,步驟4至步驟5依次把坐席人員指派到具體班次當班,直至周內(nèi)工作日區(qū)段人力需求Uw= (rwdt)5×ˉt被滿足.所以,生成解也能滿足工作日人力需求.

由引理1和引理2可知,問題最少需要M個坐席人員在4周計劃周期內(nèi)當班.從步驟2至步驟4 可以看出,對集E′w中M個坐席人員,每周有M ?Aw個人至少在雙休日休班,而Aw個人至少在工作日休班2天.若生成解中還有另外|E2|個坐席人員當班,由步驟5可知,這|E2|個坐席人員至少會在周內(nèi)雙休日休班.所以,生成解能夠滿足用工制度約束S1.

在步驟2的2–1中,每周指派M ?Aw個不同坐席人員雙休日休班,4周共指派4M ?(A1+A2+A3+A4)個雙休班.由引理1 的2)可知,4M ?(A1+A2+A3+A4)M.進一步分析步驟2–1可知:指派始于第1周的情況i)k1=k0= 0,對所有情況i)ki=ki?1= 0 指派后,必然出現(xiàn)情況iii)kw=kw?1+1 = 1的指派.當該情況出現(xiàn)時,由于=M+bw=+mwM和< M,則bwmw.于是,在該情況下對坐席人員Aw+1,Aw+2,...,M的休班指派必然覆蓋坐席人員bw?1+1,bw?1+2,...,M.因此,考慮到所有ki=ki?1= 0情況已對坐席人員1,2,...,bw雙休日休班進行指派,情況iii)休班指派之后,已經(jīng)可保證集E1的M個坐席人員均在雙休日至少休班1次.對于生成解中其它坐席人員,步驟5均指派他們在每周雙休日休班.因此,生成解能夠滿足用工制度約束S2.另外,從步驟4至步驟5容易看出,生成解也滿足用工制度S3和S4.總結(jié)以上分析,有以下結(jié)論.

定理3啟發(fā)式算法H生成問題ILP1的可行排班方案.

由定理2和定理3可知,若算法H結(jié)束于步驟4,則生成解是最優(yōu)排班方案.由于用工制度規(guī)定S4可能致使需要更多坐席人力配置,步驟5通過采用類似步驟4 的局部優(yōu)化策略來補充配置更多坐席人力.

5 計算實驗

某呼叫中心企業(yè)承包若干制造商電子產(chǎn)品售后電話服務(wù)業(yè)務(wù).企業(yè)把坐席人員分為若干服務(wù)群組,每個服務(wù)群組由十幾到幾十個坐席人員不等組成,提供由相近產(chǎn)品組成的產(chǎn)品線話務(wù)服務(wù)支持.坐席人員的當班班種班次設(shè)置見表2.假設(shè)日內(nèi)區(qū)段時長為1 h,根據(jù)區(qū)段電話實際呼入量以及承包合同指標TSF要求,使用該群組坐席服務(wù)時間統(tǒng)計量,采用Erlang A方法可計算出所有區(qū)段坐席人力需求數(shù)量rwdt;該參數(shù)用來表示排班服務(wù)指標TSF要求.計算使用臺式計算機的CPU為Intel 酷睿i7四核處理器,主頻為2.8GHz.計算實驗采用CPLEX 12.1求解整數(shù)規(guī)劃模型;使用C++編程實現(xiàn)啟發(fā)式算法H.

表2 某呼叫中心的班種班次列表Table 2 List of shift-types and shifts in a call center

5.1 實例計算

下面通過問題實例,說明啟發(fā)式算法H的計算過程及結(jié)果.

1)區(qū)段人力需求計算

呼叫中心服務(wù)群組工作時間如表2中班次覆蓋的15個區(qū)段,依次分別用符號t1,t2,...,t15來表示.企業(yè)承包制造商服務(wù)合同的指標TSF 要求取值85%.根據(jù)該群組最近半年(26周)實際數(shù)據(jù)樣本,通過檢驗擬合分析,確定坐席人員服務(wù)率μtd取值0.305/min,顧客耐心時間b取值3.45 min.表3列出該實例每日電話呼入統(tǒng)計量.由表3可看出,周內(nèi)不同日期電話呼入量差異明顯,需要合適指派員工當班/休班日期來滿足不同日話務(wù)量服務(wù)需求.使用Erlang A可計算出4周所有工作區(qū)段人力需求.表4列出第2周的周一所有區(qū)段電話實際呼入量和人力需求計算結(jié)果.由表4可看出,日內(nèi)不同區(qū)段電話呼入量存在波峰波谷現(xiàn)象,需要通過合適安排員工班次來有效應(yīng)對日內(nèi)人力需求變化.

表3 問題實例每日電話呼入統(tǒng)計量Table 3 Daily inbound calls of the problem instance

表4 某日內(nèi)區(qū)段呼入量和計算的人力需求分布Table 4 Inbound calls of intervals and calculated labor demands one day

2)員工雙休日指派情況

算法H中,步驟1通過模型ILP2計算的(A1,A2,A3,A4)=(6,6,7,7),計算的所有Bwd依次列表為(8,7,7,8,7; 9,9,8,8,8; 8,8,7,8,7; 9,7,9,9,8).由引理1和引理2計算出M=12.步驟2通過對M個坐席人員4個周末當班/休班指派,一方面保證滿足每個雙休日人力需求,另一方面保證每個坐席人員至少1個雙休日休班.由于M個坐席人員尚未覆蓋4周所有工作日人力需求,需要通過步驟5 指派坐席人員e13在一些工作日當班.該情況下,坐席人員e13在4個雙休日休班.坐席人員雙休日當班/休班情況見表5.

表5 坐席人員雙休日當班/休班情況Table 5 Attendance of agents on weekends

3)員工工作日指派情況

算法H中,步驟4對坐席人員e1至e12的每周工作日進行休班或當班班次指派.步驟4的班次指派,都是挑選覆蓋周內(nèi)工作日區(qū)段人力需求最多的班次,體現(xiàn)了局部貪婪優(yōu)化思想.步驟5指派坐席人員e13在第4周工作日當班情況為s11{1,3,4,5},其它周工作日均休班.所有坐席人員工作日當班/休班情況見表6.表中符號,如s3,表示坐席人員周內(nèi)所有工作日班次s3當班;s2{4,5}表示坐席人員在周內(nèi)周四和周五休班,其它工作日班次s2當班;“—”表示坐席人員周內(nèi)所有工作日休班.

表6 坐席人員周內(nèi)工作日當班/休班情況Table 6 Attendance of agents on weekdays

5.2 實驗分析

5.2.1 性能評估

從呼叫中心小規(guī)模服務(wù)群組選擇10個問題實例,分別使用ILP1模型和啟發(fā)式算法H求解排班問題,記錄了算法計算時間(s)和計算出的坐席人員數(shù)量.這里假設(shè)若在1小時內(nèi)尚未得到最優(yōu)解,則認為模型ILP1無法獲得最優(yōu)解.具體計算結(jié)果見表7.

根據(jù)表7,從計算成本與優(yōu)化性能兩方面,對模型和算法分析如下,①模型ILP1 對10個實例的平均計算時間為1 916.5 s,其中2個實例在3 600 s 內(nèi)未能獲得最優(yōu)解.這表明該排班問題本質(zhì)上是非常復(fù)雜組合優(yōu)化問題.模型ILP1盡管理論上說可求得問題最優(yōu)解,但由于其計算成本過大,只適合求解小規(guī)模問題.②啟發(fā)式算法H對10個實例的平均計算時間為35.6 s,遠小于模型ILP1的計算成本.這表明該算法具有良好的計算性能.③從優(yōu)化性能上看,算法H 發(fā)現(xiàn)10個實例中的5個最優(yōu)解,其它實例情況只與最優(yōu)解(或下界)多1人.這表明算法H無論逐步分解結(jié)構(gòu),或者班次覆蓋區(qū)段人力需求特征指標刻畫以及局部優(yōu)化員工指派,能夠充分反映該排班問題內(nèi)在優(yōu)化規(guī)律.算法H能夠獲得小規(guī)模問題實例的最優(yōu)解或次優(yōu)解.

表7 小規(guī)模問題實例計算結(jié)果Table 7 Experimental results of the small-scale problem instances

從較大規(guī)模服務(wù)群組選擇了10個問題實例.由于無法在合理計算時間(1小時內(nèi))使用模型ILP1獲得問題最優(yōu)解,通過下界來評估啟發(fā)式算法H的性能.定義算法H 的性能誤差率=(算法H的解評估下界M)/評估下界M.計算結(jié)果見表8.

根據(jù)表8,對算法H進一步分析如下,①盡管在理論上很難給出步驟1中模型ILP2 求下界M的計算時間復(fù)雜度,但如節(jié)4中分析所示,步驟2至步驟5的計算時間成本O(rsum)是隨著問題規(guī)模而線性增長的.對于10個較大規(guī)模問題實例,模型ILP1在1小時內(nèi)無法獲得最優(yōu)解;但算法H的平均計算時間僅為61.4 s.另外,與表7對照可以看出,算法H隨著問題規(guī)模變大其計算時間增長并不很大.據(jù)此可說,算法H能夠用來求解大規(guī)模排班問題.②從優(yōu)化性能來看,算法H與評估下界M比較,平均性能誤差率不超過5.8%.注意到下界M可能小于最優(yōu)解(參照表7),表中所示誤差率可能低估了算法H的優(yōu)化性能.據(jù)此可說,算法H能夠發(fā)現(xiàn)大規(guī)模排班問題優(yōu)化解.

表8 較大規(guī)模問題實例計算結(jié)果Table 8 Experimental results of the large-scale problem instances

5.2.2 問題討論

排班問題中,用工制度規(guī)定S2+S3體現(xiàn)了坐席人員雙休日休班公平性; 規(guī)定S4 保證坐席人員周內(nèi)工作日當值相同班次.這些排班規(guī)定體現(xiàn)企業(yè)人性化管理理念.通過是否保留模型ILP1中描述用工制度規(guī)定S2+S3及S4的約束條件式,或者使用算法H(適當修改),可計算討論這些規(guī)定因素對排班人力成本控制的影響.計算結(jié)果見表9.

表9 用工制度規(guī)定對人力成本影響計算結(jié)果Table 9 Experimental results about the influence of labor restrictions on human cost

①從表9可看出,無論考慮保證每個員工至少1個雙休日休班,或者保證每個員工每個周內(nèi)工作日同班次當班,都有可能增加排班用工成本.如果同時考慮兩者,用工成本增加可能會更多.表中用工成本最小增長率為0%,意味著針對該實例,借助優(yōu)化模型算法可實現(xiàn)成本最優(yōu),同時兼顧員工雙休日休班公平性和保證周內(nèi)工作日上班規(guī)律性.

②保證員工周內(nèi)工作日上班規(guī)律性(S4)比保證員工雙休日休班公平性(S2+S3)可能需要更多人力成本.從呼叫中心話務(wù)呼入量分布不難看出,一方面,周末呼入量通常比工作日偏少(如見表3),這給員工雙休日休班提供了較多機會;只要借助優(yōu)化模型算法,可較好實現(xiàn)人力成本控制和保證周末休班公平性雙重目標.另一方面,周內(nèi)不同工作日呼入量分布具有不均衡性,同班次規(guī)定某種程度上限制了不同工作日人力匹配靈活性,從而引起人力成本上升.

③從表9可看出,呼叫中心業(yè)務(wù)規(guī)模越小,周末休班公平性和同班次用工制度引起的人力成本增加越大.這意味著小規(guī)模呼叫中心企業(yè)面臨著突出的用工成本控制與人性化管理兩難問題.當呼叫中心企業(yè)規(guī)模較大時,人力成本與人性化管理比較容易平衡.

6 結(jié)束語

針對呼叫中心企業(yè)管理實際需求,研究納入周末休班公平性和周內(nèi)工作日同班次約束的多周排班優(yōu)化問題.通過分析認識問題結(jié)構(gòu)及優(yōu)化規(guī)律,構(gòu)建問題整數(shù)規(guī)劃模型和提出構(gòu)造性啟發(fā)式算法.計算實驗表明規(guī)劃模型適合求解小規(guī)模排班問題最優(yōu)解,而啟發(fā)式算法能夠以小計算成本獲得較大規(guī)模排班問題優(yōu)化解.研究結(jié)果表明在排班問題中納入諸如員工訴求及人性化管理因素,盡管對企業(yè)長期發(fā)展有利,但也可能導(dǎo)致人力成本稍許增加.考慮諸多用工實踐情景的坐席人員排班問題,本質(zhì)上通常是非常復(fù)雜的組合優(yōu)化問題,給學(xué)術(shù)界提供很多研究機會.