运筹优化在地服人员派工系统中的应用简介

运筹优化在地服人员派工系统中的应用简介

——以HCC项目为例

人员派工是运筹优化的一个常见的应用领域，本文结合目前正在进行的项目对这方面的内容进行一个简单的介绍。

1. 概述

人员派工模型的基本对象是两个，shift和task。shift是人员的上班时间安排，即排班，一个人一天的上班时间称为一个shift，task即需要完成的工作任务。

一般完成某个任务都需要有相应的资质，每个工作人员也都具备一定的资质，所以每一个shift也都具备一定的资质。另外每一个任务都有相应的时间限制，即起止时间，而shift也有对应的时间范围即上下班时间。所以，对于每一个任务，能够完成该任务的shift必须具备相应的资质，并且时间也要符合要求。

派工系统的作用就是将每一个task分配给相应的shift，目标是尽量用少的shift完成尽量多的任务，同时要兼顾公平性等一些原则。

在实际中，有的时候人员排班是事先确定好的，这时我们只需要考虑将task安排给shift。有的时候排班没有事先确定好，那么就需要在算法中排出shift然后再分配task。一般的做法是先根据人数和任务的分布排出shift，然后进行派工，如果任务完成率达不到要求，就重新调整shift，然后再进行派工。排shift的方法一般比较简单，本文主要介绍派工算法。

1. 基本模型

定义：

Shift集合，对每个shift i都有上下班时间

Task集合，对每个task j都有起止时间

变量  如果task j被安排给shift i，否则

变量，如果task j没有安排给任何shift，否则

变量，为task j未完成的成本

目标函数：

约束：

1) Σxij<=1,for i in I,j in J that i is quanlified for j but conflicts

2) Σxij+zj=1,for j in J,zj is the punish variable

另外资质在派工中也很重要，但资质在模型中一般作为筛选条件，会对task和shift的关系产生影响，即规定了哪些shift可以完成哪些任务，但是不影响模型的基本形式。  

1. 最大团算法

对模型中的第一个约束，判断相互冲突的任务组合，容易想到的是用两两判断的方法，但是两两判断的效率比较低，时间复杂度为n平方。这里介绍一个效率较高的算法，名子叫最大团算法。

该算法的基本想法是找到所有的最大团，其中最大团是一个任务集合，这个集合中所有的任务在时间上都是相互冲突的，并且没有其他任务和这个集合中的所有任务都冲突。最大团中所有的任务都是相互冲突的，只能选一个，这是一个比两两比较更严格并且效率更高的约束，该算法的时间复杂度为。

最大团算法：

1）对所有的任务集合，生成对应的开始和结束结点，每个节点包含相应的任务和开始或结束时间

2）将所有结点按时间排序

3）初始时把即将生成的最大团任务集设为空集，最大团集合也为空

4）对于按照时间排序的所有结点，从第一个开始判断

5）如果当前结点是开始结点，那么将结点对应的任务加入当前任务集合；

如果当前结点是结束结点并且前一个结点是开始结点，那么当前的任务集合就是一个最大团，将该最大团加入到最大团集合，并在当前任务集合中去掉当前结点对应的任务

6）继续进行第5步，判断下一个结点，直到所有的结点判断完毕。

应用了最大团算法以后，模型中第一个约束可以修改为j属于最大团中的任务集合。

1. 模型扩展

基本模型之上可以加入更多的要求形成扩展模型，典型的扩展模型简述如下：

1） 最小化所用的shift，即尽量使用最少的人员来完成任务。

可以在约束中加入每个shift的惩罚成本

2） 希望所用资质尽可能少

同样加入资质的惩罚成本

3） 吃饭或休息时间约束

如果是一个吃饭时间，可以把吃饭时间当作一个任务来看待，如果有多个吃饭时间，可以将shift复制，生成多组虚拟的shift，对于同一个shift复制的多组虚拟shift，同一时间只能有一个是有效的。

1. 实际项目中遇到问题及解决方法

任何一个实际项目中都会遇到一些模型之外的问题需要解决，这里以HCC项目为例，就项目中遇到的问题做一点介绍。

HCC项目遇到的问题是实际应用对系统的时效性要求比较高，而如果对一天的任务进行派工，运行时间太长，不能满足要求。项目团队经过研究，提出了一些解决方法，概述如下：

首先，对一天的任务进行派工运行时间太长是因为任务太多，问题规模太大，那么可以将一天的任务按时间分段进行求解，这样规模降低了，时间上就可以达到要求。

但是这样也带来一些问题，第一个就是一些任务会跨越划分时间段的分界点，解决方案是将这些任务在前后两个时间段都解一遍，但以最新的结果为准。

第二个问题是分段求解可能不是全局最优解，项目团队提出的解决办法是将分段解得到的解作为一个可行解，然后使用最短路径算法来找出全局最优解。最短路径算法也可以加入公平性等更多要求。【完】