基于大小蚁群与超立方体的资源受限项目调度算法  

Resource Constraint Project Scheduling Algorithm Based on Max-min Ant Colony and Hyper Cube

作　　者：张霞[1,2] 刘华光[2] 张静妙[1] 

机构地区：[1]河北经贸大学计算机中心,石家庄050061 [2]河北经贸大学经济管理学院,石家庄050061

出　　处：《控制工程》2016年第5期648-655,共8页Control Engineering of China

基　　金：国家自然科学基金重点项目(61333002);河北省科技计划项目(14457419D)

摘　　要：软件开发项目调度需考虑员工薪水、技能等多个因素,是一种资源有限型项目调度问题,复杂度较高,对此提出一种基于大小蚁群与超立方体的调度算法,优化了项目的工期与总成本。根据项目子任务的不同优先级建立有向图结构,全局最优蚂蚁与单轮迭代最优蚂蚁交替更新路径信息素,提高样本多样性;利用超立方体框架简化大小蚁群算法,并为蚁群设置两个启发信息,提高收敛速度。实验结果表明,本算法的优化效果与求解成功率均优于同类型算法。Software project scheduling needs to consider the salary of employees, skills etc. It is a very complex resource constraint problem, an algorithm based on max-min ant colony and hyper cube is proposed for solving this problem, and the project duration and total cost are optimized by the proposed algorithm. The directional graph is constructed based on the sub-tasks which have different priority, the pheromone trails of the path are updated by the global optimal ant and iterated optimal ant alternately to enhance the diversity of the individuals. The hyper cube is used to simplify the max-min ant colony algorithm, and two heuristic information are set for ant colony to speed up the converge. Experiment results show that the optimal results and hit rates of the proposed algorithm are both better than the other algorithms.

关 键 词：蚁群优化 超立方体 软件项目 调度算法 工期 成本 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]