基于干扰管理的RCPSP问题研究

摘要：本文通过对RCPSP问题的研究，从资源有限这个角度对项目调度进行了分析。基于干扰管理的思想从项目网络、任务、资源和里程碑四个方面对RCPSP问题的干扰因素进行了深入分析。项目网络干扰分为新任务干扰和优先关系干扰，会引起RCPSP数学模型中J、P、S集合的变化。任务扰动分为：任务工期扰动和任务资源扰动，会引起RCPSP数学模型中t、k、d、r、CT、R、ST的变化。资源干扰主要指资源短缺，会引起RCPSP数学模型中k、r、R的变化。里程碑干扰会引起项目计划的修改，从而引起RCPSP数学模型中目标函数minCT的变化。

关键词：干扰管理；RCPSP；资源受限；项目调度

一、引言

随着经济的高速发展，企业之间的竞争愈演愈烈，企业为了不断提高自身的竞争能力，需要不断地创新，开发竞争力强的项目。由于项目本身的特点，具有一定的复杂性和约束性，又要平衡资源需求和工期上的矛盾，这就使得项目调度计划的制定很难在短时间之内被完成。而在实践中，项目的执行通常具有很高的不确定性，各种随机事件都会对项目本身产生不同程度的影响和干扰，从而导致项目调度计划的改变。所以当干扰事件发生以后，需要对干扰事件进行及时的处理，尽量减少对系统整体的影响，尽量以最小的扰动和最短的时间恢复系统的正常运行。对RCPSP问题，即资源受限项目调度问题进行干扰管理研究，有利于企业充分利用有限的资源，合理地安排任务以降低成本，提高经济效益。

二、RCPSP问题研究

项目是由一组有起止时间、相互协调的受控活动所组成的特定过程，该过程要达到符合规定要求的目标，包括时间、成本和资源等约束条件。项目调度问题主要是研究如何从时间上和资源上合理地安排和调度项目的活动，在计划工期内实现项目的既定目标，以达到工期或资源的最优化。项目调度就是为项目中的各个任务分配资源及确定任务开始时间。合理的项目优化调度能显著提高项目管理水平。

项目在执行过程中需要各种各样的资源，一般来说，资源的使用都是受限的，因为在绝大多数项目中，资源本身是有限的或者获得额外资源的成本过高而不可行。因此如何充分利用各种有限资源完成项目就成为项目管理过程中的一个重要的问题。资源约束下的项目调度问题最早是由Kelley于1963年在求解资源限制的项目调度问题时提出的。RCPSP（resource　constrained project scheduling problem），即资源受限项目调度，是从资源受到限制这个角度来研究项目调度问题，是为在满足项目优先关系约束与资源约束的前提下，安排所有任务的开工期和完工期，以达到某一最优的目标，如工期最短、成本最小、资源均衡等。

RCPSP问题可以用如下的数学模型来表示：

j为任务序号，j=1,2,……，J；其中J为项目所含任务的总数量。t为时间序号，t=1,2,……，T；其中T为项目所含任务的总数量。k为资源序号，k=1,2,……，K；其中K为项目所需可更新资源种类。d为任务的工期，P为任务的紧前任务集合，S为任务的紧后任务集合，ST为任务的开始时间，CT为任务的完成时间，R为任务所需可更新资源的集合，r为资源K的供给量。

三、RCPSP问题干扰因素研究

由于客观世界存在着诸多的不确定因素，使得项目在实施过程中经常发生对原有调度方案产生扰动的情况，各种随机事件都会对项目本身产生不同程度的影响和干扰，从而导致项目调度计划的改变。所以当干扰事件发生以后，需要对干扰事件进行及时的处理，尽量减少对系统整体的影响，以最小的扰动和最短的时间恢复系统的正常运行，这就是干扰管理(Disruption Management)理论的内涵。干扰管理的定义，在理论研究领域并没有统一的和固定的规定，但相对来说比较权威的是美国学者Gang Yu提出的定义：在项目计划制定阶段，通过运用模型和算法得出一个较优解；在项目计划执行过程中，由于干扰因素的存在使得原项目计划变得不可行，需要及时地产生新的项目计划。新的项目计划既要尽量满足原目标函数，又要使干扰因素带来的负作用最小化。

目前，干扰问题的研究方法应用较多的是scheduling和re-scheduling方法。这种方法就是从扰动后的最终状态出发，对最终状态的项目系统重新进行项目计划设计，通过对原项目计划的全盘重新设计，来达到对干扰事件的管理。这种方法的本质是把变化后的项目当做一个新的项目来对待，虽然能够得到一个最优的干扰事件解决方案，但要耗费大量的时间、人力、财力和物力，并且新的项目计划有可能与原项目的目标函数相差甚远，使得新项目从实际意义出发是没有意义的。而干扰管理却不同，它是根据干扰事件发生以后的状态对原项目计划进行局部的调整，目标是使项目计划变动最小，同时也适当考虑尽量节省费用，但不是追求费用的最小化。

在项目计划的执行过程当中，干扰事件主要体现在项目网络（network）、任务(activity)、资源(resource)和里程碑（milestone）四个方面。

项目网络干扰。项目网络的结构是由基本任务和它们之间的优先关系组成的。在项目的执行过程中，会根据现实情况新增一些相关任务，也会根据实际条件取消一些任务，或者根据需要来改变任务之间的优先关系。分为：新任务干扰和优先关系干扰。新任务干扰即为增加或减少某些任务所产生的干扰，优先关系干扰即为改变当前网络图的优先关系所产生的干扰。项目网络干扰发生时，会引起RCPSP数学模型中J、P、S集合的变化。

任务干扰。当一项任务的完成时间和资源使用情况与原来的计划发生了变化，就被认为是任务受到干扰。任务扰动分为：任务工期扰动和任务资源扰动。这种干扰可能是有利的也可能是有害的。如在单件小批的生产中，由于生产技术、原料供应、产品质量等原因都有可能引起时间的变化，导致生产时间的延长或缩短。也可能因为原料的质量、操作者的熟练程度等原因引起资源使用量和种类的变化，导致资源需求量和种类增加。任务干扰发生时，会引起RCPSP数学模型中t、k、d、r、CT、R、ST的变化。