下载文档原格式
资源受限多项目调度的混合遗传算法
应瑛;寿涌毅;李敏
【期刊名称】《浙江大学学报（工学版）》
【年(卷),期】2009(043)001
【摘要】针对资源受限多项目调度问题,提出了改进后的混合遗传算法.该算法基于串行进度生成机制,结合多项目任务列表与项目优先权设计了新的染色体,所设计的交叉算子与变异算子均能保证所得新个体满足项目紧前关系约束,从而有效提高算法搜索效率.算法充分利用不同启发式算法构造初始种群,有效扩大种群多样性以避免过早收敛.算法采用正向逆向调度技术对调度方案进行优化,进一步提高了调度方案的质量.与其他多项目调度启发式算法相比,该算法能有效分配资源,显著缩短项目平均总工期.
【总页数】5页(P23-27)
【作者】应瑛;寿涌毅;李敏
【作者单位】浙江大学,管理学院,浙江,杭州310058;浙江大学,管理学院,浙江,杭州310058;浙江大学,管理学院,浙江,杭州310058
【正文语种】中文
【中图分类】TB114.1;TP311.5
【相关文献】
1.资源受限项目调度中基于邻域搜索的混合遗传算法 [J], 王振禄;蔡慧林
2.基于混合遗传算法的资源受限的运输任务调度 [J], 王剑;王红卫
3.多模式资源受限项目调度问题的混合遗传算法 [J], 喻瑛
4.求解资源受限多项目调度的改进遗传规划算法 [J], 陈浩杰;丁国富;张剑;阎开印
5.转移资源受限多项目调度的改进量子遗传算法 [J], 郭云涛;陈志;白思俊
因版权原因，仅展示原文概要，查看原文内容请购买。
基于改进粒子群算法的工程设计优化问题研究在当今的工程领域，优化设计问题至关重要。
它不仅能够提高工程产品的性能和质量，还能有效降低成本和缩短研发周期。
而粒子群算法作为一种强大的优化工具，在解决工程设计优化问题方面展现出了巨大的潜力。
然而，传统的粒子群算法在某些复杂的工程问题中可能存在局限性，因此对其进行改进成为了研究的热点。
粒子群算法的基本原理是模拟鸟群觅食的行为。
在算法中，每个粒子代表问题的一个潜在解，它们在解空间中飞行，通过不断调整自己的速度和位置来寻找最优解。
粒子的速度和位置更新取决于其自身的历史最优位置和整个群体的历史最优位置。
这种简单而有效的机制使得粒子群算法在处理许多优化问题时表现出色。
然而，在实际的工程设计优化中，问题往往具有高维度、多约束和非线性等特点，这给传统粒子群算法带来了挑战。
例如，在高维度空间中，粒子容易陷入局部最优解；多约束条件可能导致算法难以满足所有约束；非线性特性则可能使算法的搜索变得困难。
为了克服这些问题，研究人员提出了多种改进粒子群算法的策略。
其中一种常见的方法是引入惯性权重。
惯性权重的引入可以控制粒子的飞行速度，使其在搜索过程中更好地平衡全局搜索和局部搜索能力。
较大的惯性权重有利于全局搜索，能够帮助粒子跳出局部最优；较小的惯性权重则有助于在局部区域进行精细搜索，提高解的精度。
另一种改进策略是对粒子的学习因子进行调整。
学习因子决定了粒子向自身历史最优位置和群体历史最优位置学习的程度。
通过合理设置学习因子，可以提高算法的收敛速度和搜索效率。
此外，还有一些研究将粒子群算法与其他优化算法相结合，形成混合算法。
例如，将粒子群算法与遗传算法相结合，利用遗传算法的交叉和变异操作来增加种群的多样性，避免算法早熟收敛。
在工程设计优化问题中，改进粒子群算法已经取得了许多显著的成果。
以机械工程中的结构优化设计为例，通过改进粒子群算法，可以在满足强度、刚度等约束条件的前提下，优化结构的形状、尺寸和材料分布，从而减轻结构重量，提高结构的性能。
协同震荡搜索混沌粒子群求解资源受限项目调度问题戴月明;汤继涛;纪志成【摘要】针对求解资源受限项目调度问题(RCPSP),提出了协同震荡搜索混沌粒子群(CSCPSO)算法.算法围绕种群粒子吸引子建立双向协同震荡搜索机制,该机制一方面使粒子向吸引子收敛,另一方面使粒子震荡调整自身与吸引子相邻维度大小关系不一致的维度,提升算法的搜索精度和种群的多样性.项目调度采用基于粒子的拓扑排序和串行项目进度生成机制,保证项目调度解决方案满足资源约束和紧前约束.采用具体算例对算法进行检验,结果表明该算法在求解RCPSP的精度和稳定性方面表现更优.【期刊名称】《计算机应用》【年(卷),期】2014(034)006【总页数】5页(P1798-1802)【关键词】协同震荡搜索;混沌;粒子群优化算法;拓扑排序;资源受限项目调度问题【作者】戴月明;汤继涛;纪志成【作者单位】江南大学物联网工程学院,江苏无锡214122;江南大学物联网工程学院,江苏无锡214122;江南大学物联网工程学院,江苏无锡214122【正文语种】中文【中图分类】TP391资源受限的项目调度问题(Resource-Constrained Project Scheduling Problem,RCPSP),是在满足活动时序、资源约束等条件下安排各活动开始和结束时间以达到工期最小的调度方法[1]。
RCPSP广泛存在于各个行业中,该问题已被证明是NP-hard问题[2]。
因其求解困难,吸引着国内外众多学者研究,迄今已提出了一系列的问题模型,形成了一套比较完善的模型库。
RCPSP优化方法概括起来可分为精确算法和启发式算法。
精确算法用于求解小规模调度问题,但对大规模的问题求解力不从心。
对于大型复杂的调度问题,引入了各类启发式算法,如遗传算法、蚁群算法、模拟退火算法[3-5]等。
目前,一种在其他领域应用比较成功的群智能算法——粒子群优化(Particle Swarm Optimization, PSO)算法也被引入来解决这类问题[6]。
基于粒子群算法的微电网优化调度应用研究随着能源危机以及环境污染问题的日益突出，微电网成为一种受人们瞩目的新能源供应方式。
微电网是指由可再生能源与传统能源相结合，在特定区域内形成的能源互联网系统。
为了实现微电网的高效运行，需要进行优化调度。
而粒子群算法（Particle Swarm Optimization, PSO）正是一种优化算法，可以用于微电网的优化调度。
首先，粒子群算法是一种群体智能算法，受到鸟群觅食行为的启发。
算法的基本思想是个体（粒子）通过更新速度和位置来探索潜在的解空间，通过个体之间信息的共享来进行。
粒子群算法具有全局寻优能力，并具有较好的收敛性。
在微电网优化调度中，可以把微电网的电能生产、储存与需求等因素看作是粒子的速度与位置。
通过更新速度与位置，可以得到微电网的最优调度方案，即以最小的成本满足电能需求。
具体而言，可以设置目标函数为微电网的总成本，包括电力购买费用、燃料费用、负荷救济费用等，同时满足用户的电能需求。
粒子群算法会不断地更新粒子的速度与位置，通过迭代找到全局最优解。
另外，粒子群算法还可以考虑微电网的可靠性与可持续性因素。
可靠性指在电力系统中保持电能供应的能力，可持续性指以可再生能源为主要供能方式，减少对传统能源的依赖。
通过设定适当的约束条件，可以限制微电网的可靠性与可持续性指标，确保微电网的稳定运行。
为了验证粒子群算法在微电网优化调度中的有效性，可以使用实际的微电网数据进行仿真实验。
根据微电网的特性与参数设置初始位置与速度，通过迭代更新来逐渐找到最优解。
同时，可以与其他优化算法进行比较，如遗传算法、模拟退火算法等，验证粒子群算法的优越性。
综上所述，基于粒子群算法的微电网优化调度应用研究具有重要意义。
通过粒子群算法能够得到微电网的最优调度方案，降低电能成本，保证可靠性与可持续性。
希望这个研究能够为微电网的实际应用提供有效的参考。
多模式资源受限项目调度问题的混合遗传算法
喻瑛
【期刊名称】《东南大学学报（自然科学版）》
【年(卷),期】2008(038)004
【摘要】多模式资源受限项目调度问题是一种NP难的组合优化问题.提出了与基于关键链的启发式算法相结合的二层混合遗传算法对该问题进行求解.在由上层算法确定的调度顺序下,下层遗传算法结合基于关键链的启发式算法,对系统资源重新优化配置,使算法加速向最优解区域收敛,并在下层设计了随迭代代数增加的可变变异概率,以避免早熟收敛.利用标准问题库对算法进行测试,分析问题参数与算法参数对算法结果的影响,发现实验结果的绩效随迭代数的增加而提高,算法耗时随任务数和迭代数的增加而增加.数值测试结果验证了算法的可行性和可靠性.
【总页数】5页(P736-740)
【作者】喻瑛
【作者单位】东南大学经济管理学院,南京,210096
【正文语种】中文
【中图分类】C934
【相关文献】
1.抢占式资源受限项目调度问题的遗传算法 [J], 寿涌毅;彭晓峰;李菲;赖昌涛
2.一种求解资源受限项目调度问题的遗传算法 [J], 杜焱;彭武良
3.求解模糊资源受限项目调度问题的遗传算法 [J], 王宏;林丹;李敏强
4.求解柔性资源受限项目调度问题的多种群遗传算法 [J], 姚敏
5.基于遗传算法的多模式资源受限项目调度问题 [J], 侯强;刘志霞;秦毅
因版权原因，仅展示原文概要，查看原文内容请购买。
求解云计算任务调度的粒子群优化算法研究云计算任务调度是指在云计算环境中，将任务分配给合适的计算资源进行执行的过程。
任务调度的效率和质量直接影响着云计算系统的性能和用户体验。
为了优化任务调度的结果，研究者提出了多种优化算法，其中一种经典的算法是粒子群优化算法（Particle Swarm Optimization, PSO）。
本文将重点研究云计算任务调度的粒子群优化算法。
粒子群优化算法是一种基于模拟群体行为的优化算法，最初在20世纪90年代由美国Indiana University的Eberhart和Kennedy提出。
它通过模拟鸟群寻找食物的行为，来求解优化问题。
算法的核心思想是通过粒子之间的迭代和信息共享，不断更新粒子的位置和速度，从而找到最优解。
在云计算任务调度中，粒子群优化算法可以将任务表示为粒子的位置，计算资源表示为粒子的速度。
算法的基本流程如下：1.确定问题的目标函数。
云计算任务调度的目标一般是最小化任务的执行时间、最大化系统的利用率或者最小化能源消耗等。
目标函数应该能够评估出各个解的优劣程度。
2.初始化粒子群的位置和速度。
每个粒子代表一个任务，位置表示任务的调度方案，速度表示任务的执行时间或其他指标。
位置和速度的初始化可以采用随机生成的方式。
3.对每个粒子计算适应度值，即目标函数的值。
根据适应度值的大小，更新粒子的个体最优位置和整个群体的全局最优位置。
4.根据粒子的个体最优位置和全局最优位置，调整粒子的速度和位置。
可以借鉴其他粒子群优化算法的更新公式，例如线性或非线性的速度和位置更新公式。
5.判断终止条件，如果满足停止条件（例如达到最大迭代次数或目标函数值小于一些阈值），则输出最优解；否则返回步骤3继续迭代。
在云计算任务调度中，粒子群优化算法有以下优势：1.全局能力强。
粒子通过全局最优信息的引导，具有较好的全局性能，能够找到问题的最优解或近似最优解。
2.并行计算效率高。
粒子群算法的计算过程中粒子之间的更新是独立的，可以利用并行计算的特性，提高算法的运行效率。
第４０卷 第２期２０１３年２月计算机科学Ｃｏｍｐｕｔｅｒ ＳｃｉｅｎｃｅＶｏｌ．４０Ｎｏ．２Ｆｅｂ ２０１３到稿日期：２０１２－０４－０５ 返修日期：２０１２－０７－０８ 本文受教育部人文社会科学规划基金项目（１０ＹＪＡ６３０１８７），高等学校博士点基金（２００９３１２０１１０００８），上海市重点学科建设项目（Ｓ３０５０４），上海市教育委员会科研创新项目（１２ＺＳ１３３），上海市研究生创新基金项目（ＪＷＣＸＳＬ１１０２）资助。
陈君兰（１９８８－），女，硕士，主要研究方向为项目管理，Ｅ－ｍａｉｌ：ｔｒａｃｙｃｈｅｎ０６０２＠１６３．ｃｏｍ；叶春明（１９６４－），男，博士，教授，主要研究方向为工业工程、企业战略、企业生产计划与控制、生产调度、企业资源计划（ＥＲＰ）、供应链管理以及企业信息化。
粒子群优化算法在柔性资源受限项目调度中的研究陈君兰 叶春明（上海理工大学 上海２０００９３） 摘 要 为了更有效地解决柔性资源受限项目调度问题，建立了速熟练度的技能供给矩阵，并应用混沌粒子群优化算法来满足工序的先后约束关系，以在技能供给受限的情况下形成优先规则序列，根据串行进度生成机制形成该序列下的最优解，运用嵌入混沌理论的粒子群优化算法更新种群，寻得全局最优解。
实验结果验证了混沌粒子群优化算法求解该问题的可行性和有效性，对于项目管理中柔性资源受限问题具有实际应用价值。
关键词 柔性资源，粒子群，项目调度，串行进度生成机制，混沌中图法分类号 ＴＰ３９１ 文献标识码 Ａ Ｆｌｅｘｉｂｌｅ－ｒｅｓｏｕｒｃｅ Ｃｏｎｓｔｒａｉｎｅｄ Ｐｒｏｊｅｃｔ Ｓｃｈｅｄｕｌｉｎｇ Ｒｅｓｅａｒｃｈ Ｂａｓｅｄ ｏｎ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ ＯｐｔｉｍｉｚａｔｉｏｎＣＨＥＮ Ｊｕｎ－ｌａｎ ＹＥ Ｃｈｕｎ－ｍｉｎｇ（Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｈａｎｇｈａｉ ｆｏｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｓｈａｎｇｈａｉ ２０００９３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ Ｉｎ ｏｒｄｅｒ ｔｏ ｂｅｔｔｅｒ ｓｏｌｖｅ ｔｈｅ ｆｌｅｘｉｂｌｅ－ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｅｄ ｐｒｏｊｅｃｔ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ，ｍａｔｒｉｘ ｗｉｔｈ ｐｒｏｆｉｃｉｅｎｃｙｗａｓ ｅｓｔａｂｌｉｓｈｅｄ ｔｏ ｓｈｏｗ ｔｈｅ ｒｅｌａｔｉｏｎｓ ｂｅｔｗｅｅｎ ｒｅｓｏｕｒｃｅｓ ａｎｄ ｓｋｉｌｌｓ，ａｎｄ ＣＰＳＯ（Ｃｈａｏｓ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ）ｗａｓｕｓｅｄ ｉｎ ｔｈｉｓ ｅｓｓａｙ ｔｏ ｓｏｌｖｅ ｔｈｉｓ ｐｒｏｂｌｅｍ．Ｉｎ ｃｏｎｓｉｄｅｒａｔｉｏｎ ｏｆ ｗｏｒｋ’ｓ ｐｒｉｏｒｉｔｉｅｓ ａｎｄ ｆｌｅｘｉｂｌｅ－ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｅｄ ｐｒｏｂｌｅｍ，ａ ｒａｎｄｏｍｉｚｅｄ ｐｒｉｏｒｉｔｙ ｃｈａｉｎ ｗａｓ ｆｏｒｍｅｄ ａｎｄ ｆｏｌｌｏｗｅｄ ｂｙ ａｎ ｏｐｔｉｍｉｚｅｄ ｒｅｓｕｌｔ ｂａｓｅｄ ｏｎ Ｓｅｒｉａｌ Ｓｃｈｅｄｕｌｅ Ｇｅｎｅｒａｔｉｏｎ Ｓｃｈｅｍｅ（ＳＳＧＳ）ａｎｄ ｔｈｅ ｂｅｓｔ ｓｃｈｅｄｕｌｅ ｏｆ ｔｈｅ ｗｈｏｌｅ ｐｒｏｊｅｃｔ ｗａｓ ｆｏｕｎｄ ｂｙ ｕｐｄａｔｉｎｇ ｔｈｅ ｐｏｐｕｌａｔｉｏｎ ｂｙ ＣＰＳＯ．Ｒｅｓｕｌｔｓ ｐｒｏｖｅ ｔｈｅｐｏｓｓｉｂｉｌｉｔｙ ａｎｄ ｅｆｆｅｃｔ ｏｆ ｔｈｉｓ ｍｅｔｈｏｄ ｉｎ ｓｏｌｖｉｎｇ ｔｈｉｓ ｐｒｏｂｌｅｍ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓ ｍｅｔｈｏｄ ｈａｓ ｉｔｓ ｐｒａｃｔｉｃａｌ ａｐｐｌｉｃａｔｉｏｎ ｖａｌｕｅ ｆｏｒｔｈｅ ｆｌｅｘｉｂｌｅ－ｒｅｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｅｄ ｐｒｏｊｅｃｔ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍ．Ｋｅｙｗｏｒｄｓ Ｆｌｅｘｉｂｌｅ－ｒｅｓｏｕｒｃｅ，Ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ），Ｐｒｏｊｅｃｔ ｓｃｈｅｄｕｌｉｎｇ，Ｓｅｒｉａｌ ｓｃｈｅｄｕｌｅ ｇｅｎｅｒａｔｉｏｎ ｓｃｈｅｍｅ（ＳＳＧＳ），Ｃｈａｏｓ １ 引言资源受限项目调度问题（Ｒｅｓｏｕｒｃｅ－Ｃｏｎｓｔｒａｉｎｅｄ ＰｒｏｊｅｃｔＳｃｈｅｄｕｌｉｎｇ Ｐｒｏｂｌｅｍ，ＲＣＰＳＰ）是在资源前后约束下带有最小化项目持续时间目标的项目调度问题，也就是资源限制条件下的工期最短问题［１］。
多启发式规则融合粒子群算法的受限项目调度刘焕玉;喻小光【期刊名称】《计算机工程与应用》【年(卷),期】2016(052)022【摘要】在船舶生产的现实背景上，对船舶生产过程中如何利用总装平台这一瓶颈资源建立空间资源受限项目调度的问题模型。
利用空间资源和分段任务对象的特性，在最大面积优先、最长边优先、BL（Bottom-Left，一种解决布局问题的启发式规则）规则等启发式规则的基础上，提出多启发式规则融合粒子群算法的空间资源受限项目调度算法。
将分段任务对象根据几何特性和拖延惩罚因子赋予不同的权值，确定其实际开始时间，再通过最长边优先和BL规则确定其空间位置。
设计了具有初始解集并且能够自动识别的粒子群算法，加速其收敛以更快更优地获取分段任务对象序列。
通过和其他几种主流的空间调度方法（分支界定和遗传算法）进行不同规模的实验对比，得出该算法在时间复杂度和平均资源利用率方面都有所提高。
%As a kind of spatial resource, assembly platform plays an important role in ship building. Spatial resource con-strained project scheduling is proposed for optimizing utilization rate of assembly platform. On the basis of the spatial resource and constraints between tasks, algorithm integrates multi-heuristic rules with particle swarm optimization is pre-sented. In this paper, the start time of blocks are according to their different weight which is decided by their geometrical features and delays, and the position of blocks are according to Bottom-Left and Longest edge rules. In order to achieve the optimal sequence of tasks, a novel adaptive particle swarmoptimizer is designed via optimizing initial particles and self-check. An experiment compared with the traditional algorithms is provided to illustrate the high effectiveness of the proposed approach in both time complexity and utilization rate of resource.【总页数】6页(P226-231)【作者】刘焕玉;喻小光【作者单位】华侨大学计算机科学与技术学院，福建厦门 361021;华侨大学计算机科学与技术学院，福建厦门 361021【正文语种】中文【中图分类】TP391【相关文献】1.基于混沌差分进化粒子群算法的模糊资源受限项目调度问题 [J], 何立华;马芳丽2.粒子群算法在具有迭代关系资源受限项目调度中的应用 [J], 郭云涛;宋红艳;白思俊3.自适应粒子群算法求解资源受限多项目调度问题 [J], 王海鑫;王祖和;温国锋;李海霞4.求解资源受限项目调度的双种群准粒子群算法 [J], 何杰光;陈新度;陈新;刘强5.基于粒子群算法的多类资源受限项目调度 [J], 郭琦因版权原因，仅展示原文概要，查看原文内容请购买。
基于蚁群算法的资源受限多项目调度问题研究高金;郭顺生;杜百岗;李西兴【摘要】资源受限多项目调度问题主要是在资源有限的条件下寻找理想的项目调度方案,从而使多项目的完成工期最短.对于这一NP问题,文中采用改进后的蚁群算法.该算法基于串行调度生产机制,结合多项目任务列表和项目优先权对启发式信息进行改进,从而在满足项目紧前约束的条件下对多项目进行合理的调度.通过与其他多项目调度启发式算法相比,该算法能有效的分配资源,显著的缩短多项目的完成时间.%The resource-constrained multi-project scheduling problem addresses the important issue which seeks to find the expected project scheduling when the amount of resource is limited, and make the overall multi-project duration is shortest. For it is a NP problem, this paper use the improved ant colony algorithm. The algorithm utilized the serial schedule generation scheme to construct project schedules, and combined with multi-project task lists and project priorities to improve on the heuristic information to achieve the reasonable scheduling when meet precedence feasible. Through compare with other multi-project scheduling heuristic algorithm, this algorithm can effectively allocate resources, significantly reduce the multi-project completion time.【期刊名称】《武汉理工大学学报（交通科学与工程版）》【年(卷),期】2013(037)001【总页数】4页(P183-186)【关键词】蚁群算法;多项目调度;资源受限【作者】高金;郭顺生;杜百岗;李西兴【作者单位】武汉理工大学信息工程学院武汉 430070;武汉理工大学信息工程学院机电学院武汉 430070;武汉理工大学信息工程学院机电学院武汉 430070;武汉理工大学信息工程学院机电学院武汉 430070【正文语种】中文【中图分类】TH186目前对资源受限的项目调度问题（resourceconstrained project scheduling problem，RCPSP）的研究主要集中于单项目的研究上，对于资源受限的多项目调度问题（resource－constrained multi－project scheduling problem，RCMPSP）通常的处理方式有单项目方式和多项目方式2种［1］.前者是通过人为加入“开始”和“结束”的虚拟活动将多个项目综合转变为单个项目求解，而后者则把项目看成独立的.由于单项目方式忽略了资源在多个项目间的分配与在单个项目内部各活动间的分配的区别，因此存在理论缺陷［2］.对于多项目方式的研究，研究者从不同的角度，应用不同的技术对该问题进行研究.文献［3－6］运用遗传算法进行网络资源调度，能有效的改进项目调度方案，但是其搜索效率具有一定的随机性，且在作业数量较大时，会使算法的搜索空间急剧扩大，造成遗传算法的性能下降［7］.文献［8］提出一种排序方案，但是该研究没有提及如何处理作业之间的时序逻辑关系.文献［9］提出运用粒子群算法的方案，但是当项目任务多时，该算法对于离散的优化可能导致较大的误差，容易陷入局部最优.文献［10］提出针对RCMPSP的最大－最小蚁群优化算法，并结合禁忌表能够很好的防止蚁群算法的停滞现象.本文基于实际工作背景，分析RCMPSP的特点，结合文献［11］的案例建立以各项目完成时间最短为目标的数学模型.由于文献［11］用到的是遗传算法的思想，因此存在遗传算法的各种弊端.因此本文根据资源上作业间的时序关系和项目内部任务的紧前关系组成的项目网络图，提出运用蚁群算法和串行调度生产机制［12］相结合的方法对该问题求解，并运用禁忌搜索来提高算法的局部搜索能力.为使算法具有实用性，给出算法的基本步骤.结合实例对算法进行测试，通过实例表明，算法能有效的解决资源约束下的多项目调度问题.1 问题描述据典型的RCMPSP的描述，本文研究的RCMPSP共包含N个独立的子项目.各子项目之间没有必然的联系，但可能需要占用同一种资源.每个子项目包含J个任务；其任务按照1到J进行编码，其中第1和第J个任务为子项目的虚拟起始任务和最终任务，均不占资源和时间；用Aij表示第i个子项目的第j（j＝1，2，…，J）个任务，其工期为dij，任务的开始时间记为STij，完成时间记为FTij；且所有任务一旦开始就不可中断.子项目的各任务之间存在紧前关系，即各任务只有在其所有紧前任务都结束之后才能开始；任务Aij的紧前任务集合记为Pij.所有项目共享K种可更新资源，其中第k种资源的供应量为Rk；任务Aij对第k种资源的需求量为rkij.记时刻t正在进行的所有任务的集合为It.则RCMPSP可以表示为如下数学模型式中：Fi，J为第i个项目的最终完成时间，由于所有项目均从时间0开始，则max｛Fi，J｝为整个项目组的总工期.式（1）即为RCMPSP的目标函数，最小的项目工期；式（2）表示项目内部各任务之间的紧前关系；式（3）表示在任意时刻所有当前任务对资源的总需求不得超过该资源的供应量.2 基于RCMPSP的蚁群算法2.1 混合蚁群算法的设计由于无资源约束下每个项目活动都有各自的最早开始时间STij和工期dij，则根据串行调度生成机制，能够得到个阶段，每个阶段都有一个可行集DJ，在局部可行集中运用蚁群算法的思想，从而实现对RCMPSP的求解.下面对算法的具体求解过程进行说明.步骤1 初始化数据，包括初始化蚂蚁的信息素矩阵、算法的启发式矩阵.步骤2 迭代开始.步骤3 将一只蚂蚁放入虚拟起始点.步骤4 求阶段J的可行任务集.步骤5 蚂蚁根据转移规则从可行任务集中选择下一结点，即任务.将选择任务加入禁忌表中，并更新可行任务集和资源拥有量Rk.其中转移规则，采用轮盘赌选择规则；可行任务集表示在J阶段k资源上可行的任务集合，根据项目活动的计划开始时间和完成时间以及任务Aij占用的资源数决定.步骤6 判断可行任务集是否为空.若非空，则转至步骤5；否则执行步骤7.步骤7 更新项目任务的计划开始时间和完成时间.步骤8 如果蚂蚁走完所有项目的所有任务，记录蚂蚁的路径，执行步骤9；否则返回步骤4.步骤9 如果M只蚂蚁都走完所有项目的所有任务，执行步骤10；否则返回到步骤3.步骤10 将M只蚂蚁的M 条路径的信息素进行挥发，对这M条路径中完成时间最短的路径进行信息素增强.且保证所有的信息素浓度在范围［τmin，τmax］中. 步骤11 判断迭代是不是满足终止条件，若满足，则迭代结束；否则返回至步骤2.2.2 状态转移规则由算法流程可知蚂蚁都从起始点开始直到他们走完所有的节点，即蚂蚁走完所有项目的所有任务.由于在某一时间内可能存在多个项目任务同时占用某一资源，但资源不能同时满足所有项目任务的需求时，如何选择优先执行是算法的关键.由蚁群算法的思想可知蚂蚁会根据随机选择规则进行选择.计算公式为式中：pJA为阶段J选择活动A的概率；ηJA为阶段J活动A 的启发信息由式（6）计算；τJA为阶段J活动A的信息素浓度，由信息素更新机制得到；DkJ为蚂蚁在资源k上阶段J的可行集，由串行调度生成机制得到.式中：stA为活动A 的开始时间；DJ为阶段J的可行集.2.3 信息素更新规则当所有蚂蚁都遍历完所有的项目任务，所有的项目任务的信息素将发生更新.根据实际的蚂蚁可知，信息素的更新方式主要包括信息素挥发和信息素加强.首先当蚂蚁遍历所有项目任务时，信息素会按照一定的比例进行信息素挥发，挥发量由下式给出式中：ρ为挥发强度，0＜ρ＜1.在迭代中，为了突出蚂蚁的最佳路径在下次迭代中被选择概率，只对最佳路径上的信息素浓度进行加强，即最佳的项目调度的信息素得到加强.加强方式如下式中：ΔτbsJA为迭代中最佳的项目调度增加的信息素.式中：Q为蚂蚁的信息素总量，为一常数；Cbs为最佳路径的距离，这里表示项目调度中，最短的完成时间.然而，由于在一次迭代中可能存在所有的蚂蚁都选择同一种调度方案，从而导致这个调度方案的信息素增加太快，以致发生停滞现象，影响最优解的求得.为了避免这种现象的发生，本文采用最大最小蚁群算法，将信息素浓度控制在［τmin，τmax］中.式中：a为常数.2.4 可行任务集DJ由算法流程图可知，可行任务集DJ是算法的重要参数，它的扩展包含了整个项目调度的所有的解空间，如何求可行任务集DJ是算法的重点.根据Kelley的串行调度生成机制，对于包含N个项目的RCMPSP来说，一共包含个任务，因此对于RCMPSP的串行调度生成机制，需要个阶段.在每一阶段中，首先要确定可行集DJ，根据一定的优先规则从DJ中选取任务，并在满足式（2）、（3）的条件下进行调度.通过局部扩展，逐步更新可行集，从而得到整个项目的进度安排.由于每个项目都有各自的计划开始时间，于是将各项目任务按计划开始时间分配到对应资源k上，如图1所示3个项目活动在资源k上的计划进度安排.由图可知项目1和项目2最早开始发生资源冲突，则在此冲突持续时间段内的所有项目任务即为此阶段的可行任务集DJ.图1 资源冲突3 实例仿真与分析实例模型采用文献［11］的模具生产项目，即3个具有相同结构的并行执行项目，网络结构见图2.每个项目有16个任务，一共48个任务，占用9种资源，且每个项目任务只占用一种资源，不同的项目任务的执行时间不同.项目任务在无资源约束下的计划开始时间、工期和占用资源数量见表1.图2 项目网络图表1 项目活动无资源约束下的开始时间和工期及占用资源数量注：Rd为占用资源数量；ST为无资源约束下的计划开始时间，d；DT为项目任务的工期，d.任务号资源种类项目1项目2项目3 Rd ST DT Rd ST DT Rd ST DT 1 1 8 0 4 4 0 5 6 0 4 2 1 5 4 3 6 5 6 8 4 6 3 4 6 7 2 7 11 2 9 10 1 4 1 6 7 4 7 11 3 7 10 4 5 3 3 7 3 6 11 2 5 10 3 6 2 8 7 5 6 11 6 4 10 6 7 1 7 12 4 7 17 6 8 16 3 8 2 6 16 2 5 23 3 9 19 2 9 7 5 12 1 6 17 1 8 16 1 10 6 4 16 2 5 23 2 7 19 2 11 7 5 16 4 7 23 3 9 19 3 12 5 8 18 3 3 26 4 6 21 3 13 6 9 21 3 7 30 2 5 24 4 14 7 5 24 2 3 32 4 6 26 4 15 8 8 26 3 7 36 3 6 29 5 16 9 3 29 4 6 39 3 8 33 3根据设计的蚁群算法的思想，在迭代次数NC＝100，挥发系数ρ＝0.1，偏重因子α＝0.3，β＝8的设置下可以得到一个可行的调度计划，见表2.由表2可知，项目组的总的完成时间为61 d，比文献［11］少1d，说明此算法的设计在资源受限的多项目调度方面存在一定的优势，能够提高企业的项目调度效率.4 结束语针对资源受限的多项目调度问题的特征，运用串行进度生产机制和蚁群算法的基本思想，设计出一种混合的蚁群算法.为了避免蚁群算法的停滞现象，该算法采用最大最小蚁群算法中对信息素的浓度进行限制的方法，从而有效的提高算法较优解的选取.通过实例的演算与分析发现此算法能够较好的解决RCMPSP问题.表2 资源约束下的调度计划 d项目1项目2项目3 ST FT ST FT ST FT 0 4 0 5 4 8 5 8 14 20 8 14 8 10 20 22 14 15 18 22 20 23 14 18 18 21 20 22 14 17 18 23 23 29 14 20 26 30 30 36 23 26 31 33 36 39 29 31 27 28 33 34 27 28 31 33 39 41 30 32 33 37 41 44 30 33 35 38 44 48 32 35 38 41 48 50 35 39 41 43 50 54 39 41 45 48 54 57 41 45 48 52 57 61 45 49参考文献［1］BROWNING T R，YASSINE A A.Resource－constrained multi－projectscheduling：priority rule performance revisited［J］.International Journal of Production Economics，2010（2）：212－228.［2］WILEY V D，DECKRO R F，JACKSON Jr J A.Optimization analysis for design and planning of multiproject programs［J］.European Journal of Operational Research，1998（2）：492－506.［3］GONCALVES J F，MENDES J J M，RESENDE M G C.A genetic algorithm for the resource constrained multi－project scheduling problem ［J］.European Journal of Operational Research，2008（3）：1171－1190. ［4］应瑛，寿涌毅，李敏.资源受限多项目调度的混合遗传算法［J］.浙江大学学报：工学版，2009（1）：23－27.［5］李敏.资源约束下多项目调度问题遗传算法研究［D］.杭州：浙江大学，2008.［6］VALLS V，BALLESTIN F，QUINTANILLA S.A hybrid genetic algorithm for the resource－constrained project scheduling problem［J］.European Journal of Operational Research，2008（2）：495－508.［7］林琳，姚郁.多资源约束下的多项目作业调度问题研究［J］.哈尔滨工业大学学报，2007（7）：1045－1049.［8］REMY J.Resource constrained scheduling on multiple machines ［J］.Information Processing Letters，2004（91）：177－182.［9］杨铭，王凯，李原，等.基于改进型粒子群算法的航空多项目调度方法［J］.火力与指挥控制，2010（2）：55－58.［10］MCRKLC D，MIDDCNDORF M，SCHMCCK H.Ant colony optimization for resource－constrained project scheduling［J］.IEEE Transactions on Evolutionary Computation，2002，6（4）：333－318.［11］廖仁，陈庆新，毛宁.模具虚拟企业项目调度遗传算法研究［J］.计算机集成制造系统，2004（7）：80－84.［12］KELLEY J E.The critical path method：resources planning and scheduling［J］.New Jersey Industrial Scheduling USA：Prentice Hall，1963（1）：347－365.。
