考虑编制受限的均衡任务覆盖人员排班模型①

谢 维, 陈玉君, 朱文斌, 周 游

(华南理工大学 工商管理学院, 广州 510641)

人员排班问题[1]是指在一定周期内将工作安排给合适的员工完成, 安排的过程中通常涉及一系列国家法律法规以及公司规章制度, 证实是一个NP难问题[2].Ernst等[3]提出典型人员排班问题通常涉需求模型、休息日计划、班次计划、人员分配等几大模块.在地勤人员的排班问题中[4], 由于飞机起降的不确定性经常造成延误, 通常还涉及重新规划(Stolletz[5]).本文描述了航空物流服务公司出港操作室的劳动力规划过程,重点在员工每个月的行程安排, 在这个问题中, 班次不是固定的[6], 而是基于任务特点推导而成, 任务分配过程涉及员工班次和休息日安排, 并且考虑重新规划成本.

目前人员排班不再限于关注硬性人员雇佣成本,还考虑未来发展, 宁愿付出相当代价增加对人员公平[7]和个人偏好[8,9]方面的重视以提高士气.本文在面向多技能员工排班[10]前提下, 考虑员工班在次间的任务数量、工作强度等因素的公平和均衡.

在劳动密集型行业或者用人高峰季节通常会出现人员紧缺现象, 因此任务覆盖率是衡量排班质量的一项重要标准, 现有文献多采用聘用外部雇员、临时工、加班等方式来填补缺口.许丹等人[11]探索了人力资源不足情景下的护士排班加班策略, 并设计一种遗传算法对模型进行求解.胡修武等人[12]考虑可加班的呼叫中心人员排班问题, 并采用邻域搜索算法进行求解.Maenhout等人[13]采用聘请外部临时工的方式解决人员需求缺口, 并基于分散搜索算法模型进行求解.Stolletz等人[14]通过动态加班补偿机制和聘请外部医生两种方法结合来弥补需求覆盖缺口, 并对使用分解启发式算法、混合整数规划和集合覆盖模型求解的效果进行对比.

然而, 这种选择应用在航空业上不仅带来了直接的高昂的成本, 由于航空公司任务时间与航班时刻挂钩, 每日航班起降高峰出现用人高峰, 短期峰值后用人量减少, 闲置人员增加, 无疑也间接造成成本浪费.再者, 航空作为受天气等不确定因素影响的行业, 经常会出现航班延误、取消等不可控突发情况, 无法立刻从外部雇佣合格的临时员工.为解决这个问题, 本文倾向于在前期排班时适当舍弃部分任务, 这部分任务可由现场调度人员根据实际情况调度员工完成.若仅以总体覆盖率最大化为目标, 可能造成每天的覆盖率不均衡的情况, 导致有些天无法覆盖的任务过多, 无法使用现场调度进行弥补.因此在模型中, 尽可能保障无法覆盖的任务均摊至能被当天值班人员兼顾, 如通过加快速度缩短任务完成时间等方法.从管理的角度出发, 人员排班要求做到均衡任务覆盖, 同时根据最终的解决方案的无法覆盖任务数量以及在各时间段的分布情况,可供分析缺人性质是整体人员不足还是高峰用人呈现临时性缺人, 协助管理层对人员组成进行决策和调整.

本文提出了一种基于变邻域搜索算法的模型求解策略, 它能够很好地跳出局部最优, 并具有良好的时效性.

本文的主要贡献如下: (1)基于任务特点生成非固定时段的多岗位均衡任务班次; (2)建立均衡任务覆盖率的混合整数规划模型; (3)对航空物流服务公司出港操作室的真实数据进行测试, 证明方法在管理上行之有效.

1 问题描述

航空物流服务公司出港操作室的主要任务为将客户的货物从接收到送上货机的整个过程涉及的工作和程序, 共涉及6个岗位: 接单岗、操作岗、复核岗、过磅岗、拉货岗、夜班岗.

人员排班分为两个阶段: 第1阶段为班次生成[15],即指将根据相关法律法规将任务打包成班次以覆盖总任务计划中的所有任务; 第2阶段班次分配[16], 即将生成的班次按照一定的规则分配给员工.

本文考虑以一个月为周期的排班问题, 这个问题包括将拥有一种或多种岗位资质的员工, 安排到排班周期内的班次中.由任务岗位性质可知, 不同任务间持续时间相差较大, 为均衡班次的任务数量和员工工作强度, 引入一个新的概念:

定义1.长任务.任务持续时间超过1 h的任务称为长任务, 其余为普通任务.

