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

金敏力，冯玉强

(1.哈尔滨工业大学 管理学院，黑龙江 哈尔滨 150001;2.沈阳理工大学 教务处，辽宁 沈阳 110159)

关键链项目优化调度问题模型以资源约束项目调度问题模型为基础，因此求解资源约束项目调度问题是关键链项目管理的前提，设计合理的算法产生基准计划是关键链项目优化调度的基础［1］。目前关于关键链项目调度的基准计划生成的算法主要有两大方面:即基于优先规则的启发式算法生成基准计划和基于智能优化算法生成基准计划。由于不同优先规则的启发式算法在求解关键链项目调度问题时计算结果有很大差异［2－4］。因此，对不同的关键链项目调度问题需事前判断采用哪种优先规则［5］。近几十年来，人们设计了各种智能仿生算法，这些算法均是模仿自然规律而设计的问题求解模型，这些算法与经典的数学规划方法截然不同，试图通过模拟自然生态系统的演化机制求解复杂问题，如遗传算法、模拟退火算法、群智能算法(如蚁群、鱼群、蜂群和鸟群等)、神经网络计算方法和人工免疫算法等。这些智能算法为许多复杂的组合优化问题求解提供了切实可行的解决方案［6］。资源约束项目调度问题本身是一类 NP－hard［2－3］问题，求解困难，而资源约束关键链项目调度问题相比较于资源约束项目调度问题，模型更复杂，求解更困难，因此，利用智能优化算法进行优化求解是切实可行的方向。本文在前人研究的基础上，为单模式关键链项目调度问题的基准计划的产生设计一种遗传算法，并对算法的结构、编解码规则、遗传操作及初始种群的产生进行详细说明，通过仿真试验进行验证，并与最新的不同算法的计算结果进行比较。

1 模型构建

生成基准计划是产生最终关键链的中间步骤，因为关键链的基准计划采用固定活动工期，不考虑缓冲区，只受可更新资源约束，因此可参照资源约束项目调度问题建立基准计划的优化模型。单执行模式资源受限项目调度问题(SRCPSP)，假设每一个任务只有一种执行模式;每一个任务占用一定的资源，而整个项目的总资源有限，资源量均为整数;项目中各个任务的开始时间和结束时间均为非负整数，且任务之间存在紧前关系;每个任务都有确定的执行时间，其值为非负整数;用一个有向无环图G=(V，A)(其中V代表任务节点的集合，A代表任务间前后约束的有向边的集合)来表示项目计划。该问题的优化目标是在资源约束条件下，考虑前后约束关系，实现项目持续时间最短。

SRCPSP问题可用以下数学语言描述:

式中:STi为活动i的开始时间;Di为活动i的持续时间;Si为在活动i之后的所有活动的集合;rik为活动i需要资源k的数量;At为t时刻正在执行的任务的集合;K为资源类型的数量。任务1和任务n是虚工序，标识项目的开始时间和结束时间。目标是最小化项目的持续时间，即最小化STn。式(1)是最小化项目时间，式(2)满足任务的时间约束，式(3)满足每种资源的约束，式(4)保证项目时间非负。

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

2 遗传算法设计

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

2.1 制定编码解码规则

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

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

合格任务的确定可通过内度的概念得以解决，用Din表示任务的内度，其大小就是这个任务的父任务的数量。再引入割集的概念，其实质是某一时间节点符合条件的边的集合，用CUT表示。CUTi表示t时刻的割集，PSt表示t时刻的拓扑排序，V表示所有任务的集合，任务i∈PSt，任务j∈V － PSt，则 CUTt={(i，j)|i∈PSt，j∈V － PSt}表示时t刻的割集。对于给定的任务j∈V－PSt，如割集中传入任务j的边的数量等于内度，那么这个任务j是合格任务。如图1所示，给出一个项目的网络图作为例子。

图1 部分拓扑排序、割集和合格任务

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

图2 完整拓扑排序

由于每一个拓扑排序无法反映出个体的优劣，因此需要采用解码来衡量个体的情况。文中采用串行调度的方式对每一个染色体进行解码。首先根据任务之间的紧前关系约束，确定任务j=PS(i)的最早可能开始时间，再计算这个时刻所有资源的占用量，如果资源剩余量满足任务的j要求，则可确定任务j的开始时间，否则时间往后移动一个单位，再判断资源的剩余量是否满足要求;随着任务的完工，可更新资源会被释放，因此必然存在某个时刻的资源是可行的。按照这种方法确定每一个任务的开始时间和结束时间，其中最后任务的结束时间即为整个项目的时间。

