自動(dòng)排班系統(tǒng)設(shè)計(jì)及階段性成效

程 宇，夏侯康，邵奇一，徐國(guó)寧，詹智勇

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

0 引言

隨著旅客對(duì)航空行業(yè)接受度的提高，客流量逐年上漲，國(guó)內(nèi)機(jī)場(chǎng)面臨新的競(jìng)爭(zhēng)壓力，急需符合行業(yè)戰(zhàn)略發(fā)展需要的信息化系統(tǒng)和應(yīng)用解決方案。國(guó)內(nèi)機(jī)場(chǎng)對(duì)于排班算法的研究尚處于起步階段，鮮有實(shí)際的應(yīng)用案例。機(jī)場(chǎng)地面服務(wù)人員排班運(yùn)籌優(yōu)化算法及系統(tǒng)作為全國(guó)較早研究機(jī)場(chǎng)排班算法的實(shí)際應(yīng)用，在中國(guó)民航業(yè)內(nèi)有開(kāi)創(chuàng)性的意義。

人員排班問(wèn)題可以追溯到20世紀(jì)50年代，護(hù)士和警務(wù)相關(guān)人員的排班在一開(kāi)始便是學(xué)者熱衷研究的對(duì)象[1-6]，在求解方法上也是多種多樣，最近這幾年也有學(xué)者采用變領(lǐng)域搜索算法[2]和帶權(quán)禁忌算法[4]進(jìn)行求解。Bergh V D[7]對(duì)護(hù)士排班問(wèn)題進(jìn)行綜述總結(jié)，并提出Nurse-Date，Nurse-Shift和Nurse-Task的劃分方式。后來(lái)，學(xué)者發(fā)現(xiàn)排班問(wèn)題在各行各業(yè)中都有著需求，而且，不同行業(yè)上班方式的差異化，導(dǎo)致以往研究的成果不能完全可以套用。在民航相關(guān)領(lǐng)域，有關(guān)注飛機(jī)排班問(wèn)題的[8-9]，有關(guān)注機(jī)組排班問(wèn)題的[10-13]，也有關(guān)注機(jī)場(chǎng)地面服務(wù)人員排班問(wèn)題的[14-17]。盧敏等[13，17]在文中提出層次資質(zhì)的機(jī)場(chǎng)外服人員排班問(wèn)題。這個(gè)問(wèn)題在理論背景和本文所提出的有不少相似之處，但是遠(yuǎn)不能滿足實(shí)際應(yīng)用。關(guān)注到地面人員排班問(wèn)題，更多的是從管理的角度去提出新的班次長(zhǎng)度，人員搭配等等，這也是對(duì)這類問(wèn)題研究的一個(gè)角度。關(guān)于約束滿足相關(guān)內(nèi)容Tsang E[21]給出了詳細(xì)的說(shuō)明。約束滿足問(wèn)題（CSPs）是人工智能和運(yùn)籌學(xué)的熱門主題，因?yàn)槠涔街械囊?guī)律，提供了共同基礎(chǔ)來(lái)分析、解決很多看似不相關(guān)的問(wèn)題。國(guó)內(nèi)的很多學(xué)者將不同領(lǐng)域的問(wèn)題轉(zhuǎn)化成為約束滿足問(wèn)題進(jìn)行處理[18-20]，李俊芳等[19]利用約束滿足技術(shù)對(duì)并行機(jī)Job-Shop調(diào)度問(wèn)題進(jìn)行研究，許紹云等[20]在流水車間訂單投放中應(yīng)用修復(fù)式約束滿足算法。經(jīng)過(guò)眾多學(xué)者的努力，在人員排班問(wèn)題上，取得不少成果，但是也衍生出更多新的問(wèn)題，為后續(xù)的研究提出更大的挑戰(zhàn)。

