多项目调度问题的数学模型优化

上一节描述的RCPSP问题，有一个重要的前提假设，即单一的一个项目占有全部的所需资源。在这样的假设基础上，RCPSP问题希望优化资源分配以提高项目绩效。但是项目实践及实证研究指出，多数项目都是在多项目环境下执行的，项目与项目之间往往存在着资源上的竞争与冲突（Turner，2008）。因此，就有必要分析资源受限多项目调度问题（resource-constrained multi-project scheduling problem，RCMPSP）。

多项目调度问题涉及若干并行项目和一个共享资源库，该资源库中包含若干种供应量有限的可更新资源。假设项目之间除了共享资源外相互独立，不存在项目之间的紧前关系及不同项目的任务之间的紧前关系，因此对有限共享资源的竞争是这些并行项目之间的唯一联系。

为方便对问题进行描述，在单项目调度数学模型的基础上，采用表2.3所列的数学符号。多项目调度问题涉及N个相互独立的项目，第i个项目可以表示为有向图Gi=（Vi，Ei），其中包含Ji=|Vi|个任务。全部N个项目共享K种可更新资源，其中第k种资源的供给量为Rk。用（i，j）表示第i个项目中的第j个任务，其工期记为pij，对第k种资源的需求量记为rijk，任务的开始时间标记为sij，完成时间标记为cij；任务不允许抢占，因此完成时间为cij=sij+pij。任务（i，j）的所有紧前任务的集合记为Pij。在时间t，各项目所有进行中的任务的集合标记为。考虑到各项目的重要程度不同，用wi表示第i个项目的权重。

表2.3　多项目调度数学模型符号列表

RCMPSP的求解目标是要给出多项目进度计划S=（S1，S2，…，SN），其中Si是第i个子项目的进度计划，即Si=（si1，si2，…，siJi）。

常见的多项目调度问题目标函数参见表2.4。多数为基于项目时间的目标函数，也有部分非时间的目标函数，如项目净现值、资源均衡、项目拆分等（Lova et al.，2000）。此外，还有部分文献用到更复杂的组合式目标函数（Chiu and Tsai，2002；Goncalves et al.，2008）。

表2.4　多项目调度问题常见目标函数

注：1.这两个目标函数本质上是单项目方式的，可以认为是多项目测度指标（portfolio measure）。
2.在上述原始文献中，采用CPLi取代di，即相当于设定项目i的截止日期为CPLi。
3.平均项目拖期在本质上和总项目拖期没有区别。
4.平均拖期比例事实上是加权项目拖期的一种特例。

综合上述假设和采用的符号，对应于RCPSP的常规RCMPSP，即以多项目工期（multi-project duration，MPD）最小化为目标的多项目调度问题，可以表述为：

目标函数为多项目工期，即各独立项目工期的最大值，需要优化项目进度计划以最小化该目标函数。式（2.35）表示了项目内部各任务之间的紧前关系，一个任务没有完成之前不能开始它的任何后续任务；式（2.36）则限制了在任意时间所有项目执行中的任务对每种资源的总需求不得超过该资源的供给量。(www.xing528.com)

式（2.34）至（2.36）给出的数学模型为部分多项目调度研究文献所采用（Krüger and Scholl，2009；Pritsker et al.，1969），但是该数学模型存有争议。因为该模型相当于将多个独立项目合并成了一个宏项目（macro-project）。也就是说，相当于额外增加了一个虚拟的总起始任务（global start activity）和一个虚拟的总结束任务（global end activity），通过这两个虚拟任务将N个项目合并成了一个宏项目。而项目调度的目标则简化成了最小化总结束任务的完成时间。这样的处理方式事实上成为单项目方式（single-roject approach），一般来说会导致项目整体绩效下降（Kurtulus and Davis，1982）。

可以采用加权项目总工期作为目标函数，以要求采用多项目方式（multiproject approach）进行调度，如此则数学模型修改为：

其中，wi为各项目工期权重系数。

多项目方式更能反映项目实践的真实情况。因为通常不同项目由不同的项目经理负责，项目目标函数也不尽相同。

如同RCPSP问题的拓展，RCMPSP问题也可以进一步拓展，引入多执行模式、任务可抢占、任务工期不确定、时间窗约束、加权拖期最小化等不同目标函数以及多目标优化等一系列情形。此外，对于RCMPSP问题还存在一个特殊的扩展，即考虑资源在不同项目之间的转移成本或转移时间（Krüger and Scholl，2009）。不过鉴于RCMPSP问题本身的复杂度，本书的内容主要局限于对常规RCMPSP问题的研究。

对于式（2.37）—（2.39）定义的RCMPSP，也可以采用0-1规划的形式加以描述。所采用的决策变量xijt定义如下（Pritsker et al.，1969）：

则上述RCMPSP问题可表示为：

其中，式（2.42）要求各任务均不可抢占；式（2.43）给出了每个项目内部的紧前关系约束；式（2.44）给出了资源约束；式（2.45）定义了决策变量。

[1]准备时间是相对于虚拟的起始任务而言的，可以描述为任务j和虚拟任务1之间的滞后量为ρj的开始—开始搭接关系（Demeulemeester and Herroelen，2002）。