牟 松，陳穎成，杜晴晴，余龍水，張家華

（1.廣東機(jī)場白云信息科技有限公司，廣州 510470；2.民航運(yùn)籌優(yōu)化算法實(shí)驗(yàn)室，廣州 510006；3.廣東工業(yè)大學(xué)機(jī)電工程學(xué)院，廣州 510006）

0 引言

人員排班問題是一個復(fù)雜的排列組合問題，在規(guī)則組合限定范圍內(nèi)將人員、任務(wù)、時間、地點(diǎn)等進(jìn)行匹配，良好的排班方案對企業(yè)的生產(chǎn)有積極的影響。在實(shí)際的排班過程中，問題復(fù)雜度隨著人數(shù)、任務(wù)數(shù)、規(guī)則數(shù)等增加而激增。手工排班需要花費(fèi)大量時間和精力，而且排班結(jié)果也可能不理想。在交通、醫(yī)療、酒店等領(lǐng)域均有涉及[1－3]，Baker[4]將人員排班問題分為日工時排班、休息日排班和混合排班。Bechtold[5]提出可將人員排班問題的解決方法分為手工排班、整數(shù)規(guī)劃、隱式模型、目標(biāo)規(guī)劃等。Jorne Van den Bergh等[6]對問題從人員特征、約束條件、求解方法等角度進(jìn)行了分類。Brucker P等[7]開發(fā)了一種通用的人員排班模型，并應(yīng)用于幾類具有代表性的人員排班問題，建立了數(shù)學(xué)模型。于貴桃[8]闡述了計(jì)算機(jī)輔助機(jī)組排班模塊中所采用的混合整數(shù)優(yōu)化法的數(shù)學(xué)模型。施俊龍[9]設(shè)計(jì)了話務(wù)中心的排班算法，根據(jù)預(yù)測的話務(wù)量合理地安排話務(wù)員，保證人力、技能都能夠合理部署。魏云飛[10]提出依據(jù)問題的復(fù)雜程度和行業(yè)領(lǐng)域分為大眾運(yùn)輸人員排班、航空公司人員排班和一般人員排班問題。趙煥省[11]研究了機(jī)組排班過程中應(yīng)該遵循的排班規(guī)則，并設(shè)計(jì)了遺傳算法的適應(yīng)度函數(shù)和各項(xiàng)遺傳算子。李丹波[12]總結(jié)出了呼叫中心排班中考慮的約束條件，排班方式為先設(shè)置班次，再建立人員與班次的對應(yīng)關(guān)系。馮霞等[13]提出了面向?qū)哟钨Y質(zhì)的機(jī)場外航服務(wù)人員排班模型，并設(shè)計(jì)了基于禁忌搜索算法的模型求解策略。藏玉清[14]針對智能算法求解電力系統(tǒng)機(jī)組組合時存在的經(jīng)濟(jì)調(diào)度無解問題，提出了一種檢驗(yàn)方法，有效地避免對不可行機(jī)組狀態(tài)組合的經(jīng)濟(jì)調(diào)度。另外，黃華軍等[15]針對求解混合整數(shù)線性規(guī)劃問題中如何判斷問題無解進(jìn)行了預(yù)處理和探測，并給出了具體可編程實(shí)現(xiàn)的算法。人員排班問題研究過程中，人們的注意力更多聚焦在建模和求解上。

在某機(jī)場人員自動排班系統(tǒng)的設(shè)計(jì)過程中發(fā)現(xiàn)，在服從某種約束規(guī)則組合下，用戶實(shí)際輸入的數(shù)據(jù)并不是都可以成功排班。數(shù)據(jù)的有效性、合理性會直接影響到算法結(jié)果輸出，本文研究內(nèi)容就是在該機(jī)場人員自動排班系統(tǒng)的基礎(chǔ)上，對數(shù)據(jù)的有效性及合理性進(jìn)行檢驗(yàn)，確保數(shù)據(jù)進(jìn)入模型之后，能夠有效輸出排班結(jié)果。

1 問題描述及其分析

人員自動排班系統(tǒng)主要用于解決人員排班問題，采用算法模型解決人員排班問題需要依賴較多的基礎(chǔ)數(shù)據(jù)。用戶輸入這些排班數(shù)據(jù)的時候，容易存在數(shù)據(jù)缺失、重復(fù)、格式錯誤、取值范圍過大、數(shù)據(jù)間存在內(nèi)在矛盾等情況，會導(dǎo)致模型構(gòu)建失敗或者求解失敗。自動排班是一個NP難問題，隨著班次數(shù)量、人員數(shù)量和約束條件的增加，理論上求解時間會呈指數(shù)增長。盡管該系統(tǒng)調(diào)用GUROBI求解器在運(yùn)算策略上有效節(jié)省求解時間，但是仍然難以達(dá)到秒級計(jì)算。算法模型求解時間大約占業(yè)務(wù)室排班總時間的90%以上，提前發(fā)現(xiàn)數(shù)據(jù)問題，能夠有效提高算法求解成功率及縮短求解時長。本研究旨在發(fā)現(xiàn)排班不成功的原因，針對性設(shè)計(jì)檢驗(yàn)規(guī)則，在數(shù)據(jù)進(jìn)入算法模型前將大部分無解數(shù)據(jù)過濾出來，避免這些數(shù)據(jù)進(jìn)入算法模型，從而提高自動排班系統(tǒng)的效率。

