自动排班系统设计及阶段性成效

程 宇，夏侯康，邵奇一，徐国宁，詹智勇

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

0 引言

随着旅客对航空行业接受度的提高，客流量逐年上涨，国内机场面临新的竞争压力，急需符合行业战略发展需要的信息化系统和应用解决方案。国内机场对于排班算法的研究尚处于起步阶段，鲜有实际的应用案例。机场地面服务人员排班运筹优化算法及系统作为全国较早研究机场排班算法的实际应用，在中国民航业内有开创性的意义。

人员排班问题可以追溯到20世纪50年代，护士和警务相关人员的排班在一开始便是学者热衷研究的对象[1-6]，在求解方法上也是多种多样，最近这几年也有学者采用变领域搜索算法[2]和带权禁忌算法[4]进行求解。Bergh V D[7]对护士排班问题进行综述总结，并提出Nurse-Date，Nurse-Shift和Nurse-Task的划分方式。后来，学者发现排班问题在各行各业中都有着需求，而且，不同行业上班方式的差异化，导致以往研究的成果不能完全可以套用。在民航相关领域，有关注飞机排班问题的[8-9]，有关注机组排班问题的[10-13]，也有关注机场地面服务人员排班问题的[14-17]。卢敏等[13，17]在文中提出层次资质的机场外服人员排班问题。这个问题在理论背景和本文所提出的有不少相似之处，但是远不能满足实际应用。关注到地面人员排班问题，更多的是从管理的角度去提出新的班次长度，人员搭配等等，这也是对这类问题研究的一个角度。关于约束满足相关内容Tsang E[21]给出了详细的说明。约束满足问题（CSPs）是人工智能和运筹学的热门主题，因为其公式中的规律，提供了共同基础来分析、解决很多看似不相关的问题。国内的很多学者将不同领域的问题转化成为约束满足问题进行处理[18-20]，李俊芳等[19]利用约束满足技术对并行机Job-Shop调度问题进行研究，许绍云等[20]在流水车间订单投放中应用修复式约束满足算法。经过众多学者的努力，在人员排班问题上，取得不少成果，但是也衍生出更多新的问题，为后续的研究提出更大的挑战。

目前了解到，部分机场从国外引进排班系统，部分尝试组建科研团队自主开发。香港怡中公司引进Sabre的资源管理系统。南方航空公司经过近5年持续开发和优化，目前已基本实现了“人员规划—计划排班—任务安排—统计决策”功能。东方航空公司于2012正式启动一期排班调度系统建设，于2014年基本完成开发建设。2015年，东航开始在国内重点推广应用该系统。2016年，东航启动了二期建设（功能不仅是排班系统），2017年底完成。

1 问题描述

自动排班系统覆盖4个二级子单位，影响员工总数达6 200余人。各二级单位包含多个业务室，这些业务室的工作内容不同，在排班方式上也有较大的差异，在参考Bergh V D所提出的排班分类的基础上，结合所有业务室的排班业务情况，经过深入的调研、分析及总结，将问题划分为时刻型，任务型和固定型3种类型。

（1）时刻型：基于航班实际时刻的工作量分布，工作量与实际时刻的变化密切相关。

（2）任务型：基于航班任务计划时间的工作量分布，工作量可根据航班计划时间提前预期，与航班实际时刻的变化关联较小。

（3）固定型：值守型岗位工作量分布，工作量和工作时间相对固定，与航班实际时刻变化无关。

人员排班问题的归类，利于整体求解流程的设计。实际上，根据不同业务室的工作特点，仍然有一些不能忽略的特殊性存在，也因为这种特殊性的存在，导致方案设计、解决问题的时候更加复杂。

2 实现方案

2.1 自动排班系统整体框架设计

用户登录终端（PC或APP）通过NGINX将用户的请求转发到应用服务器，应用服务器将请求放入RABBITMQ待处理排班队列并调用算法微服务，求解器任务队列通过求解器任务调度服务，调用求解器将可行解放入消息队列，通过信息通知发送服务通知给用户。自动排班系统框架如图1所示。

