謝 維, 陳玉君, 朱文斌, 周 游

(華南理工大學(xué) 工商管理學(xué)院, 廣州 510641)

人員排班問題[1]是指在一定周期內(nèi)將工作安排給合適的員工完成, 安排的過程中通常涉及一系列國家法律法規(guī)以及公司規(guī)章制度, 證實是一個NP難問題[2].Ernst等[3]提出典型人員排班問題通常涉需求模型、休息日計劃、班次計劃、人員分配等幾大模塊.在地勤人員的排班問題中[4], 由于飛機起降的不確定性經(jīng)常造成延誤, 通常還涉及重新規(guī)劃(Stolletz[5]).本文描述了航空物流服務(wù)公司出港操作室的勞動力規(guī)劃過程,重點在員工每個月的行程安排, 在這個問題中, 班次不是固定的[6], 而是基于任務(wù)特點推導(dǎo)而成, 任務(wù)分配過程涉及員工班次和休息日安排, 并且考慮重新規(guī)劃成本.

目前人員排班不再限于關(guān)注硬性人員雇傭成本,還考慮未來發(fā)展, 寧愿付出相當(dāng)代價增加對人員公平[7]和個人偏好[8,9]方面的重視以提高士氣.本文在面向多技能員工排班[10]前提下, 考慮員工班在次間的任務(wù)數(shù)量、工作強度等因素的公平和均衡.

在勞動密集型行業(yè)或者用人高峰季節(jié)通常會出現(xiàn)人員緊缺現(xiàn)象, 因此任務(wù)覆蓋率是衡量排班質(zhì)量的一項重要標(biāo)準(zhǔn), 現(xiàn)有文獻多采用聘用外部雇員、臨時工、加班等方式來填補缺口.許丹等人[11]探索了人力資源不足情景下的護士排班加班策略, 并設(shè)計一種遺傳算法對模型進行求解.胡修武等人[12]考慮可加班的呼叫中心人員排班問題, 并采用鄰域搜索算法進行求解.Maenhout等人[13]采用聘請外部臨時工的方式解決人員需求缺口, 并基于分散搜索算法模型進行求解.Stolletz等人[14]通過動態(tài)加班補償機制和聘請外部醫(yī)生兩種方法結(jié)合來彌補需求覆蓋缺口, 并對使用分解啟發(fā)式算法、混合整數(shù)規(guī)劃和集合覆蓋模型求解的效果進行對比.

然而, 這種選擇應(yīng)用在航空業(yè)上不僅帶來了直接的高昂的成本, 由于航空公司任務(wù)時間與航班時刻掛鉤, 每日航班起降高峰出現(xiàn)用人高峰, 短期峰值后用人量減少, 閑置人員增加, 無疑也間接造成成本浪費.再者, 航空作為受天氣等不確定因素影響的行業(yè), 經(jīng)常會出現(xiàn)航班延誤、取消等不可控突發(fā)情況, 無法立刻從外部雇傭合格的臨時員工.為解決這個問題, 本文傾向于在前期排班時適當(dāng)舍棄部分任務(wù), 這部分任務(wù)可由現(xiàn)場調(diào)度人員根據(jù)實際情況調(diào)度員工完成.若僅以總體覆蓋率最大化為目標(biāo), 可能造成每天的覆蓋率不均衡的情況, 導(dǎo)致有些天無法覆蓋的任務(wù)過多, 無法使用現(xiàn)場調(diào)度進行彌補.因此在模型中, 盡可能保障無法覆蓋的任務(wù)均攤至能被當(dāng)天值班人員兼顧, 如通過加快速度縮短任務(wù)完成時間等方法.從管理的角度出發(fā), 人員排班要求做到均衡任務(wù)覆蓋, 同時根據(jù)最終的解決方案的無法覆蓋任務(wù)數(shù)量以及在各時間段的分布情況,可供分析缺人性質(zhì)是整體人員不足還是高峰用人呈現(xiàn)臨時性缺人, 協(xié)助管理層對人員組成進行決策和調(diào)整.

本文提出了一種基于變鄰域搜索算法的模型求解策略, 它能夠很好地跳出局部最優(yōu), 并具有良好的時效性.

本文的主要貢獻如下: (1)基于任務(wù)特點生成非固定時段的多崗位均衡任務(wù)班次; (2)建立均衡任務(wù)覆蓋率的混合整數(shù)規(guī)劃模型; (3)對航空物流服務(wù)公司出港操作室的真實數(shù)據(jù)進行測試, 證明方法在管理上行之有效.

