基于遗传算法的多模式资源约束项目调度问题研究-王为新

#72#计算机应用研究2007年基于遗传算法的多模式资源约束项目调度问题研究*王为新,李原,张开富(西北工业大学现代设计与集成制造技术教育部重点实验室,陕西西安710072)摘要:为解决多模式资源约束项目调度问题,提出了一种混合遗传算法的求解方法。该算法采用二维编码方法来表示问题的解,基因的值表示任务的优先权和执行模式,每条染色体对应一个满足逻辑关系约束的可行任务排序,根据染色体所对应的任务调度顺序和执行模式序列可以获得一个满足资源约束的项目调度方案。应用该编码方法进行选择、交叉和变异等遗传操作,能够使搜索范围遍及整个问题解空间。实际应用表明,该算法能快速求得问题的最优解或近似最优解。关键词:多模式;资源约束;项目调度;遗传算法中图法分类号:TP391文献标识码:A文章编号:1001-3695(2007)01-0072-03ResearchofMult-iModeResource-ConstrainedProjectSchedulingProblemBasedonGeneticAlgorithmWANGWe-ixin,LIYuan,ZHANGKa-ifu(StateKeyLaboratoryofContemporaryDesign&IntegratedManufacturingTechnologyforMinistryofEducation,NorthwesternPolytechnicalUniversity,Xi.anShanxi710072,China)Abstract:ThispaperdevelopesahybridgeneticalgorithmforsolvingMulti-ModeResource-ConstrainedProjectSchedulingProblem(MRCPSP).Theobjectiveistodetermineamodeandastarttmieforeachactivitysuchthatallconstraintsareobservedandtheprojectdurationisminimized.Atwo-dmiensionalencodingisusedinthealgorithm.Eachgenerepresentsthepriorityandexecutionmodeofanactivity.Afeasibleactivitysortmeetingprecedenceconstraintscanbegeneratedfromagivenchromosome.Itcanconstructaschedulingmeetingresourceconstraintsbyselectingtheactivitiesandtheirexecutionmodeinorderoftheirappearanceintheactivitysort.Usingtheencodingthealgorithmcangetallpossibleschedulingsthroughgeneticoperators:selection,crossover,mutation.Resultsshowthatthealgorithmcangetnear-optmialsolutionsofMRCPSPrapidly.Keywords:Mult-iMode;Resource-Constrained;ProjectScheduling;GeneticAlgorithm资源约束项目调度问题(RCPSP)指的是一类在满足项目资源约束和任务前后约束的条件下合理安排工程各作业的开始时间,以最小化项目总工期的调度问题。在传统的RCPSP中,每项任务的工期和资源需求量都是固定的,称为单模式资源约束项目调度问题(SRCPSP)。多模式资源约束项目调度问题(MRCPSP)是SRCPSP的扩展,每项任务在执行时有多种工期和资源需求量的组合形式可供选择,与SRCPSP相比MRCP-SP更接近工程实际。MRCPSP与SRCPSP一样也属于NP-hard问题,近年来该问题吸引着越来越多的学者对其进行研究,并提出了各种各样的优化方法,概括起来可分为以下三类:以分支定界法为代表的精确类算法[1,2];基于优先规则的启发式算法[3,4];以遗传算法和模拟退火算法为代表的智能优化算法[5~7]。精确算法能求得小规模问题的最优解,但对大规模问题无能为力;启发式算法和智能优化算法不能保证求得问题的最优解,但在解决大规模问题时能在求解质量和求解效率上获得一种较好的平衡。本文针对MRCPSP提出了一种混合遗传算法的解决策略。1问题描述在进行问题描述之前,先作如下假设:①任务一旦开始必收稿日期:2005-08-14;修返日期:2005-11-24基金项目:国家/863/CIMS0计划资助项目(2005AA411040)须进行到完工,中途不得中断,不得改变执行模式;②资源均为可更新资源,即资源能力在项目工期范围内为均匀分布;③每项任务所需资源量均小于资源的最大供应量。设项目工期为T;项目共包含n个任务,A={1,2,,,n}为项目的任务集,A中第1个和第n个任务是为了描述问题方便而增设的虚拟任务,其作用是标记项目开始时间和结束时间,只有一种模式,持续时间和资源消耗量均为0;任务j共有Mj种模式,mj是任务j所采用的模式,在该模式下对第k种资源的消耗量为rmjk,持续时间为djm;任务j的开始时间为sj;At为jj时刻t正在进行的任务集合;Pj为任务j的紧前任务集合;Rk是资源k的总量;K是不同资源类型的数量,则问题可以用数学语言描述如下:minT=sn-s1(1)s.t.s+d[s,PiIP(2)iimijjErimk[Rk,k=1,2,,,K(3)iIAti式(1)定义的是目标函数,即最小化项目工期;式(2)定义的是紧前约束关系,表示任务j必须在其所有紧前任务均已完工的情况下才能开始进行;式(3)定义的是资源约束关系,即在时刻t进行的所有任务对资源k的消耗量不能超过其限制的数量。2染色体编码和解码任务之间存在着紧前约束关系,任意的排序可能产生不可行的进行次序,如何有效地产生能够处理前后约束的编码是遗传算法解决该问题的关键。本文提出一种基于优先权的编码方案来解决该问题。定义设有任务链表V=(i1,i2,,,in),链表中的元素为各任务的编号,元素的下标为元素所对应任务在链表中的位置,如果V中各任务的排列顺序满足紧前约束关系,即如果iIPj,任务i在V中的位置处于任务j的前面,则称V为紧前关系相容链表。在算法中采用二维编码方法来表示MRCPSP的解,该编码方法如图1所示。染色体表示的二维结构由任务优先权和任务执行模式两行组成:第一行中pi的值用来表示任务i的优先权,是区间[0,1]内的一个实数,数值越大则优先权越高;第二行中mi是区间[1,Mi]内的一个整数,用来表示任务i的执行模式。p1m1p2m2,,pimi,,pnmn图1解的编码方法采用基于优先权的编码方法可以表示给定项目的所有可能紧前关系相容链表,并且任何染色体总是对应着一个紧前关系相容链表。染色体的解码过程分为两步:(1)根据染色体所表达的任务优先权和执行模式信息生成紧前关系相容链表和执行模式序列。该过程按照一次通过方式进行:从左到右一次确定一项任务在紧前关系相容链表中的位置以及该任务的执行模式。该过程每一次迭代中的所有任务均处于下列三种状态之一:①已排序任务。已经放入紧前关系相容链表中的任务。②合格任务。紧前任务都是已排序任务的任务。③自由任务。所有其他任务。令Vj=[i1,i2,,,ij](j[n)表示包含前j个任务的部分紧前关系相容链表;Mj=[mi1,mi2,,,mij](j[n)表示与部分紧前关系相容链表Vj相对应的部分执行模式序列。生成紧前关系相容链表以及执行模式序列的过程步骤如下:①i1←1,←j1,转入③。②当j[n时,转入③;否则,转入⑤。③检查所有未排序任务,将紧前任务全部位于Vj中的任务放入合格任务集S,转入④。④将合格任务集S中具有最高优先权的任务放入部分紧前关系相容链表Vj的ij之后形成新的部分紧前关系相容链表Vj+1,并将该任务的执行模式放入部分执行模式序列Mj的mij之后,形成新的部分执行模式序列Mj+1,j←j+1,转入②。⑤返回完整的紧前关系相容链表和执行模式序列,结束。(2)根据步骤(1)所生成的紧前关系相容链表和执行模式序列,按照串行调度方案生成一可行计划。令pst表示项目的开始时间,S=(si,si,,,si)表示步骤(1)所得到的紧前关系12n相容链表中相应任务的开始时间,所对应的串行调度方案的调度过程步骤如下:①si←pst,j←2,转入②。1②当j[n时,转入③;否则,转入⑥。③sij=max{sj+djmj}(jIPij),转入④。④判断活动ij按其执行模式mi进行期间是否存在资源冲j突,如果存在资源冲突则转入⑤;否则j←j+1,转入②。⑤si←si+1,转入④。jj⑥返回所有任务的最早开始时间,结束。3适应度函数对染色体进行解码得到各任务的开始时间,利用式(1)可得到项目持续时间,即目标函数值。由于MRCPSP的目标是最小化项目工期,因此必须将原始目标函数转换为适应度函数,以确保优秀个体具有大的适应度值。设vk是当前种群的第k个染色体,f(vk)是适应度函数,Tk是目标函数值,即项目持续时间,Tmax是当前种群中的最大目标函数值。转换方法如下:f(vk)=Tmax-T(vk)+C(4)其中C是一正整数,使用C的目的是使选择行为从适应度比例选择调整到纯随第1期王为新等:基于遗传算法的多模式资源约束项目调度问题研究#73#机选择。当染色体间适应度值的差距相对较大时,为比例选择;当区别相对较小时,则选择趋向于纯随机选择。4遗传操作411种群的初始化按照任务ID对项目任务进行升序排列,根据生成的排列顺序随机地为各任务指定一执行模式,并生成区间[0,1]内的一随机实数序列作为各任务的优先权,从而构成一条染色体。按照该方法生成指定数目的个体构成初始种群。412选择操作采用常用的比例选择策略,其基本原理是根据染色体的适应度值来确定个体选择概率,各个体被选中的概率与其适应度值的大小成正比。设种群规模为N,个体vk的适应度值为f(vk),则个体vk被选择的概率P(vk)为NP(vk)=f(vk)Ef(vi)(5)i=1这种选择策略可以采用如下方法实现:先生成一个[0,1]内的随机数r,若P(v1)+P(v2)+,+P(vk-1)r[P(v1)+P(v2)+,+P(vk)则选择个体vk。由于选择、交叉和变异等遗传操作的随机性,它们有可能破坏掉当前种群中适应度最好的个体,从而影响算法的收敛性。为了保证每一代的优良个体不被破坏,采用最优个体保留策略[8]。413交叉操作采用单点交叉算子来完成交叉操作。记参与交叉的两个父代个体为A和B,随机生成一整数q,1qn,由A和B在q点进行交叉产生的两个子代个体为Ac和Bc。子代个体Ac的前q个任务的优先权和执行模式继承于A,即pAic=pAi,mAic=mAi,i=1,2,,,qAc在i=q+1,q+2,,,n位置上的任务优先权和执行模式来自于B,即pAic=pBi,mAic=mBi,i=q+1,q+2,,,n子代个体Bc的形成过程与Ac相似,即pBii=1,2,,,qBc=mBii=1,2,,,qpBc=mipAii=q+1,q+2,,,nimAii=q+1,q+2,,,n414变异操作采用单重均匀变异算子来完成对染色体的变异操作,变异算子依变异概率pm对染色体A中的每个分量进行变异操作,得到子代个体Ac。设染色体A的第q个基因发生变异,则子代个体Ac各基因所表示的优先权和执行模式分别为rfi=qrIi=qpAic=mAic=pAiiXqmAiiXq其中rf为区间[0,1]内的随机实数,rI为区间[1,Mq]内的随机整数。5实例计算分析为了证明本算法的有效性,设计了一项目实例,该项目的网络计划图如图2所示,图