基于二分图的满足时序约束的迭代增量式的最大派工方法

技术领域

本发明属于指派问题中的最大匹配技术，具体是一种基于二分图的，针对时 序约束进行优化后，能够迭代增量式地指派任务的最大派工方法。

背景技术

随着信息化水平越来越高，无纸化办公、自动化办公已经越来越深入人心。 可是，很多服务机构(如家政公司)还在使用原始的手动派工方法，这显得和时 代有点格格不入。手动派工，不仅费时费力，效率低下，而且因为种种限制条件， 往往不能统筹兼顾，获得最大效益。这时，一个优秀的派工方法就显得尤为重要。 当然，想要达到提高效率，降低成本的目的，这个派工方法就必须要足够的智能。 而二分图模型则是解决这一类问题的最佳选择之一。

二分图又称作二部图，是图论中的一种特殊模型。设G＝(V，E)是一个无向 图，如果顶点V可以分割为两个互不相交的子集(V₁，V₂)，并且图中的每条边<i，j>所 关联的两个顶点i和j分别属于这两个不同的顶点集(i in V₁，j in V₂)，则称图G为 一个二分图。二分图是指派问题的数学模型，其中顶点集V₁表示一组任务，V₂表 示一组人员。连接顶点i和j的边则表示可以将任务i指派给人员j。派工问题研究 的重点就是，如何快速、有效、合理地将左边的任务尽可能多的分派给右边的人 员。

给定一个二分图G，在G的一个子图M中，如果边集E的任意两条边都不依附 于同一个顶点，则称子图M是一个匹配。在二分图中寻找这样的边数最大的子集 称为最大匹配问题。那么，解决上述派工问题的思路就转化为寻找对应的二分图 模型中的最大匹配了。一个显而易见的算法是：先找出所有匹配，然后匹配数最 多的自然就是最大匹配。但是这个算法的时间复杂度随着边数的增加而呈指数级 增长，一旦匹配规模大了，效率肯定下降的很厉害，所以实用性不强。

其实早在1965年，Edmonds就提出了更加高效的算法，该算法的核心是不 断地寻找增广路径。每找到一条增广路径，就通过异或操作，在原有匹配的基础 上增加一条匹配边。当再也找不到增广路径时，得到的匹配就是最大匹配。这就 是著名的匈牙利算法。匈牙利算法的适用范围很广，如指派问题，婚配问题等。 而指派问题作为一类特殊问题，它与其他问题最大的区别就是时序性，主要表现 为不同任务之间具有时间上的前后关系，同一个人员也能在不同时间段内完成不 同任务。在分析具体问题时，这种时序性就表现为一种时序约束。很显然，匈牙 利算法本身并没有针对时序约束进行优化，一个人员只能分派一个任务，所以得 到的最大匹配可能并不是真正意义上的最大。在满足时序约束的情况下，考虑给 某些人员重复派工(称为迭代增量式的派工)，是完全有可能找到一个更大匹配 的。

发明内容

本发明的目的在于提供一种基于二分图的，通过对时序约束的优化，能够迭 代增量式地派工的最大派工方法。

实现本发明目的的技术解决方案为：基于二分图的满足时序约束的迭代增量 式的最大派工方法，包括以下步骤：

第一步，对一组等待派工的任务进行预处理。主要是根据任务开始时间的先 后顺序进行排序，得到一组有序的任务，记为R′。然后对R′中的每一个任务r_i计 算能够完成该任务的人员子集P_i，子集中的每一个人员不仅有能力完成该任务， 而且时间安排上也不会与之前已派工的任务冲突，即同时满足技能约束和时间约 束。最后，从R′中剔除P_i为空的任务r_i(因为该任务没有人能完成，肯定派工失 败)，形成最终的有序任务集R。

第二步，由有序任务集R计算冲突矩阵C。C＝R×R，因此C是一个N×N的 方阵，N是任务的数量。矩阵中的每一个元素c_ij的取值范围都为1或2。c_ij＝1表 示任务r_i和任务r_j在时间上有冲突，而c_ij＝2表示r_i和r_j有前后时序关系。冲突矩 阵是下面计算人员总集和冲突边的基础。

第三步，由人员子集P_i计算人员总集P。具体过程是，i＝1时，将P₁中的节 点直接加入P中；当i＞1时，将P_i与P₁，P₂，…，P_i-1逐个执行“合并-分身”操作， 合并就是取并集的意思，合并每次都执行，但是分身是在两个子集中出现相同的 人员节点且对应的两个任务存在前后时序关系时才执行。将分身节点和P_i中剩下 的节点纳入P集合，本身节点因为已存在就不再纳入。这样最终就能形成人员总 集P。也就是说，同一个人员在人员总集P中会有本身和分身两种存在形式，这 是迭代增量式派工的特点之一。

第四步，利用前三步得到的任务集R，冲突矩阵C和人员总集P，构造时序二 分图G。时序二分图是一种特殊的二分图G＝(V₁，V₂，E)，其中V₁对应任务集R， 任务节点按照前后时序自上而下排列，V₂对应人员总集P，包含零到多个分身节 点。E是边集，代表任务和人员之间的指派关系。

第五步，计算冲突边，并保存为CE集合。冲突边是两条不能同时出现在一 个匹配中的边，它出现的原因是右节点中的本身节点和分身节点(实际上是同一 个人员)尝试关联有冲突的两个左节点(两个有冲突的任务)，形成的两个指派 关系如果在同一匹配中被选中，将导致派工失败，所以需要在结果中过滤冲突边。

