遗传算法的关键链项目调度基准计划问题研究

本资料包含pdf文件1个，下载需要1积分

The Benchmark Plan of Critical Chain Project SchedulingBased on the Genetic AlgorithmJIN Minli ，-.FENG Yuqiang(1.School of Management，Haerbin Institute of Technology，Haerbin 150001，China；2.Shenyang Ligong University，Shenyang 110159，China)Abstract：As a new project scheduling technology，critical chain method has been a re-search focus in project management theory and practice.For the purpose of applying criticalchain method in the large-scale projects，this paper studies the optimization models and theirsolutions for the critcal chain project schedule.This paper studies the benchmark plan of thecritical chain project scheduling problem and proposes a new genetic algorithm to solve thisproblem.And the effectiveness of this new genetic algorithm is verified by the simulationexperiments an d comparison。

Key words：benchmark plan；critical chain project scheduling；genetic algorithm；projectman agement关键链项目优化调度问题模型以资源约束项目调度问题模型为基础，因此求解资源约束项目调度问题是关键链项目管理的前提，设计合理的算法产生基准计划是关键链项目优化调度的基础。目前关于关键链项目调度的基准计划生成的算法主要有两大方面：即基于优先规则的启发式算法生成基准计划和基于智能优化算法生成基准计划。由于不同优先规则的启发式算法在求解关键链 项 目调 度 问题 时计算 结果 有 很 大差异 I4 。因此，对不同的关键链项 目调度问题需事前判断采用哪种优先规则 J↑几十年来，人们设计了各种智能仿生算法，这些算法均是模仿收稿 日期：2013-01-15作者简介：金敏力(1960-)，女，教授，研究方向：信息管理与信息系统，项 目管理沈 阳 理 工 大 学 学 报 第32卷自然规律而设计的问题求解模型，这些算法与经典的数学规划方法截然不同，试图通过模拟 自然生态系统的演化机制求解复杂问题，如遗传算法、模拟退火算法、群智能算法(如蚁群、鱼群、蜂群和鸟群等)、神经网络计算方法和人工免疫算法等。

这些智能算法为许多复杂的组合优化问题求解提供了切实可行的解决方案 J。资源约束项目调度问题本身是-类 NP-hard2-3]问题，求解困难，而资源约束关键链项目调度问题相比较于资源约束项目调度问题，模型更复杂，求解更困难，因此，利用智能优化算法进行优化求解是切实可行的方向。本文在前人研究的基础上，为单模式关键链项目调度问题的基准计划的产生设计-种遗传算法，并对算法的结构、编解码规则、遗传操作及初始种群的产生进行详细说明，通过仿真试验进行验证，并与最新的不同算法的计算结果进行比较。

1 模型构建生成基准计划是产生最终关键链的中间步骤，因为关键链的基准计划采用固定活动工期，不考虑缓冲区，只受可更新资源约束，因此可参照资源约束项 目调度问题建立基准计划的优化模型。

单执行模式资源受限项目调度问题(SRCPSP)，假设每-个任务只有-种执行模式；每-个任务占用-定的资源，而整个项目的总资源有限，资源量均为整数；项目中各个任务的开始时间和结束时间均为非负整数，且任务之间存在紧前关系；每个任务都有确定的执行时间，其值为非负整数；用-个有向无环图 G (，，A)(其中 代表任务节点的集合，A代表任务间前后约束的有向边的集合)来表示项目计划。该问题的优化目标是在资源约束条件下，考虑前后约束关系，实现项目持续时间最短。

SRCPSP问题可用以下数学语言描述：min sL (1)S.t. sLDf≤STj Vj∈Sf (2)∑r ≤Rk k1，2，3，， (3)lEAt≥0；Df≥0 i1，2，3，，n (4)式中：sri为活动i的开始时间；D 为活动 f的持续时间；S 为在活动f之后的所有活动的集合；ri 为活动 f需要资源 k的数量；A 为 t时刻正在执行的任务的集合； 为资源类型的数量。任务 1和任务n是虚工序，标识项目的开始时间和结束时间。目标是最携项 目的持续时间，即最携 。式(1)是最携项目时间，式(2)满足任务的时间约束，式(3)满足每种资源的约束，式(4)保证项目时间非负。

