Please wait a minute...
浙江大学学报(工学版)
J4  2010, Vol. 44 Issue (1): 51-55    DOI: 10.3785/j.issn.1008-973X.2010.01.010
计算机科学技术     
多目标资源受限项目调度的多种群蚁群算法
寿涌毅,傅奥
（浙江大学 管理学院,浙江 杭州 310058）
Multi-colony ant algorithm for multi-objective resource- constrained project scheduling
SHOU Yong-yi, FU Ao
(School of Management, Zhejiang University, Hangzhou 310058, China)
 全文: PDF 
摘要：

为实现资源受限项目调度的多目标优化,通过改进传统蚁群算法,提出适用于多目标优化的多种群蚁群算法.该算法基于串行进度生成机制,每个蚁群具有各自的目标函数、与目标函数相匹配的不同搜索策略以及各自的信息素更新机制.各蚁群独立进行搜索决策,但各蚁群之间存在信息素的相互作用,从而实现加速搜索.针对多目标资源受限项目调度问题设计新的精英策略.在目标规划基础上构造一系列多目标项目调度算例,经系统测试表明,所提出的多种群蚁群算法能够有效优化资源受限项目的资源配置,实现多目标优化.
关键词： 项目调度;  资源约束;  蚁群算法;  多目标优化    
Abstract:

A new ant algorithm was proposed to take advantage of multiple ant colonies in order to solve the multi-objective resource-constrained project scheduling problem. The proposed algorithm utilizes the serial schedule generation scheme to construct project schedules stage by stage. Each ant colony has its own objective function, a corresponding searching strategy and pheromone update mechanism designed for the specific function. The ant colony searches for better schedules individually, and meanwhile they share their pheromone information so as to improve the searching efficiency. A new elitist strategy was also designed for the multi- objective problem and integrated into the pheromone update mechanism. A series of multi-objective project scheduling instances were constructed using goal programming. Systematic computational tests showed that the proposed multi-colony ant algorithm can allocate constraint resources effectively to achieve the multi-objective optimization．
Key words: project scheduling    resource constraint    ant colony algorithm    multi-objective optimization
出版日期: 2010-02-04
:  TB 114.1  
基金资助:

国家自然科学基金资助项目（70401017）.
作者简介: 寿涌毅（1974-），男，浙江诸暨人，副教授，博士，从事项目管理与技术管理研究.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
寿涌毅
傅奥

引用本文:

寿涌毅, 傅奥. 多目标资源受限项目调度的多种群蚁群算法[J]. J4, 2010, 44(1): 51-55.

SHOU Chong-Yi, FU Ao. Multi-colony ant algorithm for multi-objective resource- constrained project scheduling. J4, 2010, 44(1): 51-55.

链接本文:

http://www.zjujournals.com/xueshu/eng/CN/10.3785/j.issn.1008-973X.2010.01.010    或    http://www.zjujournals.com/xueshu/eng/CN/Y2010/V44/I1/51

