关键链管理法在资源受限多项目调度中的应用

吴超（安徽工业大学 管理科学与工程学院，安徽 马鞍山　243032）

关键链管理法在资源受限多项目调度中的应用

吴超
（安徽工业大学 管理科学与工程学院，安徽 马鞍山243032）

RCMPSP问题主要待解决的问题就是解决资源冲突的问题。关键链管理法主要是需找出项目中的制约整个项目的任务并将其组成一条关键链路，并设置各种缓冲区来保护关键链。本文用关键链管理法来解RCMPSP问题中，设计了基于关键链的调度算法。

资源受限；多项目；关键链；调度算法

2　基于关键链的资源受限多项目调度算法

本文采用文献［7］中为每个项目任务设置一个优先权系数的方法来作为调度依据。本文采用粒子群遗传算法来求得多项目中各个任务的优先权系数。

2.1算法设计

（1）编码。粒子群算法和遗传算法都是可以采用整数编码的。一个粒子或染色体就表示一个优先权列表。

（2）适应数函数。设为当前种群中第k个染色体或粒子，则g（uk）是适应度函数值，f（uk）是其 RCMPSP数学模型的目标函数值。

（3）粒子群遗传算法的操作。对于产生的初始种群，先采用粒子群的两个跟新公式来对种群进行操作。

惯性权重w体现出了粒子继承先前的速度的能力，为了平衡算法的全局搜索和局部搜索的能力，本文采用线性递减的惯性权重。对于GA算法的选择操作，本文采用轮盘赌选择；对于交叉操作，采用单点交叉。

2.2关键链和非关键链的识别

本文采用基于优先权列表和总时差相结合的方法来识别关键链。方法如下：先计算出每个项目中各个任务的总时差，然后将总时差的任务为0的任务选出，从左到右，按照任务编号从大到小依次排列上一步所选择出的任务，在遇到同时有两个以上的任务的任务总时差为0时，选择优先权系数大的任务作为关键链上的任务。

2.3基于关键链的资源受限多项目调度算法

本文采用并行调度方案产生项目的调度计划。根据进度区分三个任务集合：Cg成为已完成集合；Ag为执行集合；Dg为候选集合。具体算法如下：

输入：多项目调度网络G=（V，R）；

（1）初始化任务集合

（2）初始化时间段，tg=1

（3）检查执行集合中，是否有执行完成的任务，若是有，则将其移入完成集合中，并更新这两个任务集合

（4）更新资源信息，检查候选集合中是否有满足逻辑工序和资源约束的任务，若是有，将任务优先权系数大的任务调入执行集合中；

（5）重复第4步，直至候选集合中没有任务满足逻辑工序和资源约束，跟新集合和资源信息；

（6）判断执行集合和候选是否为空集，若是，则退出算法；

（7）tg=tg+1，转入第三步；

输出基于关键链的多项目调度方案G′=（V′，G′）。

3　实例验证

3.1关键链多项目调度

采用一个实例来验证该方法的正确性。本文采用的多项目是包含三个项目。三个项目共享三种可更新资源R1、R2和R3，可使用的总量分别为：20、20、20。多项目的各个任务基本情况如图3.1。首先采用上述算法求出该多项目各个任务的优先权列表：［0-13-26-1-14-18-27-3-31-28-29-4-19-5-30-17-2-6-22-16-33-20-7-23-29-24-32-34-8-9-21-36-10-25-35-37-22-12-38］。接着求出各项目关键链，第一个项目的关键链为：1-3-5-6-7-8-10-11-12，非关键链为：2、4、9。第二个项目的关键链为：13-14-18-19-22-23-24-25。非关键链为：15、17，、16-20、21。第三个项目的关键链为：26-27-28-31-33-34-36-37。非关键链为：29-32、30、35。使用调度算法生成进度计划，见表1。

表1　关键链多项目调度方案

如表1所示，共有8个时间段，其中资源R1的负荷在各个时间段较其他两个资源的负荷是较重的。因此，将R1设为鼓资源，并为其任务设置CCB。由于本文不涉及多项目的各个缓冲区尺寸的计算，计算方法不在此详述，图1为经过关键链管理法优化的多项目网络图。

3.2关键链多项目调度结果分析

从图1可以看出，该多项目在未使用关键链管理法时的项目完工工期为154天，而使用基于关键链的多项目调度算法而产生的调度方案的工期为101.87，加上左后的项目缓冲区18，17，所以，该多项目最后的工期为120.04。

4　结语

本文考虑了RCMPSP问题的约束条件，利用关键链管理法去解决RCMPSP问题。本文为每个任务设置优先权系数，并结合总时差来求出关键链。在生成进度计划方案时，采用并行调度和优先权列表相结合的方法来求出调度方案。

主要参考文献

［1］GOLDRATT E M.Critical Chain［M］.Great Barrington，MA：The North River Press，1997.

［2］刘士新，宋健海，唐加福.基于关键链的资源受限项目调度新方法［J］.自动化学报，2006，32（1）：60-66.

［3］李俊亭，王润孝，杨云涛.关键链多项目整体进度优化［J］.计算机集成制造系统，2011，17（8）：1772-1779.

［4］别黎，崔南方.关键链多项目管理中能力约束缓冲大小研究［J］.计算机集成制造系统，2011，17（7）：1534-1540.

图1　基于关键链的多项目调度网络计划图

［5］别黎，崔南方，赵雁，张小明，等.关键链多项目调度中分散式能力约束缓冲设置法［J］.计算机集成制造系统，2013，27（2）：148-152.

［6］刘士新，宋健海，唐加福.资源受限项目调度中缓冲区的设定方法［J］.系统工程学报，2006（4）：381-386.

［7］彭武良，王成恩.关键链项目调度模型及遗传算法求解［J］.系统工程学报，2010，25（1）：123-131.

10.3969/j.issn.1673-0194.2016.17.041

TP391

A

1673-0194（2016）17-0087-03

1引言

2016-05-19则研究了关键链在多项目的整体进度优化中作用。崔南方等则对关键链缓冲区的尺寸做了一系列的研究。刘士新等也对关键链的缓冲设定方法进行了研究。

关键链项目管理法（Critical Chain Project Management. CCPM）是约束理论（Theory of Constraints，TOC）在项目管理中的应用。关键链法考虑到了人的不良行为因素，消除了存在任务中的大量的安全时间，并设置缓冲区集中保护任务的进度。刘士新等提出了一种基于启发式规则的关键链调度方法。李俊亭