1 問題描述

航空物流服務(wù)公司出港操作室的主要任務(wù)為將客戶的貨物從接收到送上貨機的整個過程涉及的工作和程序, 共涉及6個崗位: 接單崗、操作崗、復(fù)核崗、過磅崗、拉貨崗、夜班崗.

人員排班分為兩個階段: 第1階段為班次生成[15],即指將根據(jù)相關(guān)法律法規(guī)將任務(wù)打包成班次以覆蓋總?cè)蝿?wù)計劃中的所有任務(wù); 第2階段班次分配[16], 即將生成的班次按照一定的規(guī)則分配給員工.

本文考慮以一個月為周期的排班問題, 這個問題包括將擁有一種或多種崗位資質(zhì)的員工, 安排到排班周期內(nèi)的班次中.由任務(wù)崗位性質(zhì)可知, 不同任務(wù)間持續(xù)時間相差較大, 為均衡班次的任務(wù)數(shù)量和員工工作強度, 引入一個新的概念:

定義1.長任務(wù).任務(wù)持續(xù)時間超過1 h的任務(wù)稱為長任務(wù), 其余為普通任務(wù).

任務(wù)持續(xù)時長影響員工工作滿意度, 同崗位班次中長任務(wù)過少導(dǎo)致頻繁切換任務(wù), 且任務(wù)總數(shù)量上多于其他班次會造成員工內(nèi)心的不公平感, 因此均衡班次長任務(wù)數(shù)量是公平的重要體現(xiàn).本文希望做到在遵循所有合同制約的前提下, 滿足員工之間的公平性原則, 對班次的任務(wù)個數(shù)、長任務(wù)個數(shù)等盡可能平均.同時在排班周期內(nèi)按天均衡任務(wù)覆蓋率, 即在人員不足的前提下, 無法覆蓋的任務(wù)在排班周期內(nèi)呈現(xiàn)日均衡,以確?？梢酝ㄟ^現(xiàn)場調(diào)度解決高峰時期人員稀缺問題.

2 模型建立

模型建立分為兩個階段, 分別為班次生成和班次分配階段.本文用大寫字母表示輸入的數(shù)據(jù)、已知參數(shù)和可以靜態(tài)計算的量, 小寫字母表示決策變量、未知參數(shù)與下標(biāo), 用上標(biāo)表示為標(biāo)簽而不是指數(shù)運算,|·|表示集合元素個數(shù).

2.1 班次生成

馮霞等人[17,18]研究了層次資質(zhì)下的班次生成問題,本文結(jié)合航空物流服務(wù)公司出港操作室的實際情況,提出多種崗位下的班次生成模型[19].整數(shù)規(guī)劃模型符號如表1、表2所示.

表1 班次生成集合符號

表2 班次生成參數(shù)符號

中心決策變量為是否將任務(wù)t∈T分配到班次s∈S, 即:

其他決策變量有:

定義“”表示兩個集合的相對差集, 則班次生成模型如下:

其中, 班次生成目標(biāo)函數(shù)(1)表示最小化班次時間, 約束(2)表示每個任務(wù)必須分配到一個班次, 約束(3)表示表示同一班次內(nèi)任務(wù)間隔時間不小于Blb, 約束(4)和約束(5)表示一個班次只能分配一種崗位的任務(wù), 約束(6)和約束(7)限制班次時長, 其中表示夜班班次的集合.

2.2 班次分配

整數(shù)規(guī)劃模型的符號表示如表3、表4所示, 中心決策變量為是否將第d∈D天的班次s∈S分配給員工e∈E, 即:

表3 班次分配集合符號

表4 班次分配參數(shù)符號

其他決策變量為:

班次分配整數(shù)規(guī)劃模型的目標(biāo)函數(shù)(8)是最小化未完成任務(wù)的總工時, 保障最大任務(wù)覆蓋率.具體模型如下:

約束(9)表示如果班次s被分配, 則有一名員工e分配到班次s, 否則這個班次未被分配.約束(10)表示每個員工每天最多上一個班次, 否則就休息.約束(11)表示每個員工每月工時最少Hlb小時, 最多Hub小時.Cij為常數(shù), 是根據(jù)班次信息提前計算好的, 約束(12)考慮前一個班次對后面班次的影響, 例如前后班次上班間隔時間要不小于規(guī)定時間等, 確保分配的班次能夠由同一個員工完成.約束(13)和約束(14)表示員工每周至少休RWlb息天, 至多休RWub天.約束(15)和約束(16)表示員工每個月至少休息RMlb天, 至多休息RMub天.表示夜班班次的集合, 則約束(17)表示在連續(xù)夜班之后,強制休息2天.