［1］ VIANA A, SOUSA J. Using metaheuristics in multi-objective resource constrained project scheduling ［J］. European Journal of Operational Research, 2000, 120(2): 359-374．
［2］ ABBASI B, SHADROKH S, ARKAT J. Bi-objective resource-constrained project scheduling with robustness and makespan criteria ［J］. Applied Mathematics and Computation, 2006, 180(1): 146-152．
［3］ 熊鹰,匡亚萍. 施工项目工期-成本优化问题的蚁群算法［J］. 浙江大学学报：工学版, 2007, 41(1): 176-180．
XIONG Ying, KUANG Ya-ping. Using ant colony algorithm to solve construction time-cost trade-off problem ［J］. Journal of Zhejiang University: Engineering Science, 2007, 41(1): 176-180．
［4］ SLOWINSKI R. Multiobjective project scheduling under multiple-category resource constraints ［C］∥ Advances in Project Scheduling. Amsterdam: Elsevier, 1989．
［5］ MERKLE D, MIDDENDORF M, SCHMECK H. Ant colony optimization for resource-constrained project scheduling ［J］. IEEE Transactions on Evolutionary Computation, 2002, 6(4): 333-346．
［6］ KAWAMURA H, YAMAMOTO M, SUZUKI K, et al. Multiple ant colony algorithm based on colony level interactions ［J］. IEICE Transactions on Fundamentals, 2000, 83-A(2): 371-379．
［7］ 郏宣耀,藤少华. 双种群改进蚁群算法［J］. 计算机辅助工程, 2006, 15(2): 67-70．
JIA Xuan-yao, TENG Shao-hua. Dual population ant colony optimization algorithm ［J］. Computer Aided Engineering, 2006, 15(2): 67-70．
［8］ HANSEN M P, JASZKIEWICA A. Evaluating the quality of approximations to the nondominated set ［R］. Lyngby: Technical University of Denmark, 1998．
［9］ PATTERSON J H. A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem ［J］. Management Science, 1984, 30(7): 854-867．
［10］ 郑超,高连生. 蚁群算法在资源受限项目调度问题中的应用［J］. 计算机工程与应用, 2005, 41(27): 205-209．
ZHENG Chao, GAO Lian-sheng. Applications of ACO algorithm in resource-constrained project scheduling problems ［J］. Computer Engineering and Applications, 2005, 41(27): 205-209．
［11］ KOLISCH R, PADMAN R. An integrated survey of deterministic project scheduling ［J］. Omega, 2001, 29(3): 249-272．
［12］ SPRECHER A, KOLISCH R, DREXL A. Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem ［J］. European Journal of Operational Research, 1995, 80(1): 94-102．
[1] 余洋, 夏春和, 胡潇云. 采用混和路径攻击图的防御方案生成方法[J]. 浙江大学学报(工学版), 2017, 51(9): 1745-1759.
[2] 李建丽, 丁丁, 李涛. 基于二次聚类的多目标混合云任务调度算法[J]. 浙江大学学报(工学版), 2017, 51(6): 1233-1241.
[3] 张俊红, 张玉声, 王健, 徐喆轩, 胡欢, 赵永欢. 考虑热机耦合的排气歧管多目标优化设计[J]. 浙江大学学报(工学版), 2017, 51(6): 1153-1162.
[4] 任逸飞, 陆志强, 刘欣仪, 张猛. 考虑技能水平的多技能资源约束项目调度[J]. 浙江大学学报(工学版), 2017, 51(5): 1000-1006.
[5] 杨姝, 刘国平, 亓昌, 王大志. 金属空心球梯度泡沫结构抗冲击特性仿真与优化[J]. 浙江大学学报(工学版), 2016, 50(8): 1593-1599.
[6] 夏玉峰, 任莉, 叶彩红, 王力. 基于RSM的立柱加强板定位布局多目标优化[J]. 浙江大学学报(工学版), 2016, 50(8): 1600-1607.
[7] 过晓芳,王宇平,代才. 新的混合分解高维多目标进化算法[J]. 浙江大学学报(工学版), 2016, 50(7): 1313-1321.
[8] 张俊红,郭迁,王健,徐喆轩,陈孔武. 塑料机油冷却器盖加强筋参数的多目标优化[J]. 浙江大学学报(工学版), 2016, 50(7): 1360-1366.
[9] 杨辉华, 谢谱模, 张晓凤, 马巍, 刘振丙. 求解多目标优化问题的改进布谷鸟搜索算法[J]. 浙江大学学报(工学版), 2015, 49(8): 1600-1608.
[10] 何雪军, 王进, 陆国栋, 陈立. 基于蚁群算法的机器人图像绘制序列优化[J]. 浙江大学学报(工学版), 2015, 49(6): 1139-1145.
[11] 过海,倪益华,王进,陆国栋. 车用空调冷凝器性能多目标优化方法[J]. 浙江大学学报(工学版), 2015, 49(1): 142-159.
[12] 寿涌毅, 彭晓峰, 李菲, 赖昌涛. 抢占式资源受限项目调度问题的遗传算法[J]. 浙江大学学报(工学版), 2014, 48(8): 1473-1480.
[13] 何忠华,袁一星. 基于剩余能量熵的供水管网可靠性优化设计[J]. 浙江大学学报(工学版), 2014, 48(7): 1188-1194.
[14] 刘业峰，徐冠群，潘全科，柴天佑. 磁性材料成型烧结生产调度优化方法及应用[J]. J4, 2013, 47(9): 1517-1523.
[15] 虞介泽,李聪,张土乔,毛欣炜. 改进的水质服务水平与加氯费用优化分析[J]. J4, 2013, 47(7): 1140-1147.