基本模型：单项目调度数学模型符号列表续表与0-1规划描述

资源受限项目调度问题可以采用单代号方式描述为如下的有向图G=（V，E）：项目包含一组共J个任务，其集合记为V，第j项任务的工期为pj；任务的开始时间记为sj，完成时间记为cj，假定每一项任务均不可中途暂停，因此任务的完成时间为cj=sj+pj；任务j完工时的净现金流记为NCFj。任务之间存在紧前关系，即有向图G中的弧集E，如果任务j与任务h之间存在紧前关系（h，j）∈E，则任务j必须在任务h完成之后才能开始。记任务j的紧前任务集合为pj。假设任务之间只涉及基本的紧前关系，不存在回路与反馈。

项目涉及K种可更新资源，其中第k种资源的容量为Rk；第j项任务在执行时需要若干种资源，其对第k种资源的需求量为rjk；项目在某一时刻对任一资源的需求不能超过该资源的容量。

对资源受限项目调度问题的求解，就是要寻找合适的进度计划为每个任务确定一个可行的开始时间。项目进度计划可以表示为一个J-元组：S=（s1，s2，…，sJ）。该计划同时满足紧前关系与资源约束，并最优化项目的目标函数。

表2.2列出了单项目调度问题的常用符号。

表2.2　单项目调度数学模型符号列表

续表

如此，则基本的RCPSP可以描述为：(www.xing528.com)

目标函数为项目工期最小化。式（2.26）要求项目进度计划遵循任务之间的紧前关系，任何任务的开始时间必须大于等于其所有紧前任务完成时间的最大值。式（2.27）要求项目进度计划满足资源约束，在任何时刻，项目对任一可更新资源的总需求不能超过其供应量。

对于式（2.25）至（2.27）所示的RCPSP，也可以采用0-1规划的形式加以描述。所采用的决策变量xjt定义如下：

则上述RCPSP可表示为：

式（2.30）要求一项任务在开始之后不能被抢占，必须连续执行直到完成；式（2.31）表达项目内部各任务之间的紧前关系，即一项任务必须在其所有紧前任务完成之后才能开始；式（2.32）则限制了任一时刻所有进行中的任务对任一资源的总需求不能超过该资源的供给量；式（2.33）定义了决策变量的可行域。

上述RCPSP问题已被证明为NP-hard问题（Demeulemeester and Herroelen，2002）。因此，对于大型的项目调度问题，精确算法无法有效地进行求解，这也是项目调度领域的学者侧重于启发式算法研究的重要原因。