图1 自动排班系统整体框架

2.2 算法核心模块的可配置化设计

模型算法模块的处理流程如图2所示。该过程划分为数据交互层、数据处理层和模型算法层。其中数据交互层需要依据其他不同业务室排班需求，接收排班输入数据，并且在完成相应的排班会后，反馈结果。数据处理层主要功能有两部分：第一是将接收到的排班输入数据进行检验，确保数据输入的合理性和可靠性，然后再将这些数据处理成模型算法输入要求形式；第二是将模型算法输出的结果进行统计和格式处理，便于后续对数据展示。

图2 模块算法处理过程设计

结合到业务室的特殊性需求进行分析之后，决定将没有必要存在的剔除，剩下不能忽视的部分，则需要尽量满足。因此在设计模型算法层的时候需要将这些特殊性的约束也考虑在内，则要求模型更具包容性。传统解决问题的方式不足以满足本项目开发要求。针对本项目各个必要环节进行可配置化设计，如图3所示。

可配置设计中包含4个环节，分别是约束条件可配置、目标函数可配置、模型参数可配置和求解算法可配置。

（1）约束条件可配置。模型中实现所有约束的构建方法，业务室依据实际需要，选择配置约束，人员排班问题的规模由任务量、人数、排班周期等决定。通常来说约束条件增加，都有可能缩小解空间，导致搜索时间增加。

（2）目标函数可配置。目标函数决定优化方向，通常不会影响到解空间的大小。随着目标函数数量的增加，为了满足多目标的联合要求，最终也会耗费更多的时间。

图3 重要环节可配置化设计

（3）模型参数可配置。模型参数的配置可以影响求解时间和解质量。

（4）求解算法可配置。当前阶段主要应用Gurobi自带的算法，可以通过该参数设置启发式算法和精确求解算法的侧重程度。

2.3 核心模型设计

本节主要对核心模型及相关内容的配置进行介绍，包括目标函数和约束条件两部分的表达，这两部分强调的是不同类型人员排班问题共性的内容。初步描述如下。

2.3.1 符号说明

建模用到的符号说明如下：x(e,m)表示员工e做任务m；y(l,e,s)=1时，表示员工e在第l天做班次s；q(e,m)=1时，表示员工e具备任务m的资质；t(m,1)为任务m的开始时间；t(m,2)为任务m的结束时间；d(m)为任务m需要的人数；max_num(e,m)为员工所做任务数的最大值；max_num(e,rest)为员工休假天数的最大值；sum(n)为所有员工所做夜班数总和；low_hour为每日工作时长下限；up_hour为每日工作时长上限；num(e,rest)为员工周期内休假天数。

2.3.2 基本目标函数

不设定基本目标函数。

2.3.3 基本约束条件

（1）员工做某任务，必须具备该任务需求的资质。若q(e,m)=0，有：

（2）分配的人数应当和任务需求的人数对应：

（3）任何一位员工在同一时刻不能同时负责多个任务；若|t(m+j,2)-t(m,1)|＜t(m)+t(m+j)，有：

接下来在可配置目标函数和可配置约束部分可以看到，针对不同的业务室，不但可以调整约束右端项取值，同时可以依据业务室的特点选择合适的内容。

2.3.4 可配置目标函数

员工做任务的数量均衡：

员工所做的工时均衡：

员工所做的夜班数量和尽量少：

员工休假天数均衡：

2.3.5 可配置约束条件

员工每天上班的时长：

员工每天选择的班次类型（早班、中班和晚班）：

员工一段时间内休假的天数：

2.3.6 可配置模型参数

（1）模型运行时间：Gurobi.TimeLimit=Calcu_Time

（2）模型搜索节点数：Gurobi.NodeLimit=Search_Node

2.4 核心模型求解流程

自动排班系统在求解的时候除了考虑构建模型的可扩展性外，在求解流程也需要有同样的思考方式，在此不赘述。模型求解大致流程如图4所示。

3 实施效果

