大型工程项目任务多目标优化调度方法

ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　２０１０，４６（２４）　２１７　大型工程项目任务多目标优化调度方法　曾　强　，杨　育　，王小磊　，赵　川　ＺＥＮＧ　Ｑｉａｎｇ　一，ＹＡＮＧ　Ｙｕ　，ＷＡＮＧ　Ｘｉａｏ—ｌｅｉ　，ＺＨＡＯ　Ｃｈｕａｎ　１．重庆大学机械传动国家重点实验室，重庆４０００３０　２．河南理工大学，河南焦作４５４０００　１．Ｓｔａｔｅ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｍｅｃｈａｎｉｃａｌ　Ｔｒａｎｓｍｉｓｓｉｏｎｓ，Ｃｈｏｎｇｑｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ　４０００３０，Ｃｈｉｎａ　２．Ｈｅｎａｎ　Ｐｏｌｙｔｅｃｈｎｉｃ　Ｕｎｉｖｅｒｓｉｙｔ，Ｊｉａｏｚｕｏ，Ｈｅｎａｎ　４５４０００，Ｃｈｉｎａ　Ｅ—ｍａｉｌ：ｚｅｎｇｑｉａｎｇ＠ｃｑｕ．ｅｄｕ．ｃｎ　ＺＥＮＧ　Ｑｉａｎｇ，ＹＡＮＧ　Ｙｕ。ＷＡＮＧ　Ｘｉａｏ—ｌｅｉ，ｅｔ　ａ１．Ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｍｅｔｈｏｄ　ｆｏｒ　ｔａｓｋｓ　ｓｃｈｅｄｕｌｉｎｇ　ｏｆ　ｌａｒｇｅ－ｓｃａｌｅ　ｅｎｇｉｎｅｅｒｉｎｇ　ｐｒｏｊｅｃｔ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１０．４６（２４）：２１７－２２１．　Ａｂｓｔｒａｃｔ：Ａ　ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｍｅｔｈｏｄ　ｆｏｒ　ｔａｓｋｓ　ｓｃｈｅｄｕｌｉｎｇ　ｏｆ　ｌａｒｇｅ－ｓｃａｌｅ　ｅｎｇｉｎｅｅｒｉｎｇ　ｐｒｏｊｅｃｔ　ｉｓ　ｐｒｏｐｏｓｅｄ．Ｉｎ　ｔｈｅ　ｍｅｔｈｏｄ，ａ　ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　ｐｒｏｇｒａｍｍｉｎｇ　ｍｏｄｅｌ　ｉｓ　ｅｓｔａｂｌｉｓｈｅｄ　ｗｉｔｈ　ｔｈｅ　ｏｂｊｅｃｔｉｖｅ　ｔｏ　ｍｉｎｉｍｉｚｅ　ｔｈｅ　ｃｏｍｐｌｅｔｉｏｎ　ｔｉｍｅ　ａｎｄ　ｔｏｔａｌ　ｅｘ—　ｐｅｎｓｅｓ　ａｎｄ　ｔｏ　ｍａｘｉｍｉｚｅ　ｔｈｅ　ｔｏｔａｌ　ｑｕａｌｉｔｙ　ｏｆ　ｔｈｅ　ｐｒｏｊｅｃｔ．Ｃｏｎｓｉｄｅｒｉｎｇ　ｔｈｅ　ｍｏｄｅｌ’Ｓ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ｏｆ　ｍｕｌｔｉ—ｖａｒｙ，ｍｕｌｔｉ—ｒｅｓｔｒｉｃｔｉｏｎ　ａｎｄ　ｌａｒｇｅ　ｓｏｌｕｔｉｏｎ　ｓｐａｃｅ，ａ　ｈｙｂｒｉｄ　ａｌｇｏｒｉｔｈｍ　ｎａｍｅｄ　ｉｍｐｒｏｖｅｄ　ａｎｔ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ａｄａｐｔｉｖｅ　ｍｕｔａｔｉｏｎ　ｐｒｏｂａｂｉｌｉｔｙ　ａｎｄ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ｔｈｏｕｇｈｔ　ｉｓ　ｐｒｏｐｏｓｅｄ．Ｔｈｅ　ａｐｐｌｉｃａｔｉｏｎ　ｉｎ　ａ　ｌａｒｇｅ—ｓｃａｌｅ　ｅｎｇｉｎｅｅｒｉｎｇ　ｐｒｏｊｅｃｔ　ｔａｓｋｓ　ａｓｓｉｇｎｍｅｎｔ　ｅｘａｍｐｌｅ　ｖａｌｉｄａｔｅｓ　ｔｈｅ　ｃｏｒｒｅｃｔｎｅｓｓ　ａｎｄ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｏｆ　ｔｈｅ　ｍｅｔｈｏｄ．　Ｋｅｙ　ｗｏｒｄｓ：ｔａｓｋｓ　ｓｃｈｅｄｕｌｉｎｇ；ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ　ｄｅｃｉｓｉｏｎ；ａｎｔ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ；ａｄａｐｔｉｖｅ　ｍｕｔａｔｉｏｎ　ｐｒｏｂａｂｉｌｉｔｙ；ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　摘要：提出了一种大型工程项目任务多目标优化调度方法。构建了一种以项目工期最小化、费用最小化及质量最大化为目标　函数的多目标优化模型；针对模型的多变量、多约束、大组合量特点，提出了一种基于自适应变异和模拟退火思想的改进蚁群算　法。将模型和算法在某大型＿ｚ．ＳｅＡ目任务调度中加以应用，验证了所提出的优化调度方法的正确性和有效性。　关键词：任务调度；多目标决策；蚁群算法；自适应变异；模拟退火算法　ＤＯｈ　１０．３７７８０．ｉｓｓｎ．１００２—８３３１．２０１０．２４．０６４文章编号：１００２—８３３１（２０１０）２４—０２１７—０５文献标识码：Ａ　中图分类号：Ｃ９３—０３；ＴＰ３９１　随着中国经济的高速增长，单体投资超过百亿的大型工　优化调度时常常陷入困境，迫切需要寻找一种科学合理的方　程项目越来越多，项目管理研究越来越受到学术界、企业界高　法以辅助决策。　度关注。大型工程项目具有工期长、任务多、费用高、质量要　针对工程项目管理实践需要，提出了一种项目任务多目　求高的特点，因而在其运营之前制定一个良好的任务调度方　标优化调度方法，首先构建了一种综合考虑工期、质量、费用　案显得十分重要。近年来国内外学者对项目任务调度的研究　目标的多目标任务优化调度模型，针对模型特点，提出并设计　主要集中在单目标和双目标优化两个方面，如质量优化、时间　了一种改进的蚁群算法对其加以求解，最后将整个技术方案　优化、费用优化、资源优化、时间一费用优化、时问一资源优化、时　在工程实践中加以应用验证。　间　质量优化、费用一质量优化、时间一成本一费用优化ｎ。　。目标　数为三个及三个以上的项目任务优化调度是一个复杂的系统　１问题描述及假设　决策问题，其复杂性主要来自于三个方面的冲突：项目总工　问题描述：（１）＂个任务（包）的集合ＴＡＳＫ＝｛Ｔ￣，　，…，　，　期、总质量和总费用之间的冲突，不同承包商完成同一任务的　为第ｆ个子任务（包）；（２）每个任务（包）有工期ｔ　、质量　费用　工期、质量、费用之间的冲突，多个任务争夺同一承包商时产　Ｃｉ三个目标属性，同一任务针对不同的承包商，三个目标属性　生的时间冲突。正是这种复杂性使得决策者在进行项目任务　的值可不同；（３）　个承包商的集合户＝｛ｃ　，Ｃ　，…，Ｃ　｝，Ｃ　为第ｉ　基金项目：国家自然科学基金（ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．７０６０１０３７）；国家教育部“新世纪优秀人才支持　计划”（ｔｈｅ　Ｎｅｗ　Ｃｅｎｔｕｒｙ　Ｅｘｃｅｌｌｅｎｔ　Ｔａｌｅｎｔ　Ｆｏｕｎｄａｔｉｏｎ　ｆｒｏｍ　ＭＯＥ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．ＮＣＥＴ－０７—０９０８）。　作者简介：曾强（１９７５一），男，重庆大学机械工程学院博士研究生，河南理工大学工业工程系副主任，主要研究方向为工业工程、生产管理；杨育　（１９７１一），男，教授，博士生导师，主要研究方向为网络化协同制造、工业工程；王小磊，女，博士研究生，主要研究方向为工业工程、产品　协同设计；赵川，男，硕士研究生，主要研究方向为工业工程。　收稿日期：２００９　１２．０８修回日期：２０１０—０２　０８　２１８　２０１０，４６（２４）　ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ　ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　２．３．１项日总工期　个承包商；（４）基于任务优先级的工程项目网络计划图：决定　了任务（包）之间的相互依赖关系；（５）任务工期矩阵　、质量　矩阵Ｑ、费用矩阵ｃ。现欲提出一种科学辅助方法，帮助决策　者将ＴＡＳＫ中的任务优化分配给尸中的承包商使得项目总工　期　，尽量短、总质量Ｑ　，尽量高、总费用Ｃ　，尽量低，同时确　定最优的任务调度方案。　问题假设：（１）一个工程项目能分解成多个由单个承包商　图１中粗箭头表示关键路径，括号内的数字为决策者预　期的任务平均工期。　独自完成的任务（包）；（２）一个工程项目能找到有限个（　个）　承包商来承接；（３）任务一旦满足开始执行条件（紧前任务完　成且该任务的承包商状态为闲），则立即开始执行该任务，无　、＼、　；一　时滞；（４）一个承包商可以承接的任务数大于等于０；（５）某承　包商一旦开始执行某任务，不可中断去执行另一项任务；（６）同　一承包商同一时间仅执行一项任务，不能并行执行多个任务；　（７）任务与任务之间存在优先顺序，某承包商由忙转闲时，根　据任务池中任务的优先级进行任务选择。　２数学模型　２．１基本参数　ＴＱＣ矩阵：包括三个ｎＸｍ的矩阵，即任务工期矩阵　、质　量矩阵Ｑ和费用矩阵ｃ。　矩阵中元素岛表示任务Ｔｍ承包商　，完成的工期，若承包商，无法承接任务ｉ则将工期值　置为　（很大的正数）；同理，Ｑ矩阵中ｇ　表示任务　由承包商　来完　成时的质量，其值来自于专家就某任务对某承包商的综合评　价，若承包商，无法承接任务ｉ，则将其质量值ｇ　置为一　；ｃ　矩　阵中Ｃ　表示任务　由承包商，完成的费用，其大小取决于承包　商，完成任务　的工期长短、所用的资源和完成任务的方法等　冈素。　ＪＱ矩阵：又称基于优化级的紧前任务矩阵，．，Ｑ矩阵用式　（１）表示。第一列数字代表任务优先级，后面各列数字代表该　任务的紧前任务编号。　ｌ　０　．．　Ｏ　０　２　１　．．　０　０　，Ｑ＝　３　２　．．　０　０　。　－●　●　●　　：：　：　：　９　６　７　０　Ｏ　１０　６　７　８　９　２．２决策变量　设某一大型工程项目可分解成ｎ个任务（包）组成的独立　任务集｛　，　，…，　｝，　个任务在ｍ个承包商中进行选择并分　配。决策变量用式（２）所示的０－１矩阵　表示。　：１表示　分　配给承包　，　，＝ｏ表示　不分配给承包商，。　ｆ　：…　，　一　１　ｘ：ｌ　ｚ…　，ｍ一　ｍ　ｆ　（２）　…　．　一　２．３　日标函数　模型的目标函数如式（３）所示。　（３）　ＯＰＴ　Ｆ（Ｘ）＝（ｍｉｎＬｏ　，，ｍａｘＯｔｏｔａｌ｝ｍｉｎＣ　，）　显然，这是一个多目标优化问题。作为求解方法之一，可　以考虑先将向量中的子目标求出，然后采用“加权平均法”将　其进行单目标化以便于后面采用蚁群算法求解。　图１　基于任务优先级的项日网络计划图　基于图１所示的项目网络计划图，项目总工期　，计算　过程如下：　（１）任务优先级确定　任务的优先级是承包商面临多个任务时进行任务选择的　依据。任务优先级是从ｌ～ｎ的不重复的连续整数，数字越小　优先级越高。确定任务优先级的依据可以很多，取决于项目　性质、项目关键路径、决策者意志、任务的紧迫性等因素。　（２）后向推算　假如对某个大型工程项目已按照既定的原则将其任务优　先级加以确定（如图１中箭头上方的数字），可按式（４）推算项　目总工期　，：　＝　＋ｔ　ｍａｘ（Ｔ￣（０Ｅ，　，ｊ）Ｅ）　０　（４）　其中，　为任务ｉ的最早开工时间；　为任务ｉ的最早完工时　间；ＪＱ（Ｉ）为任务ｉ的紧前任务集合；Ａ（ｉ，　）为任务１～任务ｉ－１中　被分配给承包商，的任务集合。　若指向最后节点的任务有多个，如　一　与　都指向最后一　个节点，此时还不能断定ｏ　，＝　。在这种情况下，人为增加　一道后续虚任务　同时为　、Ｑ、ｃ矩阵各增加一行，该行元　素的值均赋为０。于是，项目总工期可由式（５）确定：　，＝　＋１　．＝ｍａｘ（　∞　￡）　（５　Ｊ　式（５）中虽然没有显性带有ｘ，但　实际上是　的线性函数，　但难以用解析式表达出来，大大增加了模型求解的复杂性。　２．３．２项目总质量和总费用　项目总质量Ｑ　，和项目总费用ｃ　可按式（６）～（７）计　算，其中嚷示点乘。　Ｈ＋１，　Ｑ　＝∑∑　Ｑ）　（６）　ｉ＝１　Ｊ＝１　Ｈ＋１　Ｃ　＝∑∑（ｉ＝１Ｊ＝１　　ｃ）　（７）　２．３．３单目标化　首先利用线性插值法对三个子目标进行了“归一化”处　理，然后采用“加权平均法”将三个无量纲数据统一成单一目　标。处理结果如式（８）所示：　。ＰＴ　Ｆ　＝ｍａｘ，（　＝ｗ　Ｔｍａｘ＿－Ｔ　ｔｏｔａｌ＋　ｗ：　ｔｏ　ｔａｌ－－Ｑｍｉｎ＋Ｃｍａｘ　－Ｃｔｏｔｗ，　ａｌ　（８）　其中，　、Ｑ曲、Ｃ一分别为项目工期上限、质量水平下限、项　曾　强，杨　育，王小磊，等：大型工程项目任务多目标优化调度方法　２０１０，４６（２４）　２１９　目费用上限，　、Ｑ　，、Ｃ　，为决策者预期的理想工期、理　３．２个体编码　如图３所示，针对模型变量特点，采用了基于任务基因段　的二进制编码即一个任务对应于一个长度为ｍ基因段。因每　个任务仅分配给一个承包商，故每个基因段有且仅有一个１。　任务１　任务ｉ　任务　想质量水平和理想费用，ｗ　、Ｗ：、Ｗ　分别为指标　ｃ『０　，的权系数。　、Ｑ　２．４约束条件　约束条件视决策者要求而变化，式（９）～（１４）所示是典型　的约束条件：　。　，≤Ｔ　（９）　匿　二工皿．．臣二二［二工盈…匝二二［至］［＝　图３个体编码　Ｑ　，≥Ｑ　ｍ　Ｃ　，　Ｃ　（１０）　（１１）　３－３参数初始化　：任务数；ｍ：承包商数；Ｗ　、Ｗ，、Ｗ　：工期、质量、费用目标　ｅａｌ：最小　』＝１　∑　＝１，　１，２，…，　（１２）　权系数；Ｖｍ　、　删：最大允许工期’、理想工期；Ｑ　。　、Ｑｉｄ＝，０或１，ｉ＝１，２，…，　；ｌ，＝１，２，…ｍ　（１３）　允许质量、理想质量；Ｃｍ．　、Ｃｉｄｅａｌ：最大允许费用、理想费用；　：　表示项目总工期上限，Ｑ　ｉ　表示项目总质量下限，Ｃ　表示　任务工期矩阵；Ｑ：任务质量矩阵；ｃ：任务费用矩阵；ＳＱ：紧前　工序矩阵；Ａｎｔ：蚁群规模；Ｉｔｅｒ：最大迭代次数；尸ｎ：变异扰动系　项目总费用匕限。　数阈值；Ｐ　：挥发系数；Ｐ　、Ｐｍｒａｉｎ：最大、最小变异率；ｔｏ：模　３算法设计　拟退火初始温度；ａｌｐｈａ：模拟退火系数。　针对上述模型多变量、多约束、超大组合量的特点，一般需　３．４蚁群初始化　利用智能搜索算法求解。蚁群算法是最近十余年来由意大利学　按照“拒绝策略”生成规模为Ａｎｔ的蚁群，即随机生成个　者Ｍ．Ｄｏｒｉｇｏ等人提出的一种新型的并行进化算法。与其他智　体，若该个体可行则放入种群，否则将该个体抛弃。具体初始　能搜索算法一样，简单的蚁群算法也存在一些缺陷，如搜索时间　化流程为：（１）置蚁群现有个体数ｉ＝１；（２）￣ｌＪ断是否有ｉ＜Ａｎｔ成　长，易出现停滞现象　。近年来，学者对蚁群算法主要从两个方　立，若成立则转（３），否则初始化结束；（３）随机生成一个个体　面进行了改进：一是对算法本身的结构和参数进行改进，包括概　；（４）计算该个体对应的项目总工期　、总质量Ｑ　，、总费　率选择机制改进、信息素更新规则改进等　；二是将蚁群算法和　用Ｃ　、适应度　（５）按约束条件（９）～（１１）判断个体ｆ是否可　其他搜索算法相结合以取长补短，如将蚁群算法与模拟退火算　行，若可行则将该个体放入种群中并记录该个体　、Ｑ　法相结合ｎ　“　、将蚁群算法与遗传算法相结合ｎ　、将蚁群算法与　＿厂，置个体ｆ对应的信息量　为＿厂，转（６），否则抛弃该个　粒子群算法相结合［￣４－］５１等。本文在前人研究的基础上，提出了一　体，转（３）；（６）ｉ＝ｉ＋１，转（３）。　种基于自适应变异及模拟退火思想的改进蚁群算法，该算法以　３．５自适应变异设计　蚁群搜索过程为主线，将自适应变异机制和模拟退火思想融合　（１）变异方式　在蚁群搜索过程中，从而有效地提高了算法的收敛性。　为满足任务唯一分配特点，需满足变异后的个体的每个　３．１算法计算流程　基因段有且仅有一个１。为此，以下方式实现变异操作：随机　图２为基于自适应变异和模拟退火思想的改进蚁群算法　生成一个１～ｎ×　之间的整数确定变异点及变异点所在的基因　的计算流程图。　段，若变异点所在基因座值为０，则变为１，同时将此基因座所　图２计算流程图　２２０　２０１０，４６（２４）　ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　箜一图５基于任务优先级的某大型工程项目网络计划图　在基因段中为１的值变为０；若变异点所在基因座值为１，则变　为０，同时在此基因座所在基因段中任选一个为０的基因座将　其值变为１。整个过程可以用图４表示。　任务１　任务ｉ　分（１一Ｐ　）×　及新个体的适应度　。通过不断更新信息素，会　使得信息素总体上朝着越来越大的方向变化，从而对个体变　异起到一种牵引作用，保证解朝着好解方向靠近。　变异前［　互］　圈变异后　夏Ｉ　］　叨（２）扰动系数　　　・臣＝】＝　匝工　图４变异操作　４实例验证与分析　为验证本文提出的大型工程项目多目标任务优化调度方　法，采用Ｍａｔｌａｂ　７．０编程实现了算法并在某大型工程项目管　理中加以应用。图５是该大型工程项目的基于任务优先级的　网络计划图，共有７个承包商参加投标，即有ｎ＝２７，ｍ＝７。取　Ｗ】＝０．４，Ｗ２＝０．３，Ｗ３＝０．３，Ｉｔｅｒ＝７０００，Ａｎｔ＝１００，Ｐ　＝０．５，　信息素　的值对个体　的变异起到一种牵引作用，　离最大　信息素值，ｍ　越远则应给　以越大的变异率使之向好解方向变　异，反之则给以较小的变异率以防止好解劣化。具体实现方　Ｐ　＝Ｏ．１，　＿ｍａ　＝３５０，　Ｃｍ　＝４０５，　，＝２５０，Ｑ　＝２　０００，Ｑ　，＝２　３８０，　。，＝３３０，ａｌｈｐａ＝Ｏ．９９５，ｔｏ＝１，Ｔ矩阵如表１所示，　式是，对每个个体，按式（１４）计算其扰动系数Ｐ，，再将Ｐ，与变异　扰动系数阈值Ｐ　进行对比，从而将个体的变异率划分为两个　不同的区间。　，　一，　…Ｑ、ｃ、．，Ｑ矩阵略。程序运行得到的满意适应度厂为１．００２　６，图　６是其对应的迭代过程图，表２是满意解对应的调度方案，图７　　承包商　Ｐ１尸２　Ｐ３　Ｐ４　Ｐ７　∞Ｐ　承包商　Ｐ　Ｐ　尸　：　』ｍａｘ　（１４）　　。３２　３０　２８　３４　２６　２８　３０　３Ｏ　３５　２５　２８　３２　３Ｏ　３：　（３）变异率　为了减少好解在变异过程中变劣的可能性，采取的有效　措施是对于高适应度的个体采用低变异率，对于低适应度的　９　８　］ｔＯ　ｌｌ　１２　ｌ０　８　３２　３５　３０　２８　２７　２８　２ｆ　２５　２４　２２　２８　３２　３５　２｛　ｌ７　１６　１３　１２　ｌ５　ｌ５　１８　２０　２２　１８　ｌ７　２３　ｌ７　２０　３５　３Ｏ　４０　２５　２８　３２　２７　１Ｏ　８　９　７　６　８　１２　１２　ｉ５　１４　１７　ｌ８　１２　１（　ｓ　３５　２８　２７　３２　２６　３５　２｛　２８　２５　３５　３０　３６　２８　３（　。　３５　３３　２６　３２　２６　３８　２ｆ　．４５　４２　３８　３５　４３　４６　４（　２Ｏ　２６　２８　２２　２６　ｌ９　２：　５０　５５　６０　４５　４０　４５　３｛　１５　１５　１２　１８　１６　１４　１：　个体则采用高变异率进行变异，为此设计了如式（１５）所示的　白适应变异率。其中，　为个体ｆ的适应度，　最大适应度，　大、最小变异率。　ｏ　．　为当代蚁群　为当代蚁群平均适应度，Ｐ　、Ｐ　为最　３０　２４　２６　２９　３３　３０　２５　２０　２４　２６　ｌ８　ｌ６　２５　２８　３５　４２　４０　３８　４２　４０　４６　３５　３０　２６　２８　３Ｏ　３２　２８　２２　２３　２５　１８　ｌ６　２Ｏ　１８　户　＝　：　，　１８　２５　２４　１９　ｌ５　１７　２４　３５　３３　３１　２６　２８　３５　３Ｏ　３Ｏ　２８　３４　２６　３５　３２　３（　３８　３５　４０　３５　４５　３６　４（　３．６模拟退火思想　如图２所示，在整个计算流程中对新个体的处理采用了　模拟退火过程思想，即将新个体ｔｅｍｐｉ的适应度厶…与原个　惭的适应度　相比较，若　＞　，则完全接受该新个体，反　厂　之则以概率ｅｘｐ（ｆ…－ｉｓ）ｉｔ接受该新个体。采用模拟退火思　想可使得搜索过程能从局部最优值跳出，从而增大算法全局　收敛性。　ｉ　ＩｌＩｒＩ　迭代次数ｅｐｏｃ　３．７信息素更新　按公式，，＝（１一Ｐ　）×，，＋　计算新个体　对应的信息素　，其　中Ｐ　为挥发系数。，　包含两部分，即原个体，信息素的剩余部　图６迭代过程图　＝１．００２　６）　曾　强，杨育，王小磊，等：大型工程项目任务多目标优化调度方法　表２满意解对应的任务调度方案　２０１０，４６（２４）　２２１　任务承包商开始任务时问，天任务结束任务质量任务费用历元　任务承包商开始任务时间／天任务结束任务质量任务费用／万元　ｃｓ　０　２６　２６　１００　１６．５　Ｃ　８Ｏ　２５　１０５　８５　１５．０　　’Ｇ　ｃ　２６．３４　８　１５　３４　４９　９５　９５　５．２　６．６　５　Ｃ：　ｌ１７　１４５　２８　２４　１４５　１６９　９５　９５　ｌ３．２　１０．５　Ｇ　巴　Ｃ　４９　６７　９２　１８　２５　１０　６７　９２　ｌＯ２　１０Ｏ　９５　１００　ｌ０．０　１３．５　６　Ｏ　，　ｓ　９　Ｇ　Ｃｓ　Ｃｌ　１６９　１４５　ｌ８４　Ｉ５　２６　２８　１８４　１７１　２１２　９０　９０　９５　６．３　ｌ６　５　１８．０　ｃ　Ｇ　Ｃ　６７　１Ｏ２　２６　３０　１８　４２　９７　ｌ２０　６８　９５　１００　１００　１２．３２　９．０　１６　８　孔ｏ　Ｃ　Ｇ　１２０　１Ｏ５　１５２　３２　３８　ｌ９　ｌ５２　１４３　ｌ７ｌ　９５　１Ｏ０　９０　１３．５　２０．０　１１　０　：　Ｃ　Ｇ　Ｇ　７＂１　Ｃ７　Ｇ　２６　６８　５６　８４　３０　１６　２４　３３　５６　８４　８０　ｌｌ７　９５　９５　９５　８５　１６．５　ｌ１．０　１０　４　１２　６　瓦　Ｇ　Ｃ６　Ｇ　Ｃ６　１４３　１７１　１８５　２１３　６Ｏ　１４　２８　３６　２０３　ｌ８５　２１３　２４９　９５　９５　８５　９５　２５．０　６．６　２５．２　ｌ７．６　时间：天　０　２０　４０　６０　８０　１００　１２０　１４０　１６０　１８０　２００　２２０　２４０　０　１　４　７　时间：天　５０　１００　１５０　２００　２５０　３００　：　１　．ｃ匣ｃ　４　１Ｏ　出１３　ｒｒｒｒ　１６　１９　ｃ６　Ｃ　２２　２５　图７承包商任务调度甘特图　图８项目任务进度甘特图　是满意解对应的承包商任务甘特图，图８是满意解对应的项　目任务进度甘特图。　项目工期最小化、费用最小化及质量最大化为优化目标建立　了多目标优化模型，采用“基于任务优先级的后向推算法”和　数据分析：（１）由图６可知，算法搜索过程中的最大适应　度总体上呈上升趋势，这是由蚁群算法的寻优特点所决定的。　但在寻优过程中也偶尔发生某些代蚁群最大适应度下降，这　矩阵点乘法将总工期、总费用、总成本进行了量化，利用加权　平均原理将多目标转化为单目标。提出了一种基于自适应变　异和模拟退火思想的改进蚁群算法对模型进行求解，该算法　结合了蚁群算法及模拟退火算法各自的优点，具有较好的收　敛效果。实例表明提出的基于精细化管理的大型工程项目多　目标任务优化调度方法是正确和有效的，对于促进项目管理　向精细化管理转变具有重要意义。　是由模拟退火思想所决定的，正是由于利用了模拟退火思想，　才使得个体能从局部最优跳出从而暂时变劣，但随着模拟退　火过程的继续，暂时变劣的解会逐渐变优；（２）从图６还可以　看出，初始由于模拟退火温度较高，使得劣解被接受的概率较　大，故振荡频繁，但随着迭代次数的增加，模拟退火温度逐渐　减小，劣解被接受的概率越来越小，最后趋近于０，从迭代过程　后期表现为最大适应度值趋向于平稳；（３）由最优分配方案表　２得知，最优任务调度方案所对应的总工期　，＝２４９天，项目　参考文献：　［１］胡运权，郭耀煌．运筹学教程［Ｍ］．北京：清华大学出版社，２００３．　［２高兴夫，２］胡程顺，钟登华．工程项目管理的工期．费用一质量综合优　化研究…．系统工程理论与实践，２００７（１０）：１１３　１１７．　【３］杨耀红，汪应洛．工程项目工期成本质量模糊均衡优化研究『Ｊ］．系　统工程理论与实践，２００６（７）：１１２　１１７．　［４］张纪会洎适应蚁群算法［Ｊ］ｌ控制理论与应用，２０００，１７（１）：１－８．　整体质量水平Ｑ　，＝２　４５５，项目总费用Ｃｔｏ　，：３４４．８２万元。　若项目任务按照表２或图７、图８的甘特图进行严格控制，则项　目总体上就能达到以上三个综合最优目标；（４）模型所得到的　最优目标是考虑工期、质量和费用的综合最优目标，不是单项　最优目标，这是符合客观实际的；（５）因专业分工、技术水平等　不同，项目任务分给不同的承包商完成通常能产生更理想的　综合效果。当然，这也会带来一些问题，如需要对多个承包商进　行严格控制从而保证项目工期、质量和费用综合目标的实现，　这期间也会发生相应的控制成本和风险成本，但通常情况下，　优化分配带来的利益会远远大于其付出的成本；（６）由最优分　配和调度甘特图７得知，承包商６综合竞争最强，从承接的任　务数和任务累计时间上看均处于优势，而承包商１、７综合竞　争力最弱，这说明采用优化分配模式不但可以达到项目整体　［５］陈美军，张志胜，史金飞．基于自适应蚁群算法的多约束车辆路径　问题【Ｊ］．东南大学学报，２００８，３８（１）：３７—４２．　［６］彭沛夫，林亚军，胡斌，等．基于遗传因子的自适应蚁群算法最优　ＰＩＤ控制［Ｊ】．电子学报，２００６，３４（６）：１１０９一ｌ１１３．　［７］Ｆａｖｕｚｚａ　Ｓ，Ｇｒａｄｉｔｉ　Ｇ，Ｓａｎｓｅｖｅｒｉｎｏ　Ｅ．Ａｄａｐｔｉｖｅ　ａｎｄ　ｄｙｎａｍｉｃ　ａｎｔ　ｃｏｌｏｎｙ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｏｐｔｉｍａｌ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｓｙｓｔｅｍｓ　ｒｅｉｎ－　ｆｏｒｃｅｍｅｎｔ　ｓｔｒａｔｅｇｙ［Ｊ］．Ａｐｐｌｉｅｄ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００６。２４（１）：３１－４２．　［８张杰慧，８］何中市，王健，等．基于自适应蚁群算法的组合式特征选择　算法［Ｊ］．系统仿真学报，２００９，２１（６）：１６０５　１６１４．　［９］Ｓｈａｈ　Ｍ　Ｙ，Ｌｉ　Ｇ．Ａｕｔｏ—ａｄａｐｔｅｄ　ａｎｔ　ｃｏｌｏｎｙ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａ／ｇｏ—　最优，而且可促进承包商之间相互适度竞争，实现优胜劣汰。　ｒｉｔｈｍ　ｆｏｒ　ｗａｖｅｌｅｔ　ｎｅｔｗｏｒｋ　ａｎｄ　ｉｔｓ印ｐ１ｉｃａｔｉｏｎｓ【ｃ】／／２ｏ０６　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍｅｃｈａｔｒｏｎｉｃｓ　ａｎｄ　Ａｕｔｏｍａｔｉｏｎ，ＩＣ—　５结束语　提出了一种大型工程项目任务优化调度方法。该方法以　ＭＡ　２００６，２００６：２４３７—２４４２．　（下转２４８页）　２４８　２０１０，４６（２４）　ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ　ａｎｄＡｐｐｌｉｅａｔｉｏｎｓ计算机工程与应用　另列表给出了。把各点之间的距离作为费用，即ｃ　：　，（ｉ，ｊ＝０，　２．３．２时间硬限制的处理　对于硬限制可以暂时在编码过程中不考虑约束，而在遗　㈨　㈨　；。㈣∞　使总运行费用最少。１，…，８），如何安排车辆的行驶线路，　参数选择：尸。１＝０．９，Ｐ。２＝０．６，Ｐ　１＝０．１，Ｐ　２＝０．０１。　㈣ｏ加∞　最优解为：０　３　１　２　０＿÷０　６　４　０　０　８　０加　如　５—　７—　０　。。传算法的计算过程中检测得到的染色体相应的解是否可行，　若可行，则放入下一代群体中，否则将其舍弃。　可对上述进行修改，得到　ｍｉｎＺ＝∑∑∑ｃＵ　＋　∑ｍａｘ（∑＆Ｙ“一ｑ，０）＋　ｆ＝０，＝Ｏｋ＝１　＝１　ｉ＝１　这里以ＳＧＡ表示标准遗传算法，以ＡＧＡ表示Ｓｒｉｎｖｉｖａｓ等　３　ｏ　如㈣如瑚　提出一种自适应遗传算法，以ＩＧＡ表示本文的改进遗传算法，　４∑ｍａｘ（ＥＴ．一　，０）＋　∑ｍａｘ（￣一　，０）　Ｊ　１　—　性能指标见表２。　㈣　ｍ　ｏ㈣　㈣　，＝１　如　如　０　∞　表２性能指标　。。　６　。　７巧㈣　ｏ：合∞　此时意味着时间约束必须被满足，否则适应值ｚ　㈣ｍ　如㈣∞＝３　０　）Ｏ　舳　Ｏ　０）『姒∞　∞如０　＾＾）　３实验分析　实验将改进的遗传算法应用于车辆调度优化问题中，程序　运行平台为Ｍａｔｌａｂ　７．０版本，有８项运输任务（编号为１，２，…，　８），各任务的货运量Ｇ．（单位：吨）、装货（或卸货）时间　（单位：小　时）以及要求每项任务开始执行的时间范围［ＥＬ，上硼（单位：时　表２的实验数据可见，本文提出的ＩＧＡ收敛总次数最多，　平均收敛代数最少，可见新算法具有较好的鲁棒性和较快的　收敛速度。　刻）由表１给出。这些任务由车场０发出的容量为６吨的车辆来　完成，车场０与各任务点间的距离矩阵（单位：公里）为：　４结语　标准遗传算法本身存在着早熟（过早收敛于局部最优值）　等缺陷，而改进的遗传算法能根据个体的适应值自动调整算　法中的交叉概率尸　和变异概率Ｐ　值的大小，在保证群体多样　性的同时，保证遗传算法的收敛性，很好地解决了早熟问题。　此外，还对染色体编码和时间约束的处理等问题进行了改进，　并成功地将这种算法应用于车辆凋度优化问题中。这种算法　简单可行，提高了优化算法的质量和搜索效率。　表１任务的特征及要求　参考文献：　［１］骆正山，王小亮．基于模糊条件下车辆路径问题的研究…．微电子　学与计算机，２００５，３８７（３）：ｌ８１—１８４．　［２］王小平，曹立明．遗传算法：理论、应用与软件实现［Ｍ］．西安：西安　交通大学出版社，２００２：６４—６７．　［３］航宇，金晶，苏勇．自适应遗传算法交叉变异算子的改进［Ｊ］＿汁算机　工程与应用，２００６，４２（１２）：９３．９６．　ｒ４］苏金明，王永利，ＭＡＴＬＡＢ７．０实用指南［Ｍ］．北京：电子：［业出版　社，２００４．　［５】卢厚清，王辉东，黄杰，等．任务均分的多旅行商问题［Ｊ］．系统工程，　２００５．２３（２）：２２—２４　这里，假设车辆的行驶时间与距离成正比，每辆车的平均　［６］黄可伟，汪定伟．热轧计划中的多旅行商问题及其计算方法［Ｊ】．计　算机应用研究，２００７，２４（７）：４３　４５．　行驶速度为６０　ｋｍ／ｈ，则从点ｆ到　的行驶时间，ｔｕ＝ｄＪ６０，就不　（上接２２１页）　［１Ｏ］傅鹏，张德运，马兆丰，等网络中基于模拟退火蚁群算法的ＱｏＳ　［１３］Ｋｅｒａｍａｔｉ　Ａ，Ａｚａｄｅｈ　Ａ，Ｅｂｒａｈｉｍｉｐｏｕｒ　Ｖ，ｅｔ　ａ１．Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　ａ　ｈｙｂｒｉｄ　ｇｅｎｅｔｉｃ－ａｎｔ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｅｘｐｌｏｒｉｎｇ　ｔｈｅ　ｒｅｌａｔｉｏｎ—　路由发现方法…．西安交通大学学报，２００６，４０（２）：１７９．１９０．　［１１］Ｍｕｓａ　Ｒ，Ｃｈｅｎ　Ｆ　Ｆ．Ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｎｄ　ａｎｔ　ｃｏｌｏｎｙ　ｏｐｔｉｍｉ—　ｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｔｈｅ　ｄｙｎａｍｉｃ　ｔｈｒｏｕｇｈｐｕｔ　ｍａｘｉｍｉｚａｔｉｏｎ　ｐｒｏｂ—　ｓｈｉｐ　ｂｅｔｗｅｅｎ　ＩＴ　ａｎｄ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｏｒｇａｎｉｚａｔｉｏｎｓ［Ｃ］／／ＩＩＥ　Ａｎ—　ｎｕａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ａｎｄ　Ｅｘｐｏ　２００８，２００８：１１０７－１１１２　［１４］张维存，郑丕谔，吴晓丹．基于蚁群粒子群算法求解多目标柔性调　度问题…．汁算机应用，２００７，２７（４）：９３６—９４１．　［１５］Ｓｈｅｌｏｋａｒ　Ｐ　Ｓ，Ｓｉａｒｒｙ　Ｐ，Ｊａｙａｒａｍａｎ　Ｖ　Ｋ，ｅｔ　ａ１．Ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ａｎｄ　ａｎｔ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍｓ　ｈｙｂｒｉｄｉｚｅｄ　ｆｏｒ　ｉｍｐｒｏｖｅｄ　ｃｏｎｔｉｎｕｏｕｓ　ｏｐｔｉ。　ｌｅｍ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ａｄｖａｎｃｅｄ　Ｍａｎｕｆａｃｔｕｒｉｎｇ　Ｔｅｃｈ—　ｎｏｌｏｇｙ，２００８，３７（７／８）：８３７—８５０．　【１２］毛宁，顾军华，谭庆，等．蚁群遗传混合算法［Ｊ］ｌ计算机应用，２００６，　２６（７）：１６９２—１６９６．　ｍｉｚａｔｉｏｎ［Ｊ］．Ａｐｐｌｉｅｄ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔａｔｉｏｎ。２００７，】８８（１）：　１　２９．】４２．