吳植英，汪春華，曹紫萱，杜晴晴，徐偉彬

（1.廣東工業(yè)大學(xué)機電工程學(xué)院，廣州 510006；2.廣東機場白云信息科技有限公司，廣州 510470）

0 引言

目前隨著國內(nèi)航空事業(yè)的不斷擴大，國內(nèi)各大航空公司的飛機數(shù)量也在不斷增加。如何合理地進行排班管理，有效利用人力資源，提高員工的勞動績效，降低整體的運營成本，提高生產(chǎn)力以及整個客艙清潔部門的投資回報率，是每一個機場發(fā)展到一定階段，管理者都要面臨的問題。

客艙清潔排班管理研究的目的是科學(xué)合理地安排人力資源，從而有效地分配任務(wù)，讓最適當(dāng)?shù)娜?，在最適當(dāng)?shù)臅r間，擔(dān)任最適合的任務(wù)，以達到人員與飛機的合理匹配。對管理者而言，其不僅要能有效地管理客艙清潔部門的人力資源，節(jié)約人力成本，而且還要進一步滿足客戶服務(wù)的要求，從而達到提升客艙清潔部門的運用管理水平，降低調(diào)度頻率以及客艙清潔部門的運營成本，提高整個航空公司的投資回報，增加企業(yè)收益。

排班問題是一個時間表問題，是運籌學(xué)領(lǐng)域中組合優(yōu)化問題之一，就是運用數(shù)學(xué)、計算機等領(lǐng)域的方法，在有限的時間內(nèi)去尋找一個最優(yōu)組合。國外研究人員對員工排班問題的研究起步較早，研究方向主要集中在員工排班問題的建模和算法實現(xiàn)兩個方面。

1976年，Baker K[1]提出了基于員工工作負荷拍板的數(shù)學(xué)模型，并將該模型應(yīng)用于多個工種類型的領(lǐng)域內(nèi)。1990年，Nagraj Balarishnan和Richard T Wong[2]運用網(wǎng)絡(luò)流技術(shù)，研究了基于工作負荷的員工排班問題，將排班模型的所有約束都集成到所建立的網(wǎng)絡(luò)中，而最佳排班方案就是所建立網(wǎng)絡(luò)中的一條路徑，最后的計算結(jié)果說明該方法非常適用于解決大型的排班問題。2001年，C K CHU[3]研究了機場地勤員工彈性排班問題，排班模型是整數(shù)規(guī)劃模型，目標(biāo)是在排班結(jié)果維持一定員工富余量的基礎(chǔ)上，最小化需要加班員工數(shù)量。2003年，Luca Di Gaspero等[4]提出了最少排班次數(shù)模型，其目標(biāo)在滿足員工負荷和實際需求負荷之差在一定可接受范圍內(nèi)的情況下，最小化員工排班次數(shù)和最小化員工使用數(shù)。2010年，Sin C Ho和Janny M Y Leung[5]研究了飛機配餐排班問題，由于受到航班時刻表和服務(wù)質(zhì)量的限制，此類問題是帶有時間窗和工作等級限制的排班問題，即每一架航班都需要在特定的時間內(nèi)和擁有該資質(zhì)的員工提供配餐，文中運用禁忌算法和模擬退火算法解決了該問題，并發(fā)現(xiàn)禁忌算法的效果更佳。2002年，孫宏和杜文[6]針對國內(nèi)航空公司運行與管理的特點，在單樞紐機場的情況下，提出了航班節(jié)的概念，建立了機組乘員排班模型，并設(shè)計了一種標(biāo)號算法進行求解，通過對一個算例的分析說明了該算法的應(yīng)用。2004年，劉德剛[7]研究了飛機客艙清潔人員的排班問題。具體分為兩個子問題：首先是通過合理的倒班方案，滿足高峰期對清潔隊人力資源的需求；其次是對清潔隊的作業(yè)流程進行優(yōu)化，使資源得到充分利用。2009年，許建國等[8]對機場安檢人員上班模式的問題進行了研究，建立了安檢人員日排班優(yōu)化模型和年度配置優(yōu)化模型，并用實例驗證此方法比原有上班模式更高效。2010年，程元軍和羅利[9]利用排隊論和整數(shù)規(guī)劃建立了銀行柜員彈性排班模型，并運用CPLEX求解實例，驗證了該方法的可行性。2018年，盧敏和王莉[10]研究了面向班型動態(tài)生成的地服人員排班算法，其核心思想是通過Block Gibbs抽樣迭代優(yōu)化班型內(nèi)人員構(gòu)成、班型內(nèi)航班集和班型生成，并在某機場值機人員的數(shù)據(jù)集中驗證此算法的可行性。試驗結(jié)果表明，在滿足員工層次資質(zhì)、員工白夜班和班型動態(tài)生成的約束下，算法能夠生成合理的班型。上述文獻雖然都依據(jù)其所研究的部門建立對應(yīng)的模型，但研究的排班單元只涉及到個人，并沒有考慮小組協(xié)作的情況，因此對本文所研究的客艙清潔室并不適用。

