流程执行时间最小化的资源分配模型

在讨论资源分配模型之前，首先介绍一些基本的概念。

资源分配表用来存储每个活动的资源分配情况，当为活动分配一个资源时，则在该表中插入一条记录。主要包含活动v、分配的资源s、对应的角色r、活动开始时间start time、结束时间end time以及前一个活动v′。资源分配表包括以下内容：

（1）对于某业务流程P，定义活动集合SA＝﹛vi|i＝1，2，…，k，k为流程活动总数﹜；资源集合SP＝﹛si|i＝1，2，…，n，n为流程资源总数﹜；角色集合SR＝﹛ri|i＝1，2，…，m，m为流程角色个数﹜。

（2）活动、资源的前驱和后继关系：前驱活动是顺序连接活动中，发生在前的活动；后继活动就是发生在前驱活动之后，且直接连接的活动。执行前驱活动的资源称为前驱资源，执行后继活动的资源称为后继资源。活动i是j的前驱活动，活动j是i的后继活动；如果资源s i是s j的前驱资源，则资源s j是s i的后继资源。特殊地，流程的起始（终止）活动（资源）不存在前驱（后继）活动（资源）；并行的活动不存在前驱和后继关系。在公式（6.1）中，RA表示活动之间的关联集合，RP表示资源之间的关联集合，则有

资源分配的目标是使流程的执行时间最小化：式（6.2）中的D（P）是流程P所用的时间，Time（v）是流程中每一个活动所耗用的时间。保证流程时间最小化的前提是要满足两个约束：一个资源在每一时刻只能分配给一个活动以及流程成本必须在一定的约束内。式（6.3）中的N（tm，s）表示在时间tm资源s被分配的活动数量，Cpst（s，v）表示资源s执行活动v的成本，cpst lim表示给定的成本约束。