目前了解到，部分機(jī)場(chǎng)從國(guó)外引進(jìn)排班系統(tǒng)，部分嘗試組建科研團(tuán)隊(duì)自主開(kāi)發(fā)。香港怡中公司引進(jìn)Sabre的資源管理系統(tǒng)。南方航空公司經(jīng)過(guò)近5年持續(xù)開(kāi)發(fā)和優(yōu)化，目前已基本實(shí)現(xiàn)了“人員規(guī)劃—計(jì)劃排班—任務(wù)安排—統(tǒng)計(jì)決策”功能。東方航空公司于2012正式啟動(dòng)一期排班調(diào)度系統(tǒng)建設(shè)，于2014年基本完成開(kāi)發(fā)建設(shè)。2015年，東航開(kāi)始在國(guó)內(nèi)重點(diǎn)推廣應(yīng)用該系統(tǒng)。2016年，東航啟動(dòng)了二期建設(shè)（功能不僅是排班系統(tǒng)），2017年底完成。

1 問(wèn)題描述

自動(dòng)排班系統(tǒng)覆蓋4個(gè)二級(jí)子單位，影響員工總數(shù)達(dá)6 200余人。各二級(jí)單位包含多個(gè)業(yè)務(wù)室，這些業(yè)務(wù)室的工作內(nèi)容不同，在排班方式上也有較大的差異，在參考Bergh V D所提出的排班分類的基礎(chǔ)上，結(jié)合所有業(yè)務(wù)室的排班業(yè)務(wù)情況，經(jīng)過(guò)深入的調(diào)研、分析及總結(jié)，將問(wèn)題劃分為時(shí)刻型，任務(wù)型和固定型3種類型。

（1）時(shí)刻型：基于航班實(shí)際時(shí)刻的工作量分布，工作量與實(shí)際時(shí)刻的變化密切相關(guān)。

（2）任務(wù)型：基于航班任務(wù)計(jì)劃時(shí)間的工作量分布，工作量可根據(jù)航班計(jì)劃時(shí)間提前預(yù)期，與航班實(shí)際時(shí)刻的變化關(guān)聯(lián)較小。

（3）固定型：值守型崗位工作量分布，工作量和工作時(shí)間相對(duì)固定，與航班實(shí)際時(shí)刻變化無(wú)關(guān)。

人員排班問(wèn)題的歸類，利于整體求解流程的設(shè)計(jì)。實(shí)際上，根據(jù)不同業(yè)務(wù)室的工作特點(diǎn)，仍然有一些不能忽略的特殊性存在，也因?yàn)檫@種特殊性的存在，導(dǎo)致方案設(shè)計(jì)、解決問(wèn)題的時(shí)候更加復(fù)雜。

2 實(shí)現(xiàn)方案

2.1 自動(dòng)排班系統(tǒng)整體框架設(shè)計(jì)

用戶登錄終端（PC或APP）通過(guò)NGINX將用戶的請(qǐng)求轉(zhuǎn)發(fā)到應(yīng)用服務(wù)器，應(yīng)用服務(wù)器將請(qǐng)求放入RABBITMQ待處理排班隊(duì)列并調(diào)用算法微服務(wù)，求解器任務(wù)隊(duì)列通過(guò)求解器任務(wù)調(diào)度服務(wù)，調(diào)用求解器將可行解放入消息隊(duì)列，通過(guò)信息通知發(fā)送服務(wù)通知給用戶。自動(dòng)排班系統(tǒng)框架如圖1所示。

圖1 自動(dòng)排班系統(tǒng)整體框架

2.2 算法核心模塊的可配置化設(shè)計(jì)

模型算法模塊的處理流程如圖2所示。該過(guò)程劃分為數(shù)據(jù)交互層、數(shù)據(jù)處理層和模型算法層。其中數(shù)據(jù)交互層需要依據(jù)其他不同業(yè)務(wù)室排班需求，接收排班輸入數(shù)據(jù)，并且在完成相應(yīng)的排班會(huì)后，反饋結(jié)果。數(shù)據(jù)處理層主要功能有兩部分：第一是將接收到的排班輸入數(shù)據(jù)進(jìn)行檢驗(yàn)，確保數(shù)據(jù)輸入的合理性和可靠性，然后再將這些數(shù)據(jù)處理成模型算法輸入要求形式；第二是將模型算法輸出的結(jié)果進(jìn)行統(tǒng)計(jì)和格式處理，便于后續(xù)對(duì)數(shù)據(jù)展示。

圖2 模塊算法處理過(guò)程設(shè)計(jì)