本文以某國際大型樞紐機場為例，通過前期的調(diào)研，先為客艙清潔室建立統(tǒng)一的排班標(biāo)準(zhǔn)以及排班約束，再建立出相應(yīng)的數(shù)學(xué)模型；設(shè)計整體的排班算法，在其中嵌入Gurobi的分支定界算法以求解模型；最后將結(jié)果與目前該室的手工排班表進行相應(yīng)指標(biāo)的比較，驗證排班算法的有效性及領(lǐng)先程度。

1 客艙清潔排班優(yōu)化模型的建立

1.1 問題分析

1.1.1 清潔部門概況

目前客艙清潔部門有4個分隊，每個分隊有14個小組，共有56個小組，每個小組中有5～6名員工，總數(shù)約為297人。每天清潔任務(wù)數(shù)200～500個，其中包括航前清潔，需求員工數(shù)1人；航后清潔，根據(jù)機型的不同，需求人數(shù)不同，一般為1～5組，清潔時間在40 min左右；過站清潔，根據(jù)機型的不同，需求人數(shù)也不同，一般為1～5組，清潔時間為15 min左右；排班周期以月為單位。具體情況如圖1所示。

圖1 客艙清潔部

1.1.2 排班問題分析

當(dāng)前排班是以小組為單位排班，這是基于每次的任務(wù)地點不同，需要通過運載車將員工送到指定地點，以小組為單位方便運載，同時由分隊長管理組長，組長管理員工，達到分層管理的效果。

以小組為排班單位，則會導(dǎo)致本來人力資源緊缺的客艙清潔部排班可用的人力資源進一步被壓縮，此時，清潔任務(wù)的精確分配就顯得尤為重要，因為精確的小組——任務(wù)對應(yīng)模式可以有效地提高人力資源的利用率。精確分配任務(wù)的優(yōu)化問題體現(xiàn)在如何對清潔排班的實際問題抽象出各種變量與約束，并以此建立出符合排班員期望的數(shù)學(xué)模型，該模型的優(yōu)化目標(biāo)主要體現(xiàn)在各小組之間的日工時、月工時、月夜班數(shù)、月休息天數(shù)、月上班時間等的均衡。排班單位特點對比如表1所示。

表1 排班單位對比

1.2 模型分析

對以組為單位的客艙部門排班模型，各組進行排班時要充分考慮到組內(nèi)員工執(zhí)行任務(wù)時所受到的各種限制，比如小組在同一時刻不能同時執(zhí)行兩個任務(wù)、小組在執(zhí)行連續(xù)兩個任務(wù)時需要滿足任務(wù)間隔時間約束等限制。與此同時，排班員希望排出來的結(jié)果能實現(xiàn)各員工的上班時間均衡、休假天數(shù)均衡等目標(biāo)。

在通過調(diào)研后，提取出了以下幾條基本約束和基本目標(biāo)。

（1）基本約束。任務(wù)需求組數(shù)滿足約束；連續(xù)任務(wù)間隔時間約束；班次時長的限制約束等。

（2）基本目標(biāo)。日工時均衡；休假天數(shù)均衡等。

1.3 模型建立

1.3.1 模型目標(biāo)函數(shù)