第六步，如果CE为空，直接使用匈牙利算法，得到的最大匹配就是派工结 果。而如果CE不为空，即存在冲突边，就需要对时序二分图G使用改进后的匈牙 利算法，得到一组最大匹配。然后根据冲突边CE进行过滤，得到有效的最大匹 配。最后根据自定义的优化规则，选择一个最优结果。

匈牙利算法改进的主要原理如下：

如果二分图是连通的，则通过循环使用匈牙利算法，得到二分图的所有的最 大匹配。如果不连通，先将二分图分割成几个连通的子图，分别使用匈牙利算法 求出子图的所有最大匹配。然后子图合并，算法结果做笛卡尔积运算，就能得到 整个二分图的所有的最大匹配。

本发明与现有技术相比，其显著优点：(1)派工的全过程都有算法和系统支 撑，人工参与度低，自动化水平高。(2)节省了相当大的人力资源和其他资源， 大大降低了派工成本。(3)派工速度大大提升，减少了派工时间，提高了派工效 率。(4)派工过程中充分考虑了能力约束和时间约束等限制条件，结果更加精确 合理，智能化水平高。(5)派工的结果经过了最大限度的优化，针对派工问题的 时序性特点，通过迭代增量式地派工，提高了人力资源的利用效率，可以获得更 大的经济效益。

附图说明

图1是本发明的任务预处理示意图。

图2是本发明的节点分身示意图。

图3是本发明的时序二分图构造示意图。

图4是本发明的方法流程图。

具体实施方式

本发明实质上是基于匈牙利算法的一种改进。

下面结合附图对本发明作进一步详细描述。

结合图1，对一组任务预处理的过程如下：按照任务开始的时间排序，得到 有序任务组R＝{r₁，r₂，r₃，r₄}。现在有三个工作人员{p₁，p₂，p₃}，分别对每一个任 务r_i计算P_i得到P₁＝{p₂，p₃}，P₂＝{p₂，p₃}，P₃＝{p₁，p₃}，P₄＝{p₃}。其中， P₁＝{p₂，p₃}意味着有能力完成任务r₁并且可以在指定的时间段内完成任务的人 员为p₂和p₃。同理，P₂、P₃和P₄也是这样理解。

因为每一个任务执行时间的长短不一样，所以图1中代表任务的小矩形长度 也不一样，任务r₂的执行时间明显要长于r₃和r₄。而且任意两个任务在时序上要 么是冲突的，要么是有次序的。从图1中可以看出，r₁和r₂是冲突的，r₁和r₃则 是有次序的，r₁和r₄也是有次序的。以此类推，冲突关系记为1，时序关系记为2， 就可以得到冲突矩阵C。

结合图2，详细说明计算人员总集P的过程。初始状态，P为空，所以直接将 P₁中的节点纳入P集合。接着处理P₂，P₂需要和P₁进行“合并-分身”操作，又因 为r₂与r₁在时序上冲突，所以只需要进行“合并”操作，也就是将P₁中不存在而P₂中存在的节点纳入P集合。再接下来处理P₃，P₃需要与P₂、P₁逐个进行“合并-分 身”操作，过程如下：r₃和r₂冲突，所以P₃和P₂只进行简单的“合并”操作；但 是r₃和r₁有时序关系，所以P₃和P₁合并完了之后还要进行“分身”操作。“分身” 操作的具体过程如图2，从节点p₃复制一个新的节点，命名为p_3-3，表明这个新 节点是对应r₃的p₃分身节点。然后移动一条边<r₃，p₃>到<r₃，p_3-3>，把r₃和p_3-3连 接起来，“分身”操作完成。最后，对P₄也进行上述相同的处理。需要注意的一 点是，为避免重复分身，r₄对r₁的p₃做分身得到p_3-4之后，就不能再对r₃的p_3-3做 分身了。这样最终可以得到人员总集P＝{p₁，p₂，p₃，p_3-3，p_3-4}。

结合图3，说明构造时序二分图然后求解最大匹配的过程。经过上面的“合 并-分身”操作后，只需要将集合R中的任务按次序排开，将集合P中的人员也合 理地排列，很容易就能构造出如图3的时序二分图。

计算冲突边的方法如下：(1)计算右边节点中同一节点及其分身的子集， P′₃＝{p₃，p_3-3，p_3-4}；(2)在P′₃中任选两个不同节点p₃和p_3-3，因为存在两条边 <r₂，p₃>、<r₃，p_3-3>，且r₂和r₃有冲突，所以这两条边是一对冲突边。(3)重复第 二步直到P′₃中所有的组合检查完毕。根据该方法，计算出图3中存在两对冲突边， 分另是<r₂，p₃>和<r₃，p_3-3>冲突，<r₂，p₃>和<r₄，p_3-4>冲突。

因为存在冲突边，所以需要使用改进的匈牙利算法求得最大匹配。算法原理 如下：(1)将时序二分图G划分连通子图，G＝{G₁，G₂，…，G_n}；(2)循环G中的 每一个子图G_i，对G_i计算所有最大匹配，得到的一组匹配记为M_ij，j＝1，2，…；(3) 子图合并，子图的匹配M_i做笛卡尔积运算，得到G的所有匹配，记为M。其中， 匹配个数|M|＝|M₁|×|M₂|×…×|M_n|；(4)根据冲突边过滤匹配M，得到无冲 突边的一组有效匹配子集M′；(5)若|M′|＝1，则M′即为最终解，若|M′|＝0， 则无解。否则存在多个有效匹配，根据自定义的优化规则，为每条边赋一个权值， 计算每个有效匹配的权值和，选取一个最优解作为派工结果，完成。

本发明所列举的4个任务{r₁，r₂，r₃，r₄}和3个人员{p₁，p₂，p₃}的情况，只是为 了更清晰地描述派工方法，实际应用时对任务数和人员数并没有限制。