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  HTML
摘要:

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

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.

出版日期: 2010-02-26
:  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/eng/CN/10.3785/j.issn.1008-973X.2010.01.010        http://www.zjujournals.com/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.

No related articles found!