日上班工時均衡目標(biāo)函數(shù)為：

式中：wi為第i組員工的日上班工時。

周休息天數(shù)均衡目標(biāo)函數(shù)為：

式中：ri為第i組員工的周休息天數(shù)。

1.3.2 模型約束

任務(wù)需求滿足約束：

式中：xij為第i組員工是否領(lǐng)取了第j個任務(wù)，領(lǐng)取了則xij＝1，否則為0；qj為第j個的需求人數(shù)。

日工時上限約束：

式中：wi為第i組員工的日上班時長；Wub為日上班工時上限。

2 客艙清潔部排班模型數(shù)據(jù)的無解機制

2.1 基于約束松弛的求解法

2.1.1 約束松弛表的建立

通過調(diào)研白云機場的客艙清潔部，結(jié)合實際排班時需滿足的需求和歷史排班數(shù)據(jù)分析，得到的約束松弛如表2所示。

表2 約束松弛表

2.1.2 約束松弛的流程設(shè)計

約束松弛求解流程如圖2所示。

圖2 約束松弛求解流程

2.2 基于引入虛擬資源的求解法

引入虛擬資源求解流程如圖3所示。

圖3 引入虛擬資源求解流程

2.3 整合無解應(yīng)對機制后的算法流程

完整的排班求解流程如圖4所示。

圖4 完整的排班求解流程

3 排班結(jié)果分析

根據(jù)實際需要，算法模型中以小組為排班單位，共56個小組，在一個排班周期內(nèi)盡量完成約1 882個大任務(wù)，拆分成子任務(wù)，則將獲得約3 831個子任務(wù)，每個子任務(wù)都需要有1個小組去完成。進行排班時，在眾多約束作用下，以上述目標(biāo)函數(shù)如均衡排班、降低成本等為優(yōu)化方向，實現(xiàn)了客艙清潔部排班模型的優(yōu)化求解，最后得出的排班結(jié)果較精確解，以Excel的形式進行結(jié)果輸出，包括排班數(shù)據(jù)表、排班表、未分配任務(wù)表，結(jié)果證明此排班結(jié)果是比較合理的。

分別對手工排班表和本文涉及的自動排班算法設(shè)計出的自動排班表做數(shù)據(jù)處理及指標(biāo)統(tǒng)計，分別得到手工排班分析表及自動排班分析表，統(tǒng)計結(jié)果如表3～4所示。

表3 手工排班指標(biāo)統(tǒng)計表

表4 自動排班指標(biāo)統(tǒng)計表

綜合比較表3～4，得到如表5所示的結(jié)果分析比較表。如表所示，自動排班算法所排出來的排班表相比手工的排班表，有著以下幾個較為顯著的優(yōu)勢：

表5 結(jié)果分析比較表

（1）提高了約16.60%的平均任務(wù)覆蓋率，即相當(dāng)于機場客艙清潔室的服務(wù)質(zhì)量提高了約16.60%；

（2）人均上班時長均值提高12 min可以帶來將近1h的人均有效工時均值的提高，即在一定范圍內(nèi)，延長員工的上班時長可以帶來5倍等效時長的勞動力之多；

（3）有效工時占比提高了9.74%，意味著員工的工作效率提高了9.74%；

（4）上班時長極差均值減少了3.20 h，有效工時極差均值減少了2.11 h，意味著自動排班使得員工的上班時長相比以往更加公平。

4 結(jié)束語

本文經(jīng)過對客艙清潔部排班優(yōu)化算法的研究，利用IE運籌優(yōu)化的思想、軟約束逐步松弛的方法和引入虛擬資源求解機制，以應(yīng)對模型進行算法求解時無解的狀況；利用約束簡化和拆分?jǐn)?shù)據(jù)量，分層求解，重組合求解的思想，解決了因數(shù)據(jù)量龐大而導(dǎo)致求解時間過長的問題。通過對上述問題的逐一解決，針對客艙清潔部門排班問題建立了一套自動排班方案，該方案涉及算法同樣可推廣到國內(nèi)各大機場客艙清潔部門的排班，以及其他以任務(wù)驅(qū)動模式排班的行業(yè)。