SRCPSP问题的求解，理论上可通过数学方法求得最优解，但由于资源约束项目调度问题属于 NP-hard问题，当任务数量和复杂度达到-定程度时，精确求解变得不现实。因此，启发式求解的方法适用于这种问题，这类方法给出相对简单的调度规则来寻找满意的解，而不-定是最优的解。文中提出的求解单执行模式项目调度问题的遗传算法，实质上包含两个部分：(a)根据项目的前后约束关系，产生-个可行的调度方案；(b)根据资源情况，逐个向后移动任务开始时间，最终确定满足资源约束条件的各个任务的开始时间。其中初始种群任务的优先权是根据随机产生的与任务总数相同的整数，根据串行调度的原理对每-个优先权情况下的任务进行调度，使其满足时间约束条件和资源约束条件，再采用遗传算法进化项目的调度。

2 遗传算法设计利用遗传算法求解关键链项目调度问题，是将每-个项目调度计划编码成-个染色体，通过交叉、变异、选择操作(由于选择操作采用最优保持和轮盘赌方法，染色体的性能始终向最优解的方向进化)，最终得到最优的调度计划或次优的调度计划 。传统的轮盘赌方法虽然能较好地选择出适应值较高的个体，但适应值较高的个体只是被选择的概率较高，而不能肯定被复制到下-代，因此为较好地保留局部最优的个体，采用最优保留的策略使进化持续不断地进行。基于最优保留和轮盘赌相结合的方式，文中的新遗传算法是在每-代种群中选择相对于种群规模的-定比例的最优个体直接进入到下-代中，这样既有利于最优个体的保留，也不破坏种群的多样性，更利于产生更优秀的个体。通过父代和子代相互竞争的策略，在选择过程中，子代与父代有相同的权利在轮第2期 金敏力等：遗传算法的关键链项目调度基准计划问题研究 45盘赌过程中被复制到下-代。文中采用的求解单执行模式项目调度问题遗传算法的流程为：首先设置算法参数，定义-个结构数组，用于存放项目信息，包括紧前任务关系、紧后任务关系、资源占用量、任务优先权、任务工期等；然后计算每个任务的内度，并存放到结构数组中；再基于优先权生成初始种群，进入到循环体中，进行交叉、变异、选择操作；最后对个体进行选择，直到得到满意的结果为止。

2.1 制定编码解码规则本文采用基于优先权的编码规则，再利用串行调度进行解码。基于优先权的编码是用位置表示-个活动的ID，基因的值用来表示活动的优先权，有较高优先权的任务优先进入计划。基因的值是[1，n]之间惟-的整数，其中n与任务数相同，且每个任务的优先权都不相同。编码方法是通过基因位置确定任务的ID，通过基因值确定任务的优先权。

编码过程的关键在于拓扑排序，拓扑排序对于-个给定的有向图G( ，A)，-个拓扑排序是-个所有节点的线性次序，对于任意有向边(U，1，)∈A，U在该次序中先于 v出现。每-个拓扑排序应对应与项目任务数-样多的位置，从拓扑排序第-个位置开始，从左到右，依次添加拓扑排序，对应于某个位置，可能有多个任务进行竞争，具有最高优先权的任务赢得这个位置。用向量PS存储不完全拓扑排序，初始化PS1～所有任务分为三种状态：已排序任务、合格任务和自由任务。确定了合格任务，就可根据每个合格任务的优先权确定进入拓扑排序的任务，再更新合格任务集合，不断循环，直到所有任务都进入拓扑排序为止。

合格任务的确定可通过内度的概念得以解决，用Din表示任务的内度，其大型是这个任务的父任务的数量。再引入割集的概念，其实质是某- 时间节点符合条件的边的集合，用 CUT表示。

