多维0／1背包与遗传算法的网格调度研究  

Research of Grid Scheduling for Multidimensional 0-1 Knapsack and Genetic Algorithm

作　　者：蒋勇[1,2] 谭怀亮[1] 

机构地区：[1]湖南大学计算机与通信学院,长沙410083 [2]湖南化工职业技术学院信息系,株洲412004

出　　处：《科学技术与工程》2009年第5期1160-1164,共5页Science Technology and Engineering

基　　金：湖南省自然科学基金(07JJ6139)资助

摘　　要：首先分析了网格调度的代价和成本,设计出一个将多目标、多约束的网格任务转换成单目标、单任务的0/1背包的网格调度模型。提出使用多维0/1背包与改进的二重结构编码的遗传算法的方法来求解网格最优调度,并通过编程实现其算法,经实验验证该算法优于基本的遗传算法。Firstly, price and cost of grid scheduling are analysed. Secondly, a grid scheduling model is designed which changed a multi-objective and multi-restraint grid tasks into a single objective and single task 0/1 knapsack problem. In order to solve grid optimal scheduling, a method which utilized the multidimensional 0-1 knapsack and improved the structure of the double-coded genetic algorithm, and implemented its algorithm through the programming are presented . After the experimental verification,it is superior to the simple genetic algorithm.

关 键 词：多维0-1背包 遗传算法 网格调度 最优解 

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