某機(jī)場(chǎng)人員排班數(shù)據(jù)檢驗(yàn)規(guī)則設(shè)計(jì)

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

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

0 引言

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

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

1 問(wèn)題描述及其分析

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

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

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

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

表1 常見(jiàn)基本約束

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

2.1 第I類檢驗(yàn)

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

表2 班次信息表重要字段

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

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

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

2.2 第II類檢驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 效果評(píng)估

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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