數(shù)據(jù)檢驗(yàn)問題劃分如圖1所示，由圖可知，第I類檢驗(yàn)主要針對表格內(nèi)容、重要字段空值、取值等內(nèi)容。第II類檢驗(yàn)更多是從無解的角度出發(fā)，主要檢驗(yàn)內(nèi)容是各個約束，以及約束之間的組合是否合理等。數(shù)據(jù)檢驗(yàn)主要對象包括班次信息、人員信息、預(yù)排班信息、約束規(guī)則、目標(biāo)函數(shù)和每天最晚最早班次信息等內(nèi)容。

圖1 數(shù)據(jù)檢驗(yàn)問題劃分

人員排班的基本約束如表1所示。其中，資質(zhì)約束和人數(shù)約束是默認(rèn)約束，其他約束可依據(jù)實(shí)際情況配置。

表1 常見基本約束

2 數(shù)據(jù)檢驗(yàn)規(guī)則

2.1 第I類檢驗(yàn)

第I類檢驗(yàn)需要檢驗(yàn)的數(shù)據(jù)表有6個，共有34個重要字段或者相關(guān)字段，班次信息表展示說明如表2所示。

表2 班次信息表重要字段

表3所示為班次信息的檢驗(yàn)內(nèi)容。

表3 班次信息檢驗(yàn)

經(jīng)過上述檢驗(yàn)之后，排班數(shù)據(jù)的大部分的重要字段在格式、取值和字段相互關(guān)聯(lián)等內(nèi)容均得到一定的保障，但是這種檢驗(yàn)只能確保不會導(dǎo)致程序報(bào)錯，并不能夠確保一定有排班結(jié)果輸出。

2.2 第II類檢驗(yàn)

該類檢驗(yàn)就是要在第I類檢驗(yàn)的基礎(chǔ)上，在數(shù)據(jù)進(jìn)入模型之前，能夠檢驗(yàn)出在這種約束組合下，是否會有可行解輸出。如圖2所示，假設(shè)灰色的圖案表示搜索空間，該空間主要由班次數(shù)量、人員數(shù)量等決定；黑色實(shí)線表示約束條件；深色區(qū)域表示所有約束條件的交集空間；空心圓點(diǎn)表示可行解；實(shí)心圓點(diǎn)表示非可行解；虛線為輔助曲線。

圖2 人員排班問題的幾種形態(tài)

在圖2（a）中，存在同時滿足4條約束的空間，并且該空間內(nèi)有可行解，算法在搜索過程中，一旦發(fā)現(xiàn)有滿足條件的可行解，則可以理解為有效輸出排班結(jié)果，否則理解為無法找到可行解；在圖2（b）中，存在交集，但是空間內(nèi)無可行解，算法需要全搜索才可以確定無解；在圖2（c）中，不存在同時滿足4條約束的空間，算法需要全搜索才可以確定無解。

在實(shí)際測試當(dāng)中，發(fā)現(xiàn)絕大部分是屬于圖2（a）和圖2（c）兩種情況，從約束組合是否沖突的角度劃分，圖2（a）和圖2（b）是同一種狀態(tài)，但是目前是沒有理由確定在約束組合無沖突狀態(tài)下，究竟是何種形態(tài)。對圖2（c）形態(tài)進(jìn)行分析，造成該形態(tài)的可以是約束和班次信息、人員信息間的沖突。

2.2.1 連續(xù)休假約束檢驗(yàn)

檢驗(yàn)描述：排班周期內(nèi)，任意員工連續(xù)休假天數(shù)超過n天。

檢驗(yàn)規(guī)則：若存在任意一位員工在連續(xù)n＋1天內(nèi)無任何一個班次可以做，即不能滿足連續(xù)休假約束。

檢驗(yàn)步驟：（1）按順序獲取一位員工信息；（2）根據(jù)資質(zhì)約束及班次安排情況，按日期順序獲取該員工的一個連續(xù)n＋1天可上班班次信息；（3）判斷該員工無可上班次的天數(shù)是否為n＋1，若是，則記錄檢驗(yàn)信息，并進(jìn)行下一步，否則直接進(jìn)行下一步；（4）判斷是否已遍歷每個連續(xù)n＋1天，若是，則進(jìn)行下一步，否則返回步驟（2）；（5）判斷是否已遍歷每個員工，是則結(jié)束檢驗(yàn)，否則返回步驟（1）。