3 基于管理角度的均衡性整合

從管理的角度出發(fā), 本文考慮的均衡性主要包括兩個方面: 一是基于班次之間工作量的均衡性, 即使得每個班次間總?cè)蝿?wù)數(shù)量以及長任務(wù)數(shù)量盡可能平均,保障分配到不同班次的員工所做任務(wù)數(shù)量均衡; 二是基于每日完成任務(wù)覆蓋率的均衡, 保障員工間工作強度的均衡.

本文將采用在原優(yōu)化目標(biāo)中加上一定權(quán)重下的均衡優(yōu)化目標(biāo)或者在原約束條件中加上均衡約束的方法來限制優(yōu)化目標(biāo).

3.1 基于班次間的均衡

根據(jù)對航空物流服務(wù)公司出港操作室的訪談, 得出該部門班次間的均衡主要體現(xiàn)在班次間總?cè)蝿?wù)和長任務(wù)數(shù)量的均衡.假設(shè) α ,β分別總?cè)蝿?wù)數(shù)和長任務(wù)數(shù)的公平項的權(quán)重, 則納入到班次生成模型中有:

基于班次間均衡的目標(biāo)函數(shù)式(18)是小化班次間總?cè)蝿?wù)和長任務(wù)數(shù)量差異.約束(19)表示班次s最少nlb個任務(wù), 最多nub個任務(wù).約束(20)表示班次s最少nLlb個長任務(wù), 最多nLub個長任務(wù).其中,nlb、nub、nLlb、nLlb均為未知參數(shù).

3.2 均衡任務(wù)覆蓋率

假設(shè)Mpre為預(yù)先請假的不可用人力,Mava為排班周期內(nèi)的可用人力,為第d天的可用人力, |S|為排 ??班周期內(nèi)?總的班次數(shù)量,為第d天的班次數(shù)量.其中|S|和在班次生成階段可以得出, 排班周期內(nèi)的可用人力和每天可用人力的計算公式分別如下:

4 模型求解

在班次生成階段, 先用貪婪算法構(gòu)造初始解, 然后選擇變鄰域搜索算法對班次生成方案進行調(diào)整, 采用任務(wù)交換、任務(wù)插入、任務(wù)交叉3種鄰域結(jié)構(gòu)分別如圖1、圖2、圖3所示.班次分配階段選用符合第2.2節(jié)分配約束和第3節(jié)均衡策略進行分配.

圖1 任務(wù)交換過程

圖2 任務(wù)插入過程

圖3 任務(wù)交叉過程

4.1 班次生成

4.1.1 初始解生成

班次生成的初始解步驟如下:

Step 1.將集合T中的任務(wù)按照任務(wù)開始時間的先后順序排列.

Step 2.從第1個任務(wù)開始遍歷, 將任務(wù)t1加入到班次s1中, 且將任務(wù)t1的崗位q加入到該班次崗位.

Step 3.尋找滿足約束(3)-約束(7)的任務(wù)加入到班次s1中, 直到不能再加入任務(wù), 則生成一個完整班次.

Step 4.遍歷未分配班次的任務(wù), 取第1個作為新班次的第1個任務(wù), 重復(fù)Step 2-Step 3.當(dāng)滿足約束(2)時, 得到所有班次初始解, 否則轉(zhuǎn)到Step 4.

4.1.2 鄰域結(jié)構(gòu)設(shè)置

鄰域結(jié)構(gòu)的設(shè)計是變鄰域搜索算法的核心, 在保障解的可行性前提下進行領(lǐng)域動作, 生成可行的候選解.本節(jié)設(shè)計了3種鄰域結(jié)構(gòu)來生成候選解: 任務(wù)交換、任務(wù)插入、任務(wù)交叉, 分別設(shè)為N0、N1、N2.

(1)任務(wù)交換方法

從候選解中隨機選擇兩個班次s1和s2, 交換兩個班次中的任務(wù), 生成新的班次和.判斷和是否滿足班次生成約束條件, 如果滿足則進行交換, 如圖1所示.

(2)任務(wù)插入方法

