某机场人员排班数据检验规则设计

牟 松，陈颖成，杜晴晴，余龙水，张家华

（1.广东机场白云信息科技有限公司，广州 510470；2.民航运筹优化算法实验室，广州 510006；3.广东工业大学机电工程学院，广州 510006）

0 引言

人员排班问题是一个复杂的排列组合问题，在规则组合限定范围内将人员、任务、时间、地点等进行匹配，良好的排班方案对企业的生产有积极的影响。在实际的排班过程中，问题复杂度随着人数、任务数、规则数等增加而激增。手工排班需要花费大量时间和精力，而且排班结果也可能不理想。在交通、医疗、酒店等领域均有涉及[1－3]，Baker[4]将人员排班问题分为日工时排班、休息日排班和混合排班。Bechtold[5]提出可将人员排班问题的解决方法分为手工排班、整数规划、隐式模型、目标规划等。Jorne Van den Bergh等[6]对问题从人员特征、约束条件、求解方法等角度进行了分类。Brucker P等[7]开发了一种通用的人员排班模型，并应用于几类具有代表性的人员排班问题，建立了数学模型。于贵桃[8]阐述了计算机辅助机组排班模块中所采用的混合整数优化法的数学模型。施俊龙[9]设计了话务中心的排班算法，根据预测的话务量合理地安排话务员，保证人力、技能都能够合理部署。魏云飞[10]提出依据问题的复杂程度和行业领域分为大众运输人员排班、航空公司人员排班和一般人员排班问题。赵焕省[11]研究了机组排班过程中应该遵循的排班规则，并设计了遗传算法的适应度函数和各项遗传算子。李丹波[12]总结出了呼叫中心排班中考虑的约束条件，排班方式为先设置班次，再建立人员与班次的对应关系。冯霞等[13]提出了面向层次资质的机场外航服务人员排班模型，并设计了基于禁忌搜索算法的模型求解策略。藏玉清[14]针对智能算法求解电力系统机组组合时存在的经济调度无解问题，提出了一种检验方法，有效地避免对不可行机组状态组合的经济调度。另外，黄华军等[15]针对求解混合整数线性规划问题中如何判断问题无解进行了预处理和探测，并给出了具体可编程实现的算法。人员排班问题研究过程中，人们的注意力更多聚焦在建模和求解上。

在某机场人员自动排班系统的设计过程中发现，在服从某种约束规则组合下，用户实际输入的数据并不是都可以成功排班。数据的有效性、合理性会直接影响到算法结果输出，本文研究内容就是在该机场人员自动排班系统的基础上，对数据的有效性及合理性进行检验，确保数据进入模型之后，能够有效输出排班结果。

1 问题描述及其分析

人员自动排班系统主要用于解决人员排班问题，采用算法模型解决人员排班问题需要依赖较多的基础数据。用户输入这些排班数据的时候，容易存在数据缺失、重复、格式错误、取值范围过大、数据间存在内在矛盾等情况，会导致模型构建失败或者求解失败。自动排班是一个NP难问题，随着班次数量、人员数量和约束条件的增加，理论上求解时间会呈指数增长。尽管该系统调用GUROBI求解器在运算策略上有效节省求解时间，但是仍然难以达到秒级计算。算法模型求解时间大约占业务室排班总时间的90%以上，提前发现数据问题，能够有效提高算法求解成功率及缩短求解时长。本研究旨在发现排班不成功的原因，针对性设计检验规则，在数据进入算法模型前将大部分无解数据过滤出来，避免这些数据进入算法模型，从而提高自动排班系统的效率。

数据检验问题划分如图1所示，由图可知，第I类检验主要针对表格内容、重要字段空值、取值等内容。第II类检验更多是从无解的角度出发，主要检验内容是各个约束，以及约束之间的组合是否合理等。数据检验主要对象包括班次信息、人员信息、预排班信息、约束规则、目标函数和每天最晚最早班次信息等内容。

图1 数据检验问题划分

人员排班的基本约束如表1所示。其中，资质约束和人数约束是默认约束，其他约束可依据实际情况配置。

表1 常见基本约束

2 数据检验规则

2.1 第I类检验

第I类检验需要检验的数据表有6个，共有34个重要字段或者相关字段，班次信息表展示说明如表2所示。

表2 班次信息表重要字段

表3所示为班次信息的检验内容。