結(jié)合到業(yè)務(wù)室的特殊性需求進(jìn)行分析之后，決定將沒(méi)有必要存在的剔除，剩下不能忽視的部分，則需要盡量滿足。因此在設(shè)計(jì)模型算法層的時(shí)候需要將這些特殊性的約束也考慮在內(nèi)，則要求模型更具包容性。傳統(tǒng)解決問(wèn)題的方式不足以滿足本項(xiàng)目開(kāi)發(fā)要求。針對(duì)本項(xiàng)目各個(gè)必要環(huán)節(jié)進(jìn)行可配置化設(shè)計(jì)，如圖3所示。

可配置設(shè)計(jì)中包含4個(gè)環(huán)節(jié)，分別是約束條件可配置、目標(biāo)函數(shù)可配置、模型參數(shù)可配置和求解算法可配置。

（1）約束條件可配置。模型中實(shí)現(xiàn)所有約束的構(gòu)建方法，業(yè)務(wù)室依據(jù)實(shí)際需要，選擇配置約束，人員排班問(wèn)題的規(guī)模由任務(wù)量、人數(shù)、排班周期等決定。通常來(lái)說(shuō)約束條件增加，都有可能縮小解空間，導(dǎo)致搜索時(shí)間增加。

（2）目標(biāo)函數(shù)可配置。目標(biāo)函數(shù)決定優(yōu)化方向，通常不會(huì)影響到解空間的大小。隨著目標(biāo)函數(shù)數(shù)量的增加，為了滿足多目標(biāo)的聯(lián)合要求，最終也會(huì)耗費(fèi)更多的時(shí)間。

圖3 重要環(huán)節(jié)可配置化設(shè)計(jì)

（3）模型參數(shù)可配置。模型參數(shù)的配置可以影響求解時(shí)間和解質(zhì)量。

（4）求解算法可配置。當(dāng)前階段主要應(yīng)用Gurobi自帶的算法，可以通過(guò)該參數(shù)設(shè)置啟發(fā)式算法和精確求解算法的側(cè)重程度。

2.3 核心模型設(shè)計(jì)

本節(jié)主要對(duì)核心模型及相關(guān)內(nèi)容的配置進(jìn)行介紹，包括目標(biāo)函數(shù)和約束條件兩部分的表達(dá)，這兩部分強(qiáng)調(diào)的是不同類型人員排班問(wèn)題共性的內(nèi)容。初步描述如下。

2.3.1 符號(hào)說(shuō)明

建模用到的符號(hào)說(shuō)明如下：x(e,m)表示員工e做任務(wù)m；y(l,e,s)=1時(shí)，表示員工e在第l天做班次s；q(e,m)=1時(shí)，表示員工e具備任務(wù)m的資質(zhì)；t(m,1)為任務(wù)m的開(kāi)始時(shí)間；t(m,2)為任務(wù)m的結(jié)束時(shí)間；d(m)為任務(wù)m需要的人數(shù)；max_num(e,m)為員工所做任務(wù)數(shù)的最大值；max_num(e,rest)為員工休假天數(shù)的最大值；sum(n)為所有員工所做夜班數(shù)總和；low_hour為每日工作時(shí)長(zhǎng)下限；up_hour為每日工作時(shí)長(zhǎng)上限；num(e,rest)為員工周期內(nèi)休假天數(shù)。

2.3.2 基本目標(biāo)函數(shù)

不設(shè)定基本目標(biāo)函數(shù)。

2.3.3 基本約束條件

（1）員工做某任務(wù)，必須具備該任務(wù)需求的資質(zhì)。若q(e,m)=0，有：

（2）分配的人數(shù)應(yīng)當(dāng)和任務(wù)需求的人數(shù)對(duì)應(yīng)：

（3）任何一位員工在同一時(shí)刻不能同時(shí)負(fù)責(zé)多個(gè)任務(wù)；若|t(m+j,2)-t(m,1)|＜t(m)+t(m+j)，有：

接下來(lái)在可配置目標(biāo)函數(shù)和可配置約束部分可以看到，針對(duì)不同的業(yè)務(wù)室，不但可以調(diào)整約束右端項(xiàng)取值，同時(shí)可以依據(jù)業(yè)務(wù)室的特點(diǎn)選擇合適的內(nèi)容。