從候選解中隨機選擇兩個班次s1和s2, 將班次s1的任務(wù)移除插入到班次s2中, 生成新的班次和.判斷和是否滿足班次生成約束條件, 如果滿足則進行交換, 如圖2所示.

(3)任務(wù)交叉方法

從候選解中隨機選擇兩個班次s1和s2, 在兩個班次中分別選擇一個任務(wù)節(jié)點進行交叉, 互換后面的所有任務(wù), 生成新的班次和.判斷和是否滿足班次生成約束條件, 如果滿足則進行交叉, 如圖3所示.

4.1.3 基于變鄰域搜索算法的模型求解

變鄰域搜索算法利用4.1.2節(jié)的3種鄰域結(jié)構(gòu)進行搜索, 整個算法過程只接受可行解.每進行一次鄰域動作就對新生成的解進行評估, 評估函數(shù)為3.1節(jié)的目標(biāo)函數(shù)g(s), 如果對比起當(dāng)前解s, 新的解有g(shù)(s), 則更新當(dāng)前解為s′, 當(dāng)找不出比當(dāng)前解更優(yōu)解時,跳到下一個鄰域進行搜索.具體算法步驟如算法1所示.

算法1.基于變鄰域搜索的班次生成算法images/BZ_298_569_638_598_663.png images/BZ_298_749_630_999_663.png images/BZ_298_251_680_301_709.png輸入: 初始班次生成方案; 鄰域結(jié)構(gòu); 最大迭代次數(shù) images/BZ_298_569_738_586_759.png輸出: 優(yōu)化班次生成方案images/BZ_298_398_793_478_818.pngimages/BZ_298_614_793_643_818.png(1) 令當(dāng)前解; //初始解 由4.1.1節(jié)貪婪算法生成 images/BZ_298_265_838_561_867.png(2); //設(shè)置迭代次數(shù), 達到最大迭代次數(shù)終止算法images/BZ_298_282_942_573_976.png(3) ;images/BZ_298_298_1000_815_1041.png images/BZ_298_984_1016_1001_1037.pngiimages/BZ_298_485_1056_505_1089.png(4) ; //在當(dāng)前解 的第 個鄰域結(jié)構(gòu)中隨機產(chǎn)生解()images/BZ_298_315_1123_611_1173.pngimages/BZ_298_680_1127_701_1161.png(5) ; //以 為初始解進行局部搜索, 獲得局部最優(yōu)解()images/BZ_298_315_1249_586_1299.png(6) //如果局部最優(yōu)解優(yōu)于當(dāng)前解, 則更新當(dāng)前解images/BZ_298_332_1362_411_1399.png(7) ;images/BZ_298_332_1424_432_1453.png(8) ; images/BZ_298_315_1477_444_1506.png(9)images/BZ_298_348_1530_448_1559.png(10) ; images/BZ_298_315_1583_394_1612.png(11) ; images/BZ_298_298_1636_394_1665.png(12) ; images/BZ_298_282_1689_378_1718.png(13); images/BZ_298_282_1746_386_1771.pngimages/BZ_298_755_1750_772_1771.png(14) ; //返回優(yōu)化班次生成方案

4.2 班次分配

為方便求解, 引入以下定義:

定義2.候選人.如果員工e擁有服務(wù)班次s的資質(zhì),則稱員工e為班次s的候選人.

定義3.不可指派班次.由于候選人不足或控制班次數(shù)等原因造成不能指派給員工完成的班次.

Step 1.將集合S中的班次按照候選人的數(shù)量從少到多排列.

Step 2.取第一個班次s1, 遍歷該班次的所有候選人, 刪除不符合約束(9)-約束(17)的候選人.

Step 3.在Step 2后, 如果剩余的候選人不為空, 則選取當(dāng)前月工時最短的候選人e.否則將班次加入到不可指派班次中.

Step 4.判斷是否滿足Mava-|S|＜0, 如果滿足, 則分配班次s給Step 3中選取的候選人e, 并更新其月工時、休息日等相關(guān)狀態(tài).否則將班次加入到不可指派班次中.

Step 5.重復(fù)Step 2-Step 4, 直到所有班次分配完畢, 算法結(jié)束.

5 數(shù)值實驗

5.1 實驗數(shù)據(jù)

數(shù)值實驗選取航空物流服務(wù)公司出港操作室2019年11月份數(shù)據(jù), 包括64名員工、6種崗位.總?cè)蝿?wù)個數(shù)為7893個, 操作崗任務(wù)為7161個.表5顯示了具體任務(wù)信息, 可以看出除了操作崗其余各崗位時長均超過7小時, 即一個任務(wù)為一個班次, 而操作崗時長較短, 一個班次往往包含多個任務(wù), 因此第4.1節(jié)的任務(wù)移動操作主要針對操作崗.

