一个资源约束项目调度模型与启发式算法分析

1引言

1.1研究背景与意义

在全球经济高速发展的今天，行业及资源的多样性己经带给人们广阔的发展空间。随着科学技术的进步，人们可以更加有效地完成自己的学习工作。为了创造出更多的社会价值，节省不必要的资源开销，管理的思维应运而生。目前采用项目方式开展的经济活动占全世界的百分之三十。由于项目管理能够有效的制定项目计划、配置调度项目资源、控制项目的进度及成本，因此在企业中得到了广泛的应用。在众多行业的不同领域中，项目管理成为发展的必要趋势。随着世界经济的飞速发展，全球市场的竞争愈发激烈，企业的规模也大于从前，从而对项目管理的要求也越来越高，有更多的人参与到管理方法的研究中。在项目管理中，项目目标是衡量项目完成的重要指标，它的好坏程度与项目管理有着密不可分的关系。而项目目标的完成程度是需要管理者把控的，他们的把控能力便指的是项目的调度，因此总体来说，项目调度是项目管理中十分重要的部分。

项目调度广泛存在于软件开发、建筑工程、飞机和轮船制造等行业中，是项目工程中至关重要的环节，越来越受到项目管理者的重视，其目标是有效地完成项目中的工序。项目调度的过程是将项目环境中存在的有限资源，通过有效的方式，合理地分配到需求这些资源的工件中，每个工件因为包含多个工序，将会多次需求不同的资源，同时，这些工序对资源的需求也是有顺序的。调度过程中资源对工序的加工会产生时间、金钱等代价，而这些代价也成为了项目调度的最终优化目标。正是因为项目调度在各行业中扮演的重要角色，同时不同的调度计划将会产生不同的调度结果，因此一个优秀的项目调度计划是十分必要的。求解项目调度目标最优问题即为项目调度问题。目前有很多专家学者关注项目调度问题，其具有很高的研宄价值与应用空间。

1.2论文主要内容

文章首先介绍經典的RCPSP，从资源约束、工序间的逻辑约束展开描述，然后列出当前已存在的问题求解目标。基于經典RCPSP模型，再介绍因为需求的不同所衍生出的扩展问题模型及它们可存在的应用场景。接下来介绍当前求解RCPSP问题模型的常用研究算法，包括精确算法、启发式算法等，同时将它们进行对比分析，讨论各自的优缺点。

接下来，通过将实际项目的背景需求与經典RCPSP的问题模型相结合，介绍本文提出的扩展RCPSP模型，它在經典RCPSP模型的基础上引入了工位的概念，并假设工件只能在工位上加工，且所需资源也只能在工位处才能获得。同时，模型中还存在其他约束，如工件的各工序所需要的加工时间与其所获得的可更新资源的加工能力关于；此外，工序之间可能存在互斥关系，即某几个工序的前序工序相同，但它们又不能同时加工；工序之间可能存在依赖关系，即某工序的加工过程需要与另一工序的加工过程同时进行；工件的加工过程可能有优先关系，即在能够同时获得某种资源的情况下，一工件优先于另一工件获得资源等约束。另夕卜，在本文所讨论的模型中，需要同时安排多个工件的加工过程，而每个工件的加工过程又是一个独立的项目计划，因此，本文所讨论的模型又是一个多项目调度问题。又因为在当前文献中尚未关于于该模型的讨论，因此本模型的建立和求解都是一个新问题。

2經典资源约束项目调度问题及求解算法

资源约束项目调度问题广泛存在于现实的场景中，因为环境的不同或多或少会存在不同的约束，但是这约束，都是建立在經典模型的基础之上。經典资源约束项目调度问题主要存在两个约束，一个是资源约束，即工序的加工过程需要依赖资源，同时资源量是有限制的；一个是工序间的偏序关系约束，即工序之间存在一定的加工顺序。在这些约束下，通过合理的调度，最终实现调度目标的最优化。經典模型是此类问题最基本的抽象模型，在研究扩展模型之前有必要熟悉它。在經典资源约束项目调度问题模型之后，很多专家学者己经研宄出很多不同的扩展模型，本章后面将会进行介绍，首先来介绍經典问题模型。

2.1约束描述

經典的资源约束项目调度问题主要涉及两类约束，一类是工序之间存在的逻辑约束，另一类是资源有限造成的资源约束。目前有很多研究还讨论了其他类型的约束。本节只介绍經典的问题约束。

