求解多处理机调度问题的蚁群算法  

Ant colony optimization algorithm for multiprocessor scheduling problem

作　　者：陈崚[1,2] 于广建[1] 缪旭波[3] 

机构地区：[1]扬州大学信息工程学院 [2]南京大学计算机软件新技术国家重点实验室,江苏南京210093 [3]国家环境保护总局南京环境科学研究所

出　　处：《计算机应用》2007年第2期442-445,452,共5页journal of Computer Applications

基　　金：国家自然科学基金资助项目(60673060);国家科技攻关项目(2003BA614A-14);江苏省自然科学基金资助项目(BK20005047);南京大学软件新技术国家重点实验室开放基金

摘　　要：蚁群算法是受自然界中的蚂蚁觅食行为启发而设计的智能优化算法,特别适合处理离散型的组合优化问题。提出一种求解多处理机调度的蚁群算法,利用一个蚂蚁代表一个处理机来选择任务,并通过分析关键路径及每个任务的最早、最迟开始时间来确定每个任务的紧迫程度,让蚂蚁以此来选择任务。实验证明,该算法可比传统算法取得有更好运行效率的调度策略。The ant colony optimization （ACO） algorithm is an intelligent optimization algorithm which simulates the ants＇ behaviors in searching for food. ACO is especially suitable for the discrete combination optimization problems. In this paper, we presented an ACO algorithm for multiprocessor scheduling problem. In the algorithm, each ant represented one processor and selected its tasks. The algorithm measured the urgency of each task by analyzing its critical path, the earliest and latest starting time. With the help of the obtained information, the ant selected the proper tasks for the processor it represented. Experimental results show our algorithm can obtain more efficient scheduling results than classical algorithms.

关 键 词：处理机调度问题 蚁群算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]