表5 任務(wù)信息表

5.2 實驗設(shè)置

本文采用Java實現(xiàn)第4節(jié)算法, 實驗使用的硬件環(huán)境為Intel(R) Core(TM) i7-8550U CPU @1.80 GHz主頻, 內(nèi)存為8 GB的計算機.班次生成算法設(shè)置最大迭代次數(shù),, 休息天數(shù)參數(shù)的時間單位時間為天, 其余時間單位為小時, 在計算程序中轉(zhuǎn)化為統(tǒng)一單位計算, 具體參數(shù)設(shè)置如表6所示, 參數(shù)含義參考表2和表4.

表6 實驗參數(shù)設(shè)置

5.3 實驗結(jié)果

實驗共生成班次1524個, 班次生成方案的信息包括班次日期、班次編號、班次起始時間、班次崗位資質(zhì)、以及班次保障任務(wù)集等, 具體實驗結(jié)果如表7所示.

表7 班次生成實驗結(jié)果

其中, 生成的操作崗班次由多個保障任務(wù)構(gòu)成, 由第3節(jié)可知為了保障同崗位資質(zhì)的班次間的工作強度一致, 盡可能保障同類班次間的總?cè)蝿?wù)數(shù)以及長任務(wù)數(shù)的數(shù)量平均.圖4和圖5分別表示在班次生成階段2019年11月操作崗班次的中總?cè)蝿?wù)數(shù)量和長任務(wù)數(shù)量的個數(shù).

圖4 操作崗班次總?cè)蝿?wù)個數(shù)分布

圖5 操作崗班次長任務(wù)個數(shù)分布

由上述實驗數(shù)據(jù)可知, 一個操作崗班次總?cè)蝿?wù)大多集中在9個左右, 其余都在與平均總?cè)蝿?wù)個數(shù)相差1個任務(wù)幅度范圍內(nèi), 每個班次長任務(wù)個數(shù)集中在1個到2個, 整體上呈現(xiàn)均衡.根據(jù)航班數(shù)據(jù)顯示, 航班存在比較明顯的起降高峰, 在航班起降低峰期班次內(nèi)任務(wù)數(shù)量較少, 起降高峰班次內(nèi)任務(wù)數(shù)量較多是不可避免的, 因而總體的班次生成方案設(shè)置合理, 在工作量以及工作強度上呈現(xiàn)均衡性.

在班次分配階段, 由Mava-|S|得出的理論上不可完成班次為88個.未對均衡任務(wù)覆蓋率限制的情況下,即4.2節(jié)中不進行Step 4的判斷, 得出的2019年11月的月度班次分配情況如圖6所示, 未分配的班次為88個, 達到理論最優(yōu)值, 集中在月末2天.均衡任務(wù)覆蓋限制后, 2019年11月的月度分配情況如圖7所示,未分配班次數(shù)為90個, 僅比最優(yōu)值多2個, 但在月度上呈現(xiàn)均衡, 在管理的角度更加可取.

圖6 均衡前月度班次分配情況 (2019年11月)

圖7 均衡后月度班次分配情況 (2019年11月)

6 結(jié)論

本文在結(jié)合國內(nèi)外機場地勤人員排班研究的基礎(chǔ)上, 調(diào)研航空物流服務(wù)公司出港操作室的具體業(yè)務(wù)場景, 建立了一套均衡任務(wù)覆蓋率模型.數(shù)值實驗表明這個模型對航空業(yè)或受季節(jié)、突發(fā)事件影響大而導(dǎo)致的缺人的情況下更有效.均衡任務(wù)覆蓋模型可以很好應(yīng)對不確定性, 給現(xiàn)場調(diào)度人員最大的可安排空間, 同時將公平性融入到排班計劃中, 提高員工的滿意程度和人員保留率, 間接降低人員招聘和培訓(xùn)等運營過程成本, 在管理上行之有效.

本文雖對現(xiàn)場調(diào)度因素做了一定的考量, 但目前算法仍主要關(guān)注班次生成和班次分配階段, 在今后的研究中可以對現(xiàn)場調(diào)度涉及因素更細化地考慮進模型中, 形成一個更科學(xué)、更合理的智能排班系統(tǒng).