流程执行时间最小化的资源分配方法

图6.1所示为用流程建模标准BPMN描述的航空公司赔偿流程模型[3]，共有7个活动。

图6.1　航空赔偿流程

该流程运行了一段时间后，产生许多流程实例运行的日志数据。每个流程实例由若干条日志记录组成，详细记录了该流程实例中的活动、资源、执行时间和成本等数据。假设流程实例运行时间的范围为2010年12月30日至2011年1月13日，删除日志中的噪声、错误数据，剩下的日志记录共有1 254条，如表6.1所示。

表6.1　航空赔偿流程日志

依据上述6.1节模型可知，获得流程执行时间最小情况下的资源分配，还要遵循资源可用性和成本约束。Xu等提出执行成本最小的资源分配方法，意图找到活动执行成本最小的资源后检验资源可用性，最后再检验总流程时间是否超过限定值[10]。这种对整个流程依次检验约束满足与否的方法效率比较低，下面提出一种优化的方法，在给活动分配资源时，同时检验可用性与成本约束，具体的过程如下：

（1）首先找出执行目标活动（待分配资源的活动）时间最小的资源。

（2）然后检测该资源的可用性，如果不可用，替换执行活动时间次优的资源，直到符合资源可用性约束。

（3）符合资源可用性约束后，预测目标活动分配该资源后的整体花费，计算是否超出成本约束。如果超出，则找到非最长路径上最合适的资源替换。这里的最长路径是执行时间最长的路径，它决定了流程的执行时间[10]。

（4）如果在第（3）步替换了资源，则重复步骤（2）和步骤（3），直到找到同时满足可用性约束和成本约束的资源。

（5）将该活动的分配信息插入资源分配表。

计算目标活动的整体花费估计超过成本约束，则需要重新分配资源，从最长路径上选择重新分配资源的活动。为了避免在资源调整过程中增加流程执行时间，可以优先调整非最长路径上的活动来降低成本。如果调整后仍不满足，再调整最长路径中的活动。