2.2.2 周休息約束檢驗(yàn)

檢驗(yàn)描述：一周內(nèi)，任意員工不存在上班班次組合，滿足周休息約束。

檢驗(yàn)規(guī)則：找出每個員工在每周無可上班次的天數(shù)，若存在某個員工在某周內(nèi)無可上班的天數(shù)為大于周休息約束上限，即不可能同時滿足周休息約束。

檢驗(yàn)步驟：（1）按序號順序獲取一名員工的信息；（2）根據(jù)資質(zhì)約束及班次安排情況，按周次順序獲取該員工的一周可上班班次信息；（3）判斷該員工這周無可上班班次的天數(shù)是否大于周休息上限，是則記錄檢驗(yàn)信息并進(jìn)行下一步，否則直接進(jìn)行下一步；（4）判斷是否已遍歷每一周，是則進(jìn)行下一步，否則返回步驟（2）；（5）判斷是否已遍歷每個員工，是則修正排班周期休息約束范圍，否則返回步驟（1）。

2.2.3 排班周期休息約束檢驗(yàn)

檢驗(yàn)描述：周期內(nèi)，任意員工不存在上班班次組合，滿足排班周期休息約束。

檢驗(yàn)規(guī)則：找出每個員工在排班周期內(nèi)無可上班次的天數(shù)，若存在某個員工在排班周期內(nèi)無可上班的天數(shù)為大于排班周期休息約束上限，即不可能同時滿足周休息約束。

檢驗(yàn)步驟：（1）按順序獲取一名員工的信息；（2）根據(jù)資質(zhì)約束及班次安排情況，獲取該員工的當(dāng)前排班周期內(nèi)可上班班次信息；（3）判斷該員工在當(dāng)前排班周期內(nèi)無可上班班次的天數(shù)是否大于其對應(yīng)的排班周期休息上限，是則記錄檢驗(yàn)信息并進(jìn)行下一步，否則直接進(jìn)行下一步；（4）判斷是否已遍歷每個員工，是則修正排班周期休息約束范圍并結(jié)束本次檢驗(yàn)，否則返回步驟（1）。

2.2.4 周工時約束檢驗(yàn)

檢驗(yàn)描述：一周內(nèi)，任意員工不存在上班班次組合，滿足周工時約束。

檢驗(yàn)規(guī)則：根據(jù)各個崗位的班次安排情況，在滿足周休息約束的前提下，找出每個員工在每一周內(nèi)可能的最大工時及最少工時，作為對應(yīng)工時范圍的上下界，若某員工某周內(nèi)不存在一個這樣的范圍與周工時范圍存在交集，即為不可能同時滿足周休息約束和周工時約束。

檢驗(yàn)步驟：（1）按序號順序獲取一名員工的信息；（2）根據(jù)資質(zhì)約束及班次安排情況，按周次順序獲取該員工的一周可上班班次信息；（3）根據(jù)周休息約束計(jì)算一周內(nèi)工作不同天數(shù)下對應(yīng)的工時范圍；（4）遍歷步驟（3）所得到的每一個工時范圍，判斷是否不存在一個工時范圍與所給周工時約束范圍有交集，是則記錄檢驗(yàn)信息并進(jìn)行下一步，否則直接進(jìn)行下一步；（5）判斷是否已遍歷每一周，是則進(jìn)行下一步，否則返回步驟（2）；（6）判斷是否已遍歷每個員工，是則修正周工時約束范圍并結(jié)束本次檢驗(yàn)，否則返回步驟（1）。

2.2.5 排班周期工時約束檢驗(yàn)

檢驗(yàn)描述：在周期內(nèi)，任意員工不存在上班班次組合，滿足排班周期工時約束。

檢驗(yàn)規(guī)則：根據(jù)各個崗位的班次安排情況，在滿足排班周期休息約束的前提下，找出每個員工在排班周期內(nèi)工作不同天數(shù)下的最大工時及最少工時，作為對應(yīng)工時范圍的上下界，若某員工在排班周期內(nèi)不存在一個這樣的范圍與修正的排班周期工時范圍存在交集，即為不可能在滿足排班周期休息約束或者周工時約束的情況下滿足排班周期工時約束。

檢驗(yàn)步驟：（1）按序號順序獲取一名員工的信息；（2）根據(jù)資質(zhì)約束及班次安排情況，獲取該員工的當(dāng)前排班周期可上班班次信息；（3）排班周期休息約束下計(jì)算員工排班周期內(nèi)工作不同天數(shù)下對應(yīng)的工時范圍；（4）遍歷步驟（3）所得到的每一個工時范圍，判斷是否不存在一個工時范圍與該員工對應(yīng)的排班周期工時約束范圍有交集，是則記錄檢驗(yàn)信息并進(jìn)行下一步，否則直接進(jìn)行下一步；（5）判斷是否已遍歷每個員工，是則結(jié)束檢驗(yàn)，否則返回步驟（1）。