cur，表示 t时刻的割集，PS 表示 t时刻的拓扑排序， 表示所有任务的集合，任务f∈PS ，任务 ∈- P ，，贝0 cur，(f， )I i∈PS，，-，∈V-P ，表示时t刻的割集。对于给定的任务J∈V-PS ，如割集中传人任务 的边的数量等于内度，那么这个任务是合格任务。如图 1所示，给出-个项目的网络图作为例子。

图 1 部分拓tl't序、割集和合格任务当时刻为4时，部分拓扑排序 1，3，2，6，此刻的割集为 c (6，10)，(3，7)，(1，4)，(1，5)。由于任务 10的内度为2，而仅有-条属于割集的边传人该任务，因此任务 10不是合格任务，而是自由任务。由于任务4、5、7的内度均为1，而传人这些任务的边均在割集中，因此任务4、5、7均是合格任务。以此类推，可得到这个项目在该优先权下的拓扑排序，如图2所示。

图 2 完整拓扑排序由于每-个拓扑排序无法反映出个体的优劣，因此需要采用解码来衡量个体的情况。文中采用串行调度的方式对每-个染色体进行解码。

(f)的最早可能开始时间，再计算这个时刻所有资源的占用量，如果资源剩余量满足任务的 要求，则可确定任务的开始时间，否则时间往后移动-个单位，再判断资源的剩余量是否满足要求；随着任务的完工，可更新资源会被释放，因此必然存在某个时刻的资源是可行的。按照这种方法确定每-个任务的开始时间和结束时间，其中最后任务的结束时间即为整个项目的时间。

2.2 遗传算子与适值函数遗传算法主要通过遗传算子实现向目标解方向进化，遗传算子主要有三部分组成：交叉算子、变异算子和选择算子；其中交叉算子实现在广度空间上的搜索，变异算子有利于深度搜索，选择算子使解向更好的方向发展。

(1)交叉算子设计本文的编码实际上是[1，n]的整数排列，这个排列发生改变，个体也随之改变，理论上据这些整数的所有排列方式就可计算出所有的可行解。用沈 阳 理 工 大 学 学 报 第32卷杂交方法随机地从父代 1中选择若干个基 因位置，将这些基因的值遗传给子代中相应的位置，子父代1子代父代2代中空缺的位置由父代 2由左到右依次填补完整，如图3所示。

4 7 1 8 2 1O 6 3 12 I 5 l1 9I I I I I I3 7 1 8 2 10 4 l1 l2 I 6 5 9～ - 7f 2 l 3 7 9 8 1O 4 11 l 6 l2 5图 3 交叉操作执行过程(2)变异算子设计本文变异算子的主要目的是搜索当前解的邻域来寻找更好的解，既深度搜索。随机在父代中父代子找到两个位置，交换这两个位置的基因值，产生新的个体，如图4所示。

图4 变异操作执行过程(3)选择算子设计通过解码，计算出每个个体对应的项 目的持续时间，最后-个活动的结束时间就是目标值，显然这个 目标值越小越好，属于最携问题，但在遗传算法中，必须将原始目标值最携问题转化成适应值，以确保优秀个体具有大的适应值。

设f为当前种群第f个个体，g(f)为适应值函数，(i)为第 f个个体的目标值(即项目持续时间)，2和 分别为当前种群的最大目标值和最小目标值～目标值转化成适应值的转换公式为 (5)式中，.是属于[0，1]的正实数，文中取0.5。使用r的目的是：(1)防止式中分母为零的现象出现；(2)如果染色体间适应值的差距相对比较大，则采用适应值比例选择；如果区别相对较小，则选择在相互竞争的染色体中进行纯随机选择。