2.2 遗传算子与适值函数

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

(1)交叉算子设计

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

图3 交叉操作执行过程

(2)变异算子设计

本文变异算子的主要目的是搜索当前解的邻域来寻找更好的解，既深度搜索。随机在父代中找到两个位置，交换这两个位置的基因值，产生新的个体，如图4所示。

图4 变异操作执行过程

(3)选择算子设计

通过解码，计算出每个个体对应的项目的持续时间，最后一个活动的结束时间就是目标值，显然这个目标值越小越好，属于最小化问题，但在遗传算法中，必须将原始目标值最小化问题转化成适应值，以确保优秀个体具有大的适应值。

设i为当前种群第i个个体，g(i)为适应值函数，f(i)为第i个个体的目标值(即项目持续时间)，f2和f1分别为当前种群的最大目标值和最小目标值。将目标值转化成适应值的转换公式为

式中r是属于［0，1］的正实数，文中取0.5。使用r的目的是:(1)防止式中分母为零的现象出现;(2)如果染色体间适应值的差距相对比较大，则采用适应值比例选择;如果区别相对较小，则选择在相互竞争的染色体中进行纯随机选择。

2.3 初始种群的产生

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

3 算例仿真与分析

3.1 算例确定与参数设计选择

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

首先对实验参数进行分析，确定算法的最优参数设置。具体参数设置为:种群规模分别取值10、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。算法的初始种群由两部分产生，但在确定参数过程中，为测试算法的有效性，通过尽量扩大解的空间方式更清楚地分辨出在不同参数设置情况下算法的有效性。计算过程中初始种群均随机产生，随机产生初始种群存在的不确定性，通过对同一个项目实例测试多次，取其均值的方法予以消除。测试实例选j301_1.sm，为了测试的有效性，使种群规模保持一定，每个测试最终生成的个体皆为1000个，以项目调度时间最短作为选择标准，选择最优个体作为比较对象。

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

3.2 仿真结果与分析

实验中，对于标准问题J30，根据各个解距离最优解的平均偏差avdew、最大偏差maxdev、最优解比例optimal、可行解比率feasible四个指标来统计算法的有效性，统计结果如表1所示。对于标准问题J60，通过各个解与当前最好解的平均偏差avdev、最大偏差 maxdev、最优解比例 optimal、可行解比率feasible四个指标来统计算法的有效性，统计结果如表2所示。算例中比较的对象是基于2008年的最好结果。值得指出的是，对于J30这组项目实例的最优解已通过精确算法得到;而J60目前还没有获得全部的最优解，但通过大量的算法给出了最大下界，还给出了经过多种算法获得的当前最好的解。

表1 J30.sm的测试性能表

表2 J60.sm的测试性能

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

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

表3 不同算法结果比较表

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

4 结束语

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

［1］彭武良，王承恩.关键链项目调度模型及遗传算法求解［J］.系统工程学报，2010，25(1):123 －131.

［2］Bartusch M，Möhring R H，Radermacher F J.Scheduling Project Networks with Resource Constraints and Time Windows［J］.Annals of Operation Research，1988，16:201 －240.

［3］Blazewicz J，Lenstra J K，Rinnooy Kan A H G.Scheduling Subject to Resource Constraints:Classification and Complexity［J］.Discrete Applied Mathematics，1983，5:11－24.

［4］Pate－Cornell M E，Dillon R L.Success Factors and Future Challenges in the Management of Faster Bettercheaper Projects:Lessons Learned from NASA［J］.IEEE Transactions on Engineering Management，2008，48(1):25－35.

［5］Wuliang Peng，Zhongliang Zhang，Zhaofu Tian. The Scheduling of Project Time，Cost and Product Quality.Proceeding of the 2010 Chinese Control and Decision Conference［C］.Xuzhou，China，2010:150 －155.

［6］刘士新.项目优化调度理论与方法［M］.北京:机械工业出版社，2007:1－53.

［7］Hartmann S.Project Scheduling with Multiple Modes:A Genetic Algorithm［J］.Annals of Operations Research，2001(102):111 －135.