2.3.4 可配置目標(biāo)函數(shù)

員工做任務(wù)的數(shù)量均衡：

員工所做的工時(shí)均衡：

員工所做的夜班數(shù)量和盡量少：

員工休假天數(shù)均衡：

2.3.5 可配置約束條件

員工每天上班的時(shí)長(zhǎng)：

員工每天選擇的班次類型（早班、中班和晚班）：

員工一段時(shí)間內(nèi)休假的天數(shù)：

2.3.6 可配置模型參數(shù)

（1）模型運(yùn)行時(shí)間：Gurobi.TimeLimit=Calcu_Time

（2）模型搜索節(jié)點(diǎn)數(shù)：Gurobi.NodeLimit=Search_Node

2.4 核心模型求解流程

自動(dòng)排班系統(tǒng)在求解的時(shí)候除了考慮構(gòu)建模型的可擴(kuò)展性外，在求解流程也需要有同樣的思考方式，在此不贅述。模型求解大致流程如圖4所示。

3 實(shí)施效果

3.1 案例展示1——國(guó)際值機(jī)室

3.1.1 結(jié)果展示

排班結(jié)果展示中，利用多種方式展示結(jié)果，一方面利于排班員查看，另一方面一線員工可以直接依據(jù)排班任務(wù)上下班。在甘特圖中展示已排任務(wù)和未排任務(wù)兩種類型，排班員可以對(duì)這些任務(wù)進(jìn)行操作，將未分配任務(wù)合理安排。如圖5所示，條框部分為已分配任務(wù)，深色的方塊表示任務(wù)實(shí)際作業(yè)時(shí)間，淺色表示任務(wù)間隔的空閑時(shí)間；褐色則表示未分配任務(wù)，在圖中可以看出未分配任務(wù)相對(duì)位置。

3.1.2 結(jié)果對(duì)比

（1）覆蓋率

圖4 模型求解流程

圖5 國(guó)際值機(jī)室員工任務(wù)展示

手工排班時(shí)，任務(wù)無(wú)法實(shí)現(xiàn)全覆蓋，但是在實(shí)際工作中，可以通過(guò)降低人力標(biāo)準(zhǔn)或者一人同時(shí)負(fù)責(zé)多個(gè)任務(wù)來(lái)解決。自動(dòng)排班時(shí)，不允許將多個(gè)任務(wù)同時(shí)安排給一人，需要嚴(yán)格按照服務(wù)標(biāo)準(zhǔn)進(jìn)行排班。但是自動(dòng)排班系統(tǒng)所得出來(lái)的結(jié)果，其覆蓋率仍然高于手工排班的覆蓋率。

表1 任務(wù)覆蓋對(duì)比

在自動(dòng)排班系統(tǒng)當(dāng)中，可以自動(dòng)統(tǒng)計(jì)出各個(gè)時(shí)段任務(wù)分布和未分配任務(wù)的覆蓋情況，如圖6所示，條框?yàn)槊總€(gè)時(shí)段任務(wù)量，曲線為通過(guò)自動(dòng)排班系統(tǒng)安排出來(lái)的已分配任務(wù)量。

（2）有效工時(shí)率

圖6 國(guó)際值機(jī)任務(wù)覆蓋信息

在手工排班當(dāng)中，排班結(jié)果在使用時(shí)會(huì)不斷調(diào)整，所以手工排班人均有效工時(shí)需要通過(guò)覆蓋任務(wù)的總時(shí)長(zhǎng)除以上班總?cè)藬?shù)。由于存在一個(gè)人同時(shí)擔(dān)任多個(gè)任務(wù)的情況，在計(jì)算人均有效工時(shí)有較大差異，這里不作統(tǒng)計(jì)。在自動(dòng)排班系統(tǒng)當(dāng)中，這些指標(biāo)都可以即時(shí)統(tǒng)計(jì)。國(guó)際值機(jī)有效工時(shí)率對(duì)比如表2所示。

表2 國(guó)際值機(jī)有效工時(shí)率對(duì)比

3.2 案例展示2——物流國(guó)內(nèi)出港操作室

3.2.1 結(jié)果展示

物流國(guó)內(nèi)出港操作崗位員工執(zhí)行任務(wù)展示如圖7所示。