一般地，项目的工序及工序间的关系可以通过节点网络表示，此网络图是有向的，网络中的每一个节点表示一个工序，而箭线表示工序与工序间的加工逻辑顺序关系，如图2-1所示。图中最幵头的节点表示工序开始，最后的节点表示工序加工结束。通常在一个项目中，用没有任何意义的工序来表示项目的开始和结束，没有意义指的是不消耗资源与时间，它们的作用仅仅是串联项目中的实际工序，这些没有任何实际意义的工序被称为虚工序。如图2-1中的工序1与工序8，它们分别表示开始与结束虚工序。

2.2问题目标

一般情况下，项目在确定了项目的环境时就己经有了大致的项目目标。项目目标一般包含三个维度，分别是时间、费用、质量。

在RCPSP模型中，最基本的一类目标就是时间维度的，希望项目尽可能在短时间内完成或尽可能按制定的时间计划完成。但是项目的计划有时又需要牵扯到资源问题，即资源利用效率，此时资源又会引出费用问题，结果项目目标可能一方面希望降低费用，一方面希望提高项目收益，另一方面还要达到好的质量。

在实际研究中，目前研究最多的目标是基于时间维度的，即最小化项目最大完工时间。

3种特殊的资源约束项目调度问题.........19

3.1环境概念描述及分析...........19

3.1.1工位描述........20

4调度算法设计............26

4.1算法涉及概念...........26

4.2算法主要思想.............27

5实验及分析............42

5.1实验方案设计..........42

5实验及分析

为测试算法的正确性和可行性，并最终将其应用于实际项目中。本文釆用实际项目中的模型数据，将它们作为测试算例。在使用项目数据时，因为本算法设计了通用的输入数据格式，这使得实际项目中的数据结构必然与算法中的略有不同，这时就需要将实际数据格式转换为算法指定的格式，以便正确测试使用。在实验中将会采用不同的算例对算法进行测试，检验标准是算法的运行时长以及正确性。运行时长可以通过计时器计算，正确性可以通过两种方法验证。一种是将调度结果以甘特图的方式进行展示来验证。另一种是使用项目中己有的仿真平台进行验证。实验方案的设计及算例的详细描述将在本章内列出。在实验最后，本文将对实验结果进行分析，得出实验结论。下面将对实验进行逐步介绍。

5.1实验方案设计

由于该算法最终要应用于实际场景中，并且己经存在的仿真平台具备仿真数据的生成功能，但是仿真平台生成的数据不能与算法的输入数据格式相吻合，这就需要将其转换为算法输入的通用数据格式，即将仿真平台生成的数据转化成算法规定的数据格式。

本文选取三个测试实例，其中一个实例是基本的数据模型，即不会产生死锁情况，并且环境数据与工序数据量很平衡。另外两个实例是相对复杂的数据模型，其中的环境数据与工序数据不平衡，环境数据不能直接满足工序数据的可更新资源与工位需求。这两个实例的不同点是其中一个实例的工件阶段数不全相同。这么做的目的是为了测试某工件多次执行相同阶段的工序时，保证其可以被正常调度，即某工件可参与多个批次（每个批次包含不同的工件，批次之间连续调度）。

6总结与展望

6.1论文总结

本文为某企业的调度需求建立了一个特殊的资源约束项目调度问题模型SRCPSP，在该模型中，除了要满足资源约束、偏序关系约束外，还需要满足工位约束及资源之间的约束，这使得本文提出的模型比經典的资源约束项目调度问题更为复杂。为求解该模型，本文提出了一种基于优先规则的构造型启发式算法，釆用了串行调度生成方案和三种优先规则，并且考虑了调度过程中可能产生的死锁问题。本文的详细工作如下：

第一，本文根据实际项目的问题需求，确定要求解的问题为资源约束项目调度问题。然后根据相关文献，本文详细介绍了經典资源约束项目调度问题的模型，在该模型中，主要说明了逻辑约束、资源约束以及问题求解目标。同时还提到了目前针对该问题的扩展模型，以及常见的求解算法，如精确算法与启发式算法。

第二，结合实际问题，本文基于經典资源约束项目调度问题提出了一种特殊的资源约束项目调度问题模型，该问题模型在經典模型的基础上加入了工位约束、工序间的关系约束、可更新资源与不可更新资源的多种对应关系等。同时结合新的约束给出了新型问题模型的描述，并且确定了求解问题目标。

第三，为了求解新型问题模型，本文结合调度生成方案提出了一个基于优先规则的构造型启发式算法，该算法涉及到三种优先规则，采用串行调度生成方案。文中还介绍了实际问题中会出现的死锁问题，并提出了两种解锁方法。此外，为了更详细的说明算法流程，本文将算法按模块划分进行介绍，并给出了详细的算法思想。

最后，结合实际项目中的算例，对本文提出的算法及解锁规则进行实验，并证明提出的算法可以有效地构造出问题的解，其不仅可以节约大量的人力资源，而且可以得到更加优化的调度方案。

参考文献（略）