胡修武,徐 悅,王秀利

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

1 引 言

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

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

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

2 坐席人員排班模型

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

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

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

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

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

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

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

3 問(wèn)題分析

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

3.1 人力需求計(jì)算

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

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

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

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

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

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

成立.

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

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

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

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

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

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

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

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

證明1) 結(jié)論顯然成立.2) 令uw表示最優(yōu)解中周w雙休日休班坐席人員數(shù)量.則對(duì)于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需要的最少當(dāng)班坐席人員數(shù)量,則Bwd=Q?wd,這里w= 1,2,3,4 和d= 1,2,...,5.由于規(guī)定S1要求每個(gè)員工周內(nèi)雙休日或工作日至少休班2 天,同時(shí)考慮每周工作日當(dāng)班和休班人力情況,可導(dǎo)出如下結(jié)論.

引理2問(wèn)題最優(yōu)目標(biāo)值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).在問(wèn)題最優(yōu)解中,令uw和vw分別表示周w雙休日或工作日休班的坐席人員數(shù)量; 令uwd表示周w工作日d休班的坐席人員數(shù)量.對(duì)所有日期d= 1,2,...,5,V ?Bwd+uwd成立.于是,成立.注意到和V ?Aw+uw,有7V ?成立.考慮到每個(gè)坐席人員周內(nèi)至少休班2天,且要么在雙休日休班,要么在工作日休班,故V ?uw+vw成立.因此,成立.注意到V ?,Aw和Bwd均為非負(fù)整數(shù),故結(jié)論2)成立.證畢.

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

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

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

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

不失一般性,假設(shè)問(wèn)題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)當(dāng)M=A1時(shí)

該情況下,可安排所有M個(gè)員工在本周雙休日當(dāng)班; 而在其它3周雙休日分別安排M ?A2,M ?A3和M ?A4個(gè)員工休班.于是,所有員工在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個(gè)員工每人在4周內(nèi)至少有1 個(gè)雙休日休班.

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

ii)當(dāng)M=(A1+A2+A3+A4)/3時(shí)

該情況下,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個(gè)員工每人至少有1個(gè)雙休日休班.

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

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

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

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

4 啟發(fā)式算法

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

啟發(fā)式算法H

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

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

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)解中,針對(duì)個(gè)相同當(dāng)班班次(即滿足x?w6es=x?w7es=1)需求,把E1中未安排休班的個(gè)員工指派到這些雙休日班次當(dāng)班.

2–3 對(duì)Aw6?個(gè)其它當(dāng)班班次,把E1中尚未指派的Aw6?個(gè)員工指派到周六這些班次當(dāng)班;對(duì)Aw7?個(gè)其它當(dāng)班班次,把E1中尚未指派的Aw7??個(gè)員工指派到周日這些班次當(dāng)班.

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

步驟3對(duì)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}兩個(gè)子集,其中,E′w中員工在本周雙休日休班,而E′′w中員工雙休日當(dāng)班.設(shè)Uw=(rwdt)5×ˉt為周w工作日區(qū)段人力需求矩陣;對(duì)工作日d=1,2,...,5,設(shè)Uwd=(rwd1,rwd2,...,rwdˉt)T為周w日期d的區(qū)段人力需求向量.

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

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

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

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

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

4–6 當(dāng)Uw >0時(shí),區(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.

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

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

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

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

在假設(shè)工作區(qū)段數(shù)ˉt和班次數(shù)ˉs給定情況下,排班問(wèn)題規(guī)模可用人力需求輸入?yún)?shù)

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

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

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

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

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

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

5 計(jì)算實(shí)驗(yàn)

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

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

5.1 實(shí)例計(jì)算

下面通過(guò)問(wèn)題實(shí)例,說(shuō)明啟發(fā)式算法H的計(jì)算過(guò)程及結(jié)果.

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

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

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

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

2)員工雙休日指派情況

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

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

3)員工工作日指派情況

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

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

5.2 實(shí)驗(yàn)分析

5.2.1 性能評(píng)估

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

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

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

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

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

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

5.2.2 問(wèn)題討論

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

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

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

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

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

6 結(jié)束語(yǔ)

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