某機場人員排班數(shù)據(jù)檢驗規(guī)則設計

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

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

0 引言

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

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

1 問題描述及其分析

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

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

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

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

表1 常見基本約束

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

2.1 第I類檢驗

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

表2 班次信息表重要字段

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

表3 班次信息檢驗

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

2.2 第II類檢驗

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

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

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

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

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

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

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

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

2.2.2 周休息約束檢驗

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

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

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

2.2.3 排班周期休息約束檢驗

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

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

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

2.2.4 周工時約束檢驗

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

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

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

2.2.5 排班周期工時約束檢驗

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

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

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

3 效果評估

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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