任务持续时长影响员工工作满意度, 同岗位班次中长任务过少导致频繁切换任务, 且任务总数量上多于其他班次会造成员工内心的不公平感, 因此均衡班次长任务数量是公平的重要体现.本文希望做到在遵循所有合同制约的前提下, 满足员工之间的公平性原则, 对班次的任务个数、长任务个数等尽可能平均.同时在排班周期内按天均衡任务覆盖率, 即在人员不足的前提下, 无法覆盖的任务在排班周期内呈现日均衡,以确保可以通过现场调度解决高峰时期人员稀缺问题.

2 模型建立

模型建立分为两个阶段, 分别为班次生成和班次分配阶段.本文用大写字母表示输入的数据、已知参数和可以静态计算的量, 小写字母表示决策变量、未知参数与下标, 用上标表示为标签而不是指数运算,|·|表示集合元素个数.

2.1 班次生成

冯霞等人[17,18]研究了层次资质下的班次生成问题,本文结合航空物流服务公司出港操作室的实际情况,提出多种岗位下的班次生成模型[19].整数规划模型符号如表1、表2所示.

表1 班次生成集合符号

表2 班次生成参数符号

中心决策变量为是否将任务t∈T分配到班次s∈S, 即:

其他决策变量有:

定义“”表示两个集合的相对差集, 则班次生成模型如下:

其中, 班次生成目标函数(1)表示最小化班次时间, 约束(2)表示每个任务必须分配到一个班次, 约束(3)表示表示同一班次内任务间隔时间不小于Blb, 约束(4)和约束(5)表示一个班次只能分配一种岗位的任务, 约束(6)和约束(7)限制班次时长, 其中表示夜班班次的集合.

2.2 班次分配

整数规划模型的符号表示如表3、表4所示, 中心决策变量为是否将第d∈D天的班次s∈S分配给员工e∈E, 即:

表3 班次分配集合符号

表4 班次分配参数符号

其他决策变量为:

班次分配整数规划模型的目标函数(8)是最小化未完成任务的总工时, 保障最大任务覆盖率.具体模型如下:

约束(9)表示如果班次s被分配, 则有一名员工e分配到班次s, 否则这个班次未被分配.约束(10)表示每个员工每天最多上一个班次, 否则就休息.约束(11)表示每个员工每月工时最少Hlb小时, 最多Hub小时.Cij为常数, 是根据班次信息提前计算好的, 约束(12)考虑前一个班次对后面班次的影响, 例如前后班次上班间隔时间要不小于规定时间等, 确保分配的班次能够由同一个员工完成.约束(13)和约束(14)表示员工每周至少休RWlb息天, 至多休RWub天.约束(15)和约束(16)表示员工每个月至少休息RMlb天, 至多休息RMub天.表示夜班班次的集合, 则约束(17)表示在连续夜班之后,强制休息2天.

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

从管理的角度出发, 本文考虑的均衡性主要包括两个方面: 一是基于班次之间工作量的均衡性, 即使得每个班次间总任务数量以及长任务数量尽可能平均,保障分配到不同班次的员工所做任务数量均衡; 二是基于每日完成任务覆盖率的均衡, 保障员工间工作强度的均衡.

本文将采用在原优化目标中加上一定权重下的均衡优化目标或者在原约束条件中加上均衡约束的方法来限制优化目标.

3.1 基于班次间的均衡

根据对航空物流服务公司出港操作室的访谈, 得出该部门班次间的均衡主要体现在班次间总任务和长任务数量的均衡.假设 α ,β分别总任务数和长任务数的公平项的权重, 则纳入到班次生成模型中有:

基于班次间均衡的目标函数式(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节分配约束和第3节均衡策略进行分配.

图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 邻域结构设置

邻域结构的设计是变邻域搜索算法的核心, 在保障解的可行性前提下进行领域动作, 生成可行的候选解.本节设计了3种邻域结构来生成候选解: 任务交换、任务插入、任务交叉, 分别设为N0、N1、N2.

(1)任务交换方法

从候选解中随机选择两个班次s1和s2, 交换两个班次中的任务, 生成新的班次和.判断和是否满足班次生成约束条件, 如果满足则进行交换, 如图1所示.

(2)任务插入方法

从候选解中随机选择两个班次s1和s2, 将班次s1的任务移除插入到班次s2中, 生成新的班次和.判断和是否满足班次生成约束条件, 如果满足则进行交换, 如图2所示.

(3)任务交叉方法

从候选解中随机选择两个班次s1和s2, 在两个班次中分别选择一个任务节点进行交叉, 互换后面的所有任务, 生成新的班次和.判断和是否满足班次生成约束条件, 如果满足则进行交叉, 如图3所示.

4.1.3 基于变邻域搜索算法的模型求解

变邻域搜索算法利用4.1.2节的3种邻域结构进行搜索, 整个算法过程只接受可行解.每进行一次邻域动作就对新生成的解进行评估, 评估函数为3.1节的目标函数g(s), 如果对比起当前解s, 新的解有g(s), 则更新当前解为s′, 当找不出比当前解更优解时,跳到下一个邻域进行搜索.具体算法步骤如算法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输出: 优化班次生成方案images/BZ_298_398_793_478_818.pngimages/BZ_298_614_793_643_818.png(1) 令当前解; //初始解 由4.1.1节贪婪算法生成 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) ; //以 为初始解进行局部搜索, 获得局部最优解()images/BZ_298_315_1249_586_1299.png(6) //如果局部最优解优于当前解, 则更新当前解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) ; //返回优化班次生成方案

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, 并更新其月工时、休息日等相关状态.否则将班次加入到不可指派班次中.

Step 5.重复Step 2-Step 4, 直到所有班次分配完毕, 算法结束.

5 数值实验

5.1 实验数据

数值实验选取航空物流服务公司出港操作室2019年11月份数据, 包括64名员工、6种岗位.总任务个数为7893个, 操作岗任务为7161个.表5显示了具体任务信息, 可以看出除了操作岗其余各岗位时长均超过7小时, 即一个任务为一个班次, 而操作岗时长较短, 一个班次往往包含多个任务, 因此第4.1节的任务移动操作主要针对操作岗.

表5 任务信息表

5.2 实验设置

本文采用Java实现第4节算法, 实验使用的硬件环境为Intel(R) Core(TM) i7-8550U CPU @1.80 GHz主频, 内存为8 GB的计算机.班次生成算法设置最大迭代次数,, 休息天数参数的时间单位时间为天, 其余时间单位为小时, 在计算程序中转化为统一单位计算, 具体参数设置如表6所示, 参数含义参考表2和表4.

表6 实验参数设置

5.3 实验结果

实验共生成班次1524个, 班次生成方案的信息包括班次日期、班次编号、班次起始时间、班次岗位资质、以及班次保障任务集等, 具体实验结果如表7所示.

表7 班次生成实验结果

其中, 生成的操作岗班次由多个保障任务构成, 由第3节可知为了保障同岗位资质的班次间的工作强度一致, 尽可能保障同类班次间的总任务数以及长任务数的数量平均.图4和图5分别表示在班次生成阶段2019年11月操作岗班次的中总任务数量和长任务数量的个数.

图4 操作岗班次总任务个数分布

图5 操作岗班次长任务个数分布

由上述实验数据可知, 一个操作岗班次总任务大多集中在9个左右, 其余都在与平均总任务个数相差1个任务幅度范围内, 每个班次长任务个数集中在1个到2个, 整体上呈现均衡.根据航班数据显示, 航班存在比较明显的起降高峰, 在航班起降低峰期班次内任务数量较少, 起降高峰班次内任务数量较多是不可避免的, 因而总体的班次生成方案设置合理, 在工作量以及工作强度上呈现均衡性.

在班次分配阶段, 由Mava-|S|得出的理论上不可完成班次为88个.未对均衡任务覆盖率限制的情况下,即4.2节中不进行Step 4的判断, 得出的2019年11月的月度班次分配情况如图6所示, 未分配的班次为88个, 达到理论最优值, 集中在月末2天.均衡任务覆盖限制后, 2019年11月的月度分配情况如图7所示,未分配班次数为90个, 仅比最优值多2个, 但在月度上呈现均衡, 在管理的角度更加可取.

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

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

6 结论

本文在结合国内外机场地勤人员排班研究的基础上, 调研航空物流服务公司出港操作室的具体业务场景, 建立了一套均衡任务覆盖率模型.数值实验表明这个模型对航空业或受季节、突发事件影响大而导致的缺人的情况下更有效.均衡任务覆盖模型可以很好应对不确定性, 给现场调度人员最大的可安排空间, 同时将公平性融入到排班计划中, 提高员工的满意程度和人员保留率, 间接降低人员招聘和培训等运营过程成本, 在管理上行之有效.

本文虽对现场调度因素做了一定的考量, 但目前算法仍主要关注班次生成和班次分配阶段, 在今后的研究中可以对现场调度涉及因素更细化地考虑进模型中, 形成一个更科学、更合理的智能排班系统.