3.1 案例展示1——国际值机室

3.1.1 结果展示

排班结果展示中，利用多种方式展示结果，一方面利于排班员查看，另一方面一线员工可以直接依据排班任务上下班。在甘特图中展示已排任务和未排任务两种类型，排班员可以对这些任务进行操作，将未分配任务合理安排。如图5所示，条框部分为已分配任务，深色的方块表示任务实际作业时间，浅色表示任务间隔的空闲时间；褐色则表示未分配任务，在图中可以看出未分配任务相对位置。

3.1.2 结果对比

（1）覆盖率

图4 模型求解流程

图5 国际值机室员工任务展示

手工排班时，任务无法实现全覆盖，但是在实际工作中，可以通过降低人力标准或者一人同时负责多个任务来解决。自动排班时，不允许将多个任务同时安排给一人，需要严格按照服务标准进行排班。但是自动排班系统所得出来的结果，其覆盖率仍然高于手工排班的覆盖率。

表1 任务覆盖对比

在自动排班系统当中，可以自动统计出各个时段任务分布和未分配任务的覆盖情况，如图6所示，条框为每个时段任务量，曲线为通过自动排班系统安排出来的已分配任务量。

（2）有效工时率

图6 国际值机任务覆盖信息

在手工排班当中，排班结果在使用时会不断调整，所以手工排班人均有效工时需要通过覆盖任务的总时长除以上班总人数。由于存在一个人同时担任多个任务的情况，在计算人均有效工时有较大差异，这里不作统计。在自动排班系统当中，这些指标都可以即时统计。国际值机有效工时率对比如表2所示。

表2 国际值机有效工时率对比

3.2 案例展示2——物流国内出港操作室

3.2.1 结果展示

物流国内出港操作岗位员工执行任务展示如图7所示。

图7 物流国内出港操作岗位员工执行任务展示

3.2.2 结果对比

（1）覆盖率

如图8～9所示，手工排班结果不能覆盖所有任务。进一步和用户确认后，发现需要通过加班的方式来保证任务完成情况。自动排班则依据任务分布情况，实现任务的全覆盖。

图8 手工排班任务覆盖情况

（2）有效工时率

图9 自动排班任务覆盖情况

物流国内出港操作岗手工排班是将人员安排到相应的班次上，未能实现将人员和任务匹配，故无人均有效工时相关统计。如果单单从排班结果的对比（不考虑临时加班），手工排班的人均有效工时和人均上班工时均是低于自动排班的结果。如果从任务全覆盖的角度对比，两种排班方式的人均有效时长理论上是一致，但是人均上班时长增加，导致有效工时率低于自动排班。如表3所示。

表3 物流国内出港操作岗有效工时率对比

4 结束语

本次研究通过对机场一线员工的岗位资质和工作量进行估算、设计、优化和调整，在机场一线员工中高效地利用各种人、财、物资源，提高运营效率，降低运营成本，建立一个结果正确、响应及时、可人工干预、整体联动，并根据航班信息、员工资质、保障任务、约束条件，并通过混合算法运筹优化排班的机场地面服务人员排班运筹优化算法及系统。

（1）实践成效

该系统已在机场的航服国际值机室、物流国内出港操作、地勤客舱清洁等业务室使用，在任务的覆盖率、人均有效工时率均有提升，并实现数据采集，有助于实现人力资源排班方面的精细化管理。

（2）市场独有性

全球民航业的机场地面服务人员排班系统被国外商家垄断，国内只有少数航空公司尝试上线地面服务人员智能化排班系统。在本产品上线之前，国内机场目前并没有真正投入使用地面服务人员智能排班系统，本次研究的产品在国内市场上具备独有性，拥有十分广阔的市场前景。

（3）技术领先性

系统架构通过多个微服务，响应不同的请求，可实现多线程处理；模型求解过程可实现约束多级调整，并设计了无解机制，通过生成未分配任务，再通过手工调整的方式，提供系统实用性；可配置化设计，实现参数、约束、目标等按需配置。