多项目资源均衡问题及其遗传算法_王为新.doc

46 计算机应用研究 2006年多项目资源均衡问题及其遗传算法*王为新, 李 原(西北工业大学现代设计与集成制造技术教育部重点实验室, 陕西西安 710072)摘 要: 针对单项目资源均衡优化在企业实际应用中的不足, 提出了多项目资源均衡优化的概念, 建立了多项目资源均衡问题模型。在此基础上给出一种遗传算法的求解方法,在算法中有效地利用了网络计划图的拓扑排序,减少了遗传操作过程中非法个体的修复计算量, 加快了算法的收敛速度。实例计算表明, 多项目资源均衡优化可以有效地实现整个企业资源的均衡配置, 遗传算法在求解该问题时具有可行性和高效性。关键词: 多项目; 资源均衡; 遗传算法; 拓扑排序中图法分类号:TP391 文献标识码:A 文章编号:1001 3695( 2006) 12 0046 02Multi ProjectResource Leveling and ItsGeneticA lgorithmWANG W ei xin,LIYuan(Key Laboratory of Contem porary D esign & Integrated Manufacturing T echnology, N orthwestern Polytechnical University, Xi an Shanxi 710072, China)Abstract: The resource leveling to single project can only realize the balance of resource in the project but can t in thewhole enterprise. This paper puts forward the concept ofmultiproject resource leveling and sets up the model of it. A genetic algo rithm is applied for solving multiproject resource leveling. U sing of topological sorting of newtork planning chart can decrease the computational complexity of repairing the invalid individuals in GA operations and accelerate the speed ofGA s convergence.Results showsmultiproject resource leveling can realize the balance ofwhole enterprise and the genetic algorithm isfeasible and efficient in solving the problem.Key words: M ultiProjec;t Resource Leveling; GeneticA lgorithm; Topological Sorting项目资源均衡问题是指在项目工期固定不变的条件下, 合理地调整项目网络计划中的某些工作, 使资源的需求量在项目工期范围内趋于均衡的过程。在制定项目网络计划的过程中, 仅考虑了工序之间的逻辑关系及工序的持续时间, 并没有考虑资源条件。因此, 有必要对初始网络计划进行资源均衡优化以保证项目顺利实施, 降低项目成本。在企业中通常存在着多个不同的项目, 并且这些项目在时序上往往具有并行关系, 对某些资源也存在着共同的需求。如果分别对多个项目进行独立的资源均衡优化, 只能优化项目内部的资源分布状况, 并不能在整个企业内实现项目资源需求量的均衡分布, 因此研究多项目资源均衡问题更具有现实意义。目前, 有许多专家和学者对单项目的资源均衡问题进行了研究 1 4 , 而对多项目资源均衡问题研究较少。本文针对多项目资源均衡优化问题, 建立了多项目资源均衡优化模型, 并给出了一种遗传算法的解决策略。1 多项目资源均衡问题建模为了使问题的求解具有可操作性, 给需要进行资源均衡优化的多个项目的双代号网络图首尾各添加一个辅助任务。辅助任务具有一定的持续时间, 但不消耗资源, 所有的起始辅助任务共用一个起始节点, 所有的结束辅助任务共用一个结束节收稿日期:2005 09 12; 修返日期:2005 10 18基金项目: 国家 863 /CIMS 主题资助项目 ( 2005AA411040) 点。这样就可以将多个双代号网络图连接成一个双代号网络图, 将这多个项目合并为一个大的项目, 从而使多项目资源均衡问题转换为单项目资源均衡问题。设有 m 个项目, A = 1, 2, , m 为项目集, 项目 i的任务集为 B = i1, i2, , in , 开始时间为 Si, 项目工期为 T i, 首尾添i加的辅助任务分别为 is 和 ie。合并后大项目的开始时间 S、项目工期 T 分别为S= m in S , 1im( 1) iT = m ax S i + T i - S, 1 i m ( 2) 在进行资源均衡优化的过程中, 需要对任务的开始时间进行调整。为保证所有项目的项目开始时间和项目工期在优化过程中不发生改变, 项目 i的辅助任务 is 和 ie 的持续时间分别为d i = Si - S( 3)sd ie = S+ T - (S i + T i )( 4) 这样就可以保证所有辅助任务均为关键任务 , 在均衡优化过程中其开始时间没有调整余地, 因而各个项目的开始时间和工期就不会发生改变。设合并后的大项目任务集为 C = 1, 2, n , 其中 n =n1 + n2 + + nm + 2m; 任务 j的最迟开始时间为 LSj, 实际开始时间为 s, 持续时间为 dj , 资源消耗量为 R j; Pj 为任务 j的紧前j任务集合; A t 为时刻 t正在进行的任务集合。多项目资源均衡问题可以用数学语言描述为1 Tm in 2 = R( t) - R 2( 5)T t= 1第 12期 王为新等: 多项目资源均衡问题及其遗传算法 47m ax si + d i sjLS j,iP j( 6)R( t) = R l( 7) l A t1 nR=R jd j( 8)T j = 1式 ( 5)定义的是目标函数, 即最小化资源方差; 式 ( 6)定义的是约束条件, 表示任务 j的开工时间必须满足其所有紧前任务的完工约束和最迟开始时间约束; 式 ( 7)表示 t时刻资源的消耗量; 式 ( 8)表示总工期内资源的平均耗用量。对于有多种资源需求均衡的情况, 由于项目在各时段对各种资源的需求量的数量级可能不同, 为使所有资源在数量上具有可比性, 需要对资源的需求量进行同一化处理; 然后采用层次分析法确定各种资源的相对权重, 将多资源均衡问题转换为单一资源均衡问题 5。2 多项目资源均衡问题的遗传算法设计2 1 适应度函数由于项目资源均衡的目标是最小化资源方差, 因此必须将原始目标函数转换为适应度函数以确保优秀个体具有大的适应度值。设 vk 是当前种群的第 k个染色体; f (vk )是适应度函数; 2k 是目标函数值, 即项目资源方差; 2m ax是当前种群中的最大目标函数值。转换方法如下:f( v ) = 2 - 2 +( 9) k max k其中 是一正数, 使用 的目的是使选择行为从适应度比例选择调整到纯随机选择。当染色体间适应度值的差距相对较大时, 为比例选择; 当区别相对较小时, 选择趋向于纯随机选择。2 2 染色体编码方案染色体采用任务的实际开工时间作为基因值, 每个基因对应于一个任务, 按照网络图的拓扑排序顺序将所有工序排列成一行, 形成染色体串。由式 ( 6)可知每个任务都必须在其所有的紧前任务结束之后才能进行, 因此, 如果任务按照任意顺序排列, 就有可能无法对式 ( 6)进行判定。在项目网络计划的拓扑排序序列中, 对任意任务开工时间有影响的任务均位于该任务之前, 所有受该任务影响的任务均排在其后, 因而就可以按照染色体中基因的顺序判断任务的合法性。获得项目网络计划拓扑排序的步骤如下:( 1)将网络图中的起始任务置入部分拓扑排序序列中。( 2)检查尚未进行排序的任务, 将紧前任务均位于部分拓扑序列中的任务置入部分拓扑排序序列中。( 3)重复步骤 ( 2) 直到所有任务均置入部分拓扑排序序列中, 得到网络图的拓扑排序。2 3 种群的初始化对个体的初始化按照染色体的顺序从左向右进行。任务 j的基因值, 即开始时间为 sj = FESj + random (LS j - FESj )( 10)其中 FESj为任务 j的实际最早开始时间, 其值为FESj = m ax si + d i , i Pj( 11) 由于整个过程是按照拓扑排序的顺序进行的, 任务 j紧前任务的开始时间 si 已经赋值, 因此, 式 ( 11) 不会产生非法计划安排。在确定初始种群的过程中, 如果初始种群的规模较小, 虽然可以提高遗传算法的运算速度, 却降低了群体的多样性, 容易陷入局部最优解; 而当初始种群的数量较大时, 又会使得算法的运行效率降低。对于初始种群的大小, 实际应用中只能依据经验或实验确定, 目前尚无理论上的指导, 一般建议的取值范围是 20 100 6。2 4 选择操作采用常用的比例选择策略 , 其基本原理是根据染色体的适应度值来确定个体选择概率, 各个体被选中的概率与其适应度值的大小成正比。设种群规模为 N, 个体 vk 的适应度值为 f ( vk ), 则个体 vk 被选择的概率 P (vk )为NP( vk ) = f( vk )f( vi )( 12)i= 1这种选择策略可以采用如下方法实现: 生成一个 0, 1内k- 1k的随机数 r, 若 P( v i ) r P( vi ) ( 13)i= 1i= 1则选择个体 vk。2 5 交叉操作采用单点交叉算子来完成交叉操作, 由于任务的开始时间依赖于其紧前任务的结束时间, 单纯的交叉操作会产生非法个体, 因此在交叉之后需要对个体进行合法性检验, 对于非法个体需要进行修正。对于交叉点左边的基因, 由于基因值未发生改变, 因而无须修正, 修正的过程为按照染色体中基因的顺序自交叉点向右逐一对基因进行检验:sjm ax si + d i ,iP j( 14) 当基因值满足上述条件时该基因值合理, 否则需要进行调整。调整方式按照式 ( 10)重新向该基因赋值。2 6 变异操作变异的过程比较简单, 对于一个给定的个体, 按照变异概率随机选择一个基因位, 然后对该基因的值按照式 ( 10)重新赋值。3 实例计算分析设某单位有三个在时序上存在并行关系的项目, 项目 1的开始时间为 0, 工期为 14; 项目 2 的开始时间为 1, 工期为 19; 项目 3的开始时间为 4, 工期为 16。在这三个项目的网络计划图首尾各添加一个辅助任务, 将它们合并为一个大的双代号网络图, 并对各任务进行重新编号, 如图 1所示。图中箭头线上方的数字表示相对应任务的资源消耗量, 箭头线下方的数字表示相对应任务的持续时间。合并后的网络图共有 27个节点、43个任务, 其中包括三个项目首尾部分用虚线表示的六个辅助任务。由式 ( 1)、式 ( 2)可得合并后项目的开始时间为 0, 工期为20; 由式 ( 3) 、式 ( 4)可得辅助任务 1 2, 1 3, 1 4, 23 27, 26 27,58 计算机应用研究 2006年25 27的持续时间分别为 0, 1, 4, 6, 0, 0。在本实例中选取种群规模为 100, 交叉概率为 0. 7, 变异概率为 0. 15, 最大迭代次数为 200, 分别对这三个项目进行多次试验, 多数情况下均能得到最优解。项目 1的最小资源方差为 7. 92, 项目 2的最小资源方差为 30. 48, 项目 3的最小资源方差为 2 84。优化结果对于单个项目来说均比较理想, 但是三个项目优化结果相叠加的资源方差结果为 187. 09。对这三个项目进行多项目均衡优化所取得的最优解为 65 09。优化后的各个任务开始时间如表 1所示。可见, 对企业内的项目进行多项目资源均衡优化, 与针对单个项目分别进行均衡优化相比, 能更好地配置整个企业内的资源。 (下转第 58页 ) 半监督归纳算法的检索效果要优于标准 SVM 和转导 SVM。经过八轮反馈, 在前 20个返回结果中, 标准 SVM 的准确度可以达到 51% , 转导 SVM 的准确度可以达到 51% , 而半监督归纳算法的准确度可以达到 63% 。3 3 使用 ILPP迭代学习算法的比较实验下面我们对采用 PCA算法、标准 LPP算法和 ILPP算法在降维空间中进行检索的实验效果作出比较。在图 2 中可以看到前 20个返回结果的准确度。分析实验结果, 作一个大致的比较: 在七次反馈后, 对于前 20个返回结果, PCA算法可以达到 48% 的准确度, LPP算法可以达到 50% 的准确度, ILPP算法可以达到 55% 的准确度。可以看出, ILPP算法的检索效果要优于 PCA算法和标准 LPP算法。4 总结LPP是近来国际上的一个研究热点, 相对于广泛应用的PCA 算法, LPP在应用于图像降维时可以获得更好的效果。基于 LPP的半监督归纳算法是在 LPP算法基础上, 结合了 SVM 算法的机制而提出的一种新型算法。该算法的优点在于可以使二分类之间的空白最大化并保留数据的局部信息, 因而可以提高检索的准确度。 ILPP算法是在 LPP算法的基础上, 采用迭代机制更新最近相邻图, 从而使之能更好地模仿流形局部结构 , 因此用于图像检索时可以获得更好的效果。实验结果显示 , 基于 LPP的半监督归纳算法的分类准确度明显优于 SVM 算法; ILPP算法在图像检索中的效果明显优于 PCA 算法, 比LPP的效果也要强一些。总之, 基于 LPP的半监督归纳算法和ILPP算法均是在 LPP算法基础上进行的一些优化研究, 目前这些研究取得了一些成果, 提高了 LPP算法的检索效率。参考文献: 1 X iaofeiH e, Partha N iyog.i Locality P reserving Projections C. Van couver: Advances in N eural Information P rocessing System s, 2003.291 299. 2 X iaofeiH e, O liver K ing, W eiY ing M a, et al. Learning a Sem anticSpace from U ser s Relevance Feedback for Im age Retrieval J. IEEE Trans. on Circuit and System s for V ideo T echnology, 2003, 13( 1): 39 48. 3Ke Lu,et al.Image RetrievalU sing D im ensiona lity Reduction C.CIS,2004. 775 781. 作者简介:鲁珂 ( 1974 ), 男, 讲师, 博士研究生, 主要研究方向为网络多媒体; 赵继东 ( 1976 ), 男, 讲师, 博士研究生, 主要研究方向为计算机网络; 叶娅兰 ( 1978 ), 女, 博士研究生, 主要研究方向为网络体系结构; 曾家智 ( 1939 ), 男, 教授, 博导, 主要研究方向为计算机网络与通信。(上接第 47页)4 结束语单项目资源均衡优化虽然能改善单个项目的资源分布状况, 但并不能实现整个企业内的资源均衡, 因而本文提出了多项目资源均衡优化的概念, 并建立了多项目资源均衡优化问题的模型。针对多项目资源均衡问题, 给出了一种遗传算法的求解方法。在算法中, 按照网络图的拓扑排列顺序, 将任务开始时间编码为染色体, 满足了任务间的逻辑约束关系, 能减少遗传操作