圖7 物流國(guó)內(nèi)出港操作崗位員工執(zhí)行任務(wù)展示

3.2.2 結(jié)果對(duì)比

（1）覆蓋率

如圖8～9所示，手工排班結(jié)果不能覆蓋所有任務(wù)。進(jìn)一步和用戶確認(rèn)后，發(fā)現(xiàn)需要通過(guò)加班的方式來(lái)保證任務(wù)完成情況。自動(dòng)排班則依據(jù)任務(wù)分布情況，實(shí)現(xiàn)任務(wù)的全覆蓋。

圖8 手工排班任務(wù)覆蓋情況

（2）有效工時(shí)率

圖9 自動(dòng)排班任務(wù)覆蓋情況

物流國(guó)內(nèi)出港操作崗手工排班是將人員安排到相應(yīng)的班次上，未能實(shí)現(xiàn)將人員和任務(wù)匹配，故無(wú)人均有效工時(shí)相關(guān)統(tǒng)計(jì)。如果單單從排班結(jié)果的對(duì)比（不考慮臨時(shí)加班），手工排班的人均有效工時(shí)和人均上班工時(shí)均是低于自動(dòng)排班的結(jié)果。如果從任務(wù)全覆蓋的角度對(duì)比，兩種排班方式的人均有效時(shí)長(zhǎng)理論上是一致，但是人均上班時(shí)長(zhǎng)增加，導(dǎo)致有效工時(shí)率低于自動(dòng)排班。如表3所示。

表3 物流國(guó)內(nèi)出港操作崗有效工時(shí)率對(duì)比

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

本次研究通過(guò)對(duì)機(jī)場(chǎng)一線員工的崗位資質(zhì)和工作量進(jìn)行估算、設(shè)計(jì)、優(yōu)化和調(diào)整，在機(jī)場(chǎng)一線員工中高效地利用各種人、財(cái)、物資源，提高運(yùn)營(yíng)效率，降低運(yùn)營(yíng)成本，建立一個(gè)結(jié)果正確、響應(yīng)及時(shí)、可人工干預(yù)、整體聯(lián)動(dòng)，并根據(jù)航班信息、員工資質(zhì)、保障任務(wù)、約束條件，并通過(guò)混合算法運(yùn)籌優(yōu)化排班的機(jī)場(chǎng)地面服務(wù)人員排班運(yùn)籌優(yōu)化算法及系統(tǒng)。

（1）實(shí)踐成效

該系統(tǒng)已在機(jī)場(chǎng)的航服國(guó)際值機(jī)室、物流國(guó)內(nèi)出港操作、地勤客艙清潔等業(yè)務(wù)室使用，在任務(wù)的覆蓋率、人均有效工時(shí)率均有提升，并實(shí)現(xiàn)數(shù)據(jù)采集，有助于實(shí)現(xiàn)人力資源排班方面的精細(xì)化管理。

（2）市場(chǎng)獨(dú)有性

全球民航業(yè)的機(jī)場(chǎng)地面服務(wù)人員排班系統(tǒng)被國(guó)外商家壟斷，國(guó)內(nèi)只有少數(shù)航空公司嘗試上線地面服務(wù)人員智能化排班系統(tǒng)。在本產(chǎn)品上線之前，國(guó)內(nèi)機(jī)場(chǎng)目前并沒(méi)有真正投入使用地面服務(wù)人員智能排班系統(tǒng)，本次研究的產(chǎn)品在國(guó)內(nèi)市場(chǎng)上具備獨(dú)有性，擁有十分廣闊的市場(chǎng)前景。

（3）技術(shù)領(lǐng)先性

系統(tǒng)架構(gòu)通過(guò)多個(gè)微服務(wù)，響應(yīng)不同的請(qǐng)求，可實(shí)現(xiàn)多線程處理；模型求解過(guò)程可實(shí)現(xiàn)約束多級(jí)調(diào)整，并設(shè)計(jì)了無(wú)解機(jī)制，通過(guò)生成未分配任務(wù)，再通過(guò)手工調(diào)整的方式，提供系統(tǒng)實(shí)用性；可配置化設(shè)計(jì)，實(shí)現(xiàn)參數(shù)、約束、目標(biāo)等按需配置。