一种求解多模式资源受限项目调度问题的蚁群算法  

ACO for Solving MMRCPSP

作　　者：彭武良[1] PENG Wuliang(School of Economics and Management,Shenyang Ligong University,Shenyang 110168)

机构地区：[1]沈阳理工大学经济管理学院,沈阳110168

出　　处：《信息系统学报》2009年第1期1-10,共10页China Journal of Information Systems

基　　金：国家自然科学基金资助项目(60604025)。

摘　　要：多模式资源受限项目调度问题是一种著名的NP完全问题,本文提出了一种求解该问题的蚁群算法。相对于现有算法,该算法采用规则池管理和使用大量优先级规则,提升了算法的通用性和性能。另外,每只蚂蚁被赋予自治能力、学习能力和预判能力。自治能力体现在每只蚂蚁具有单独的线程,学习能力体现在蚂蚁可以动态选择更好的优先级规则,预判能力体现在蚂蚁能够通过分支定界的方法排除不可行路径。最后利用PSPLIB标准问题对算法进行了大量的仿真测试,取得了令人满意的结果。An ant colony optimization(ACO)algorithm for solving multi-mode resource-constrained project scheduling problem(MMRCPSP),which is a well-known NP hard problem was presented.Compared with the existing studies,the algorithm uses a priority rule pool to manage a large number of priority rules.In addition,each ant is endowed with autonomous ability,learning ability and pre judgment ability.The autonomous ability is that each ant is provided with a single thread,the learning ability is that each ant can dynamically select the excellent priority rules,and the pre judgment ability is that each ant can avoid the non-feasible routes based on the branch and bound method.Finally,a full factorial computational experiment was set up using the well-known standard instances in PSPLIB,and computational results reveal that the algorithm is effective for MMRCPSP.

关 键 词：多模式资源受限项目调度问题 计划与调度 蚁群算法 

分 类 号：TP91[自动化与计算机技术]