随机资源受限项目调度问题的一种算法

本文对随机资源受限项目调度问题提出了一种基于任务关键概率的启发式算法。在该算法中，任务被调度的优先权值由其属于项目关键链的概率决定，并分别使用了关键链率乘以任务平均工期和单独使用关键链率作为优先权值的两种计算方法。在项目调度中，则分别采用了依照优先权值的大小进行调度的标准方法和以优先权值来计算被调度概率的采样算法来对任务进行调度。最后通过算例证明了该算法能够得到优于传统基于关键路径的启发式方法的调度结果。

引言

许多关于资源受限项目调度问题（Resource-constrained　Project　Scheduling　Problem，RCPSP）的文献讨论了生成项目的确定性调度计划的方法[1～3]，即在任务工期和资源确定的条件下进行调度。这个计划将作为项目实际执行阶段的指导，因此它被称作基准调度计划或预期调度计划[4]。然而，在项目执行的过程中，一些不确定因素的出现会造成项目计划的偏离，如天气变化、机械设备故障、人员受伤等等。大多数不确定因素对项目的影响会体现在任务工期和资源的增加或减少上。

目前对于不确定项目调度的研究主要有两种方法。第一种方法称为主动（鲁棒）—反应式调度。这种方法首先使用主动（鲁棒）调度在预测了可能出现的不确定因素的基础上，生成保护性的确定基准调度计划，然后在项目执行阶段不确定因素出现时使用反应式调度对计划进行修正。这种调度方法已经得到了广泛的研究[5～8]。第二种方法称为随机资源受限项目调度（Stochastic　RCPSP　或　SRCPSP）。在SRCPSP中，项目的执行由调度策略（Scheduling　Policy）替代确定性的基准调度计划来决定[9～10]，它是一个多阶段的决策过程。在项目开始以及每个任务完工的决策时刻，调度策略将决定哪些任务可以开工。随机资源受项目调度最常见的目标是最小化项目的预期完工时间，Stork[11]在他的博士论文中使用了分支定界算法来对其进行精确求解，而另一些文献则对求解这个目标的启发式算法进行了研究[12～14]。另外，Sobel等[15]基于最小化期望净现值目标提出一套算法，而Deblaere等[16]则对随机调度的稳定性目标进行了研究。

本文基于SRCPSP的最小期望工期目标提出一种基于任务关键链概率的启发式算法。论文的结构如下：第2节对随机调度问题的基本内容进行了概述；第3节介绍了本文算法的步骤；在第4节通过一个算例检验了算法的性能；第5节给出了最后的结论。