3 效果評估

3.1 人員排班數(shù)據(jù)集

人員排班數(shù)據(jù)集是該機(jī)場的實(shí)際數(shù)據(jù)，經(jīng)過整理將20個數(shù)據(jù)集用于測試本文提出的檢驗(yàn)規(guī)則，這20個數(shù)據(jù)集均為第I類檢驗(yàn)，但是排班算法無法找到可行解。數(shù)據(jù)集包括班次信息、人員信息以及約束信息，對數(shù)據(jù)集中包含的班次數(shù)、員工數(shù)、排班周期、約束要求進(jìn)行統(tǒng)計(jì)，如表4所示。

表4 測試數(shù)據(jù)的相關(guān)信息

數(shù)據(jù)中可以發(fā)現(xiàn)不同業(yè)務(wù)室的班次數(shù)、人員數(shù)、排班周期及約束要求一般都是不同的，而相同的業(yè)務(wù)室在不同排班周期上的情況也會有所不同。由于約束一般通過人工排班的經(jīng)驗(yàn)結(jié)合排班需求主觀設(shè)置的，而排班算法是嚴(yán)格按照約束規(guī)則求解，在這種情況下，排班算法也無法找到可行解。

3.2 數(shù)據(jù)檢驗(yàn)規(guī)則效果測評

由于一些檢驗(yàn)規(guī)則需要修正約束，因此檢驗(yàn)順序是需要考慮的，而且當(dāng)某個數(shù)據(jù)集在前一步檢驗(yàn)就有返回沖突數(shù)據(jù)信息，則不進(jìn)行下一步檢驗(yàn)，因此同一個數(shù)據(jù)集可能存在多次檢驗(yàn)修改的情況。20個無解的數(shù)據(jù)集，其檢驗(yàn)結(jié)果如表5所示。

表5 數(shù)據(jù)測試情況

對于每個數(shù)據(jù)集，每次檢驗(yàn)不通過時都進(jìn)行一次修正，直到通過所有檢驗(yàn)后，再進(jìn)行排班算法求解。

每次檢驗(yàn)的運(yùn)行時間在1 s以內(nèi)，通過對20個數(shù)據(jù)集檢驗(yàn)結(jié)果分析發(fā)現(xiàn)：（1）有15個數(shù)據(jù)集是由于排班周期工時約束與其他約束沖突導(dǎo)致；（2）有8個數(shù)據(jù)集未通過休息檢驗(yàn)，在修正數(shù)據(jù)時發(fā)現(xiàn)不通過的原因大部分是某些員工的資質(zhì)不包含任何班次所需的資質(zhì)；（3）大部分?jǐn)?shù)據(jù)集根據(jù)提供的檢驗(yàn)信息修正后，排班算法可以找到可行解，只有2個數(shù)據(jù)集，即使通過了第II類檢驗(yàn)，仍然無解，這是由于目前的檢驗(yàn)方法未覆蓋所有約束，以及可能存在的極端班次組合問題所造成的。

4 結(jié)束語

以往通過手工排查排班失敗的原因，往往需要大量時間與精力，特別是由于排班算法無解所引起的排班失敗現(xiàn)象，需要多次修正數(shù)據(jù)并進(jìn)行算法求解，才有可能找出其原因，嚴(yán)重影響了排班的效率。

本文通過設(shè)計(jì)檢驗(yàn)排班算法無解原因的方法，大大減少了人工排查的時間，在一定程度上提高了排班的效率，具有實(shí)際的應(yīng)用意義。所提出的檢驗(yàn)規(guī)則，雖然無法完全覆蓋所有排班算法無解的原因，但是可以檢驗(yàn)出常見的造成排班算法無解的原因。通過檢驗(yàn)所提供的信息，對數(shù)據(jù)進(jìn)行修正，一般可以得到排班結(jié)果，在自動排班過程中發(fā)揮了重要的作用。

本文還存在一些問題有待進(jìn)一步地研究，具體如下。

（1）考慮的約束條件有限。在設(shè)計(jì)檢驗(yàn)規(guī)則時，僅對排班約束的其中7種進(jìn)行設(shè)計(jì)，并未考慮其他約束的影響。

（2）存在一定局限性。對于所提出的檢驗(yàn)規(guī)則，盡管利用了部分?jǐn)?shù)據(jù)進(jìn)行了驗(yàn)證，但是這些規(guī)則仍有需要完善的地方，比如班次組合所得到的工時約束范圍是離散的，使得在一些極端的班次組合情況下即使通過了第II類檢驗(yàn)，仍然無法得到一個可行解。