考慮編制受限的均衡任務覆蓋人員排班模型①

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

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

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

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

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

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

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

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

1 問題描述

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

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

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

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

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

2 模型建立

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

2.1 班次生成

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

表1 班次生成集合符號

表2 班次生成參數符號

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

其他決策變量有:

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

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

2.2 班次分配

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

表3 班次分配集合符號

表4 班次分配參數符號

其他決策變量為:

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

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

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

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

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

3.1 基于班次間的均衡

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

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

3.2 均衡任務覆蓋率

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

4 模型求解

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

圖1 任務交換過程

圖2 任務插入過程

圖3 任務交叉過程

4.1 班次生成

4.1.1 初始解生成

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

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

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

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

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

4.1.2 鄰域結構設置

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

(1)任務交換方法

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

(2)任務插入方法

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

(3)任務交叉方法

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

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

變鄰域搜索算法利用4.1.2節(jié)的3種鄰域結構進行搜索, 整個算法過程只接受可行解.每進行一次鄰域動作就對新生成的解進行評估, 評估函數為3.1節(jié)的目標函數g(s), 如果對比起當前解s, 新的解有g(s), 則更新當前解為s′, 當找不出比當前解更優(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輸入: 初始班次生成方案; 鄰域結構; 最大迭代次數 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) 令當前解; //初始解 由4.1.1節(jié)貪婪算法生成 images/BZ_298_265_838_561_867.png(2); //設置迭代次數, 達到最大迭代次數終止算法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) ; //在當前解 的第 個鄰域結構中隨機產生解()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)于當前解, 則更新當前解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擁有服務班次s的資質,則稱員工e為班次s的候選人.

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

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

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

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

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

Step 5.重復Step 2-Step 4, 直到所有班次分配完畢, 算法結束.

5 數值實驗

5.1 實驗數據

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

表5 任務信息表

5.2 實驗設置

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

表6 實驗參數設置

5.3 實驗結果

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

表7 班次生成實驗結果

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

圖4 操作崗班次總任務個數分布

圖5 操作崗班次長任務個數分布

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

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

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

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

6 結論

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

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