表3 班次信息检验

经过上述检验之后，排班数据的大部分的重要字段在格式、取值和字段相互关联等内容均得到一定的保障，但是这种检验只能确保不会导致程序报错，并不能够确保一定有排班结果输出。

2.2 第II类检验

该类检验就是要在第I类检验的基础上，在数据进入模型之前，能够检验出在这种约束组合下，是否会有可行解输出。如图2所示，假设灰色的图案表示搜索空间，该空间主要由班次数量、人员数量等决定；黑色实线表示约束条件；深色区域表示所有约束条件的交集空间；空心圆点表示可行解；实心圆点表示非可行解；虚线为辅助曲线。

图2 人员排班问题的几种形态

在图2（a）中，存在同时满足4条约束的空间，并且该空间内有可行解，算法在搜索过程中，一旦发现有满足条件的可行解，则可以理解为有效输出排班结果，否则理解为无法找到可行解；在图2（b）中，存在交集，但是空间内无可行解，算法需要全搜索才可以确定无解；在图2（c）中，不存在同时满足4条约束的空间，算法需要全搜索才可以确定无解。

在实际测试当中，发现绝大部分是属于图2（a）和图2（c）两种情况，从约束组合是否冲突的角度划分，图2（a）和图2（b）是同一种状态，但是目前是没有理由确定在约束组合无冲突状态下，究竟是何种形态。对图2（c）形态进行分析，造成该形态的可以是约束和班次信息、人员信息间的冲突。

2.2.1 连续休假约束检验

检验描述：排班周期内，任意员工连续休假天数超过n天。

检验规则：若存在任意一位员工在连续n＋1天内无任何一个班次可以做，即不能满足连续休假约束。

检验步骤：（1）按顺序获取一位员工信息；（2）根据资质约束及班次安排情况，按日期顺序获取该员工的一个连续n＋1天可上班班次信息；（3）判断该员工无可上班次的天数是否为n＋1，若是，则记录检验信息，并进行下一步，否则直接进行下一步；（4）判断是否已遍历每个连续n＋1天，若是，则进行下一步，否则返回步骤（2）；（5）判断是否已遍历每个员工，是则结束检验，否则返回步骤（1）。

2.2.2 周休息约束检验

检验描述：一周内，任意员工不存在上班班次组合，满足周休息约束。

检验规则：找出每个员工在每周无可上班次的天数，若存在某个员工在某周内无可上班的天数为大于周休息约束上限，即不可能同时满足周休息约束。

检验步骤：（1）按序号顺序获取一名员工的信息；（2）根据资质约束及班次安排情况，按周次顺序获取该员工的一周可上班班次信息；（3）判断该员工这周无可上班班次的天数是否大于周休息上限，是则记录检验信息并进行下一步，否则直接进行下一步；（4）判断是否已遍历每一周，是则进行下一步，否则返回步骤（2）；（5）判断是否已遍历每个员工，是则修正排班周期休息约束范围，否则返回步骤（1）。

2.2.3 排班周期休息约束检验

检验描述：周期内，任意员工不存在上班班次组合，满足排班周期休息约束。

检验规则：找出每个员工在排班周期内无可上班次的天数，若存在某个员工在排班周期内无可上班的天数为大于排班周期休息约束上限，即不可能同时满足周休息约束。

检验步骤：（1）按顺序获取一名员工的信息；（2）根据资质约束及班次安排情况，获取该员工的当前排班周期内可上班班次信息；（3）判断该员工在当前排班周期内无可上班班次的天数是否大于其对应的排班周期休息上限，是则记录检验信息并进行下一步，否则直接进行下一步；（4）判断是否已遍历每个员工，是则修正排班周期休息约束范围并结束本次检验，否则返回步骤（1）。

2.2.4 周工时约束检验

检验描述：一周内，任意员工不存在上班班次组合，满足周工时约束。

检验规则：根据各个岗位的班次安排情况，在满足周休息约束的前提下，找出每个员工在每一周内可能的最大工时及最少工时，作为对应工时范围的上下界，若某员工某周内不存在一个这样的范围与周工时范围存在交集，即为不可能同时满足周休息约束和周工时约束。