2.3 初始种群的产生算法初始种群由两部分组成：-部分根据优先级规则产生，保证种群有较好的基础；另-部分随机产生，保证初始种群 的多样性。文 中采用MINSLK、MINLFT LST GRU、W RUP GRPW GRD、SRD这几种常用的优先级规则产生的个体作为初始种群的-部分。执行选择操作过程中，选择最优保持的策略，最后结果不会比基于优先级规则的算法所求得的结果差。

3 算例仿真与分析3.1 算例确定与参数设计选择选择标准问题库 PSPLIB中的单执行模式项目调度问题的J30、J60两组实例，用MATLAB软件进行遗传算法的设计。J30和 J60均有 480个问题实例，J30中的每个实例包括 32个活动，其中活动 1和活动 32是虚活动；J60中的每个实例包括62个活动，其中活动 1和活动62是虚活动，每个项 目实例需要 4种可更新资源。

首先对实验参数进行分析，确定算法的最优参数设置。具体参数设置为：种群规模分别取值1O、20和40；迭代次数分别为 100、50和 25；交叉概率分别为0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8和0.9；变异概率取值分别为0.01、0.03、0.05、0.07、0.09、0.1、0.2、0.3和 0.4。算法的初始种群由两部分产生，但在确定参数过程中，为测试算法的有效性，通过尽量扩大解的空间方式更清楚地分辨出在不同参数设置情况下算法的有效性。

计算过程中初始种群均随机产生，随机产生初始种群存在的不确定性，通过对同-个项目实例测试多次，取其均值的方法予以消除。测试实例选j3011.sm，为了测试的有效性，使种群规模保持第2期 金敏力等：遗传算法的关键链项目调度基准计划问题研究 47- 定，每个测试最终生成的个体皆为 1000个，以项目调度时间最短作为选择标准，选择最优个体作为比较对象。

实验结果表明：在总个体数相同情况下，种群规模与迭代次数对求解效果的影响较小；当 P ∈0，7，0，8，0，9、P ∈0，2，0，3，0，4的组合时，求解效果最好。因此选择参数如下：种群规模为40，迭代次数为25，交叉概率(P )为0.7，变异概率(P )为 0.2。

3.2 仿真结果与分析实验中，对于标准问题 J30，根据各个解距离最优解的平均偏差 avdew、最大偏差 maxdev、最优解比例 optimal、可行解比率feasible四个指标来统计算法的有效性，统计结果如表 1所示。对于标准问题J60，通过各个解与当前最好解的平均偏差 avdev、最大偏差 maxdev、最优解 比例 opti。

ma l、可行解比率feasible四个指标来统计算法的有效性，统计结果如表2所示。算例中比较的对象是基于2008年的最好结果。值得指出的是，对于J30这组项目实例的最优解已通过精确算法得到；而 J60目前还没有获得全部的最优解，但通过大量的算法给出了最大下界，还给出了经过多种算法获得的当前最好的解。

表 1 J30.sm的测试性能表从上述计算结果可以看出，本文所提出的遗传算法是有效的，在解决关键链项目调度的基准计划方面具有较高的准确性和精确度及可行性。

Kolisch和Drexl的自适应搜索算法、Baar等人的禁忌搜索算法、Haxtmann的遗传算法和Bouleimen和 Lecocq的模 拟退 火算法 是求 解SRCPSP较成功的几种启发式算法 J。为进-步分析本文所设计的算法的求解效果，将本文算法与这些算法进行比较，比较结果如表3所示。

表 3 不同算法结果比较表由表3可见，与前人的算法相比，本算法的性能也较好。注意：本文的比较对象是近年的最新结果，其中有些最好解就是由上述算法得到的。

4 结束语本文对单执行模式资源受限项 目的关键链调度问题基准计划的产生设计了-种遗传算法，该方法在选择操作上采用最优保持和轮盘赌方法混合的方式，通过算法的结构、编码解码规则、遗传操作等产生初始种群，并进行多次迭代得到最优调度。通过对 PSPLIB中 J30和 J60两组实例的仿真计算验证了该算法的有效性，并与目前比较流行的几种算法 比较，验证了该算法的有效性。