检验步骤：（1）按序号顺序获取一名员工的信息；（2）根据资质约束及班次安排情况，按周次顺序获取该员工的一周可上班班次信息；（3）根据周休息约束计算一周内工作不同天数下对应的工时范围；（4）遍历步骤（3）所得到的每一个工时范围，判断是否不存在一个工时范围与所给周工时约束范围有交集，是则记录检验信息并进行下一步，否则直接进行下一步；（5）判断是否已遍历每一周，是则进行下一步，否则返回步骤（2）；（6）判断是否已遍历每个员工，是则修正周工时约束范围并结束本次检验，否则返回步骤（1）。

2.2.5 排班周期工时约束检验

检验描述：在周期内，任意员工不存在上班班次组合，满足排班周期工时约束。

检验规则：根据各个岗位的班次安排情况，在满足排班周期休息约束的前提下，找出每个员工在排班周期内工作不同天数下的最大工时及最少工时，作为对应工时范围的上下界，若某员工在排班周期内不存在一个这样的范围与修正的排班周期工时范围存在交集，即为不可能在满足排班周期休息约束或者周工时约束的情况下满足排班周期工时约束。

检验步骤：（1）按序号顺序获取一名员工的信息；（2）根据资质约束及班次安排情况，获取该员工的当前排班周期可上班班次信息；（3）排班周期休息约束下计算员工排班周期内工作不同天数下对应的工时范围；（4）遍历步骤（3）所得到的每一个工时范围，判断是否不存在一个工时范围与该员工对应的排班周期工时约束范围有交集，是则记录检验信息并进行下一步，否则直接进行下一步；（5）判断是否已遍历每个员工，是则结束检验，否则返回步骤（1）。

3 效果评估

3.1 人员排班数据集

人员排班数据集是该机场的实际数据，经过整理将20个数据集用于测试本文提出的检验规则，这20个数据集均为第I类检验，但是排班算法无法找到可行解。数据集包括班次信息、人员信息以及约束信息，对数据集中包含的班次数、员工数、排班周期、约束要求进行统计，如表4所示。

表4 测试数据的相关信息

数据中可以发现不同业务室的班次数、人员数、排班周期及约束要求一般都是不同的，而相同的业务室在不同排班周期上的情况也会有所不同。由于约束一般通过人工排班的经验结合排班需求主观设置的，而排班算法是严格按照约束规则求解，在这种情况下，排班算法也无法找到可行解。

3.2 数据检验规则效果测评

由于一些检验规则需要修正约束，因此检验顺序是需要考虑的，而且当某个数据集在前一步检验就有返回冲突数据信息，则不进行下一步检验，因此同一个数据集可能存在多次检验修改的情况。20个无解的数据集，其检验结果如表5所示。

表5 数据测试情况

对于每个数据集，每次检验不通过时都进行一次修正，直到通过所有检验后，再进行排班算法求解。

每次检验的运行时间在1 s以内，通过对20个数据集检验结果分析发现：（1）有15个数据集是由于排班周期工时约束与其他约束冲突导致；（2）有8个数据集未通过休息检验，在修正数据时发现不通过的原因大部分是某些员工的资质不包含任何班次所需的资质；（3）大部分数据集根据提供的检验信息修正后，排班算法可以找到可行解，只有2个数据集，即使通过了第II类检验，仍然无解，这是由于目前的检验方法未覆盖所有约束，以及可能存在的极端班次组合问题所造成的。

4 结束语

以往通过手工排查排班失败的原因，往往需要大量时间与精力，特别是由于排班算法无解所引起的排班失败现象，需要多次修正数据并进行算法求解，才有可能找出其原因，严重影响了排班的效率。

本文通过设计检验排班算法无解原因的方法，大大减少了人工排查的时间，在一定程度上提高了排班的效率，具有实际的应用意义。所提出的检验规则，虽然无法完全覆盖所有排班算法无解的原因，但是可以检验出常见的造成排班算法无解的原因。通过检验所提供的信息，对数据进行修正，一般可以得到排班结果，在自动排班过程中发挥了重要的作用。

本文还存在一些问题有待进一步地研究，具体如下。

（1）考虑的约束条件有限。在设计检验规则时，仅对排班约束的其中7种进行设计，并未考虑其他约束的影响。

（2）存在一定局限性。对于所提出的检验规则，尽管利用了部分数据进行了验证，但是这些规则仍有需要完善的地方，比如班次组合所得到的工时约束范围是离散的，使得在一些极端的班次组合情况下即使通过了第II类检验，仍然无法得到一个可行解。