基于混合遗传算法的资源受限的运输任务调度  

Resource-constrained transport task scheduling based on hybrid genetic algorithm.

作　　者：王剑[1] 王红卫[1] 

机构地区：[1]华中科技大学系统工程研究所

出　　处：《计算机工程与应用》2007年第31期34-38,共5页Computer Engineering and Applications

基　　金：国家自然科学基金( the National Natural Science Foundation of China under Grant No.70671045)

摘　　要：在利用串行调度启发式方法解决资源受限的运输任务调度问题(RCTTSP)的基础之上,提出了一种混合遗传算法(HGA)。该算法通过对运输任务执行优先次序进行基因编码,利用串行调度方法获得初始种群,并在遗传个体调度目标值与适应值确定的过程中使用了局部搜索启发式规则,从而充分地结合了遗传算法的全局搜索与启发式方法的局部搜索能力。首先对RCTTSP进行了描述,给出了混合遗传算法的基本原理,然后针对测试案例进行实现,并与单纯使用串行调度方法进行了比较。结果显示,该混合遗传算法能有效地改进调度效果。This paper proposes a Hybrid Genetic Algorithm （HGA） based on a serial scheduling heuristic method to solve the Resource-Constrained Transport Task Scheduling Problem（ RCTTSP ）.The proposed HGA uses transport task priority-based chromosome encoding,generates the initial population with the serial method,and applies the local search-based heuristic rules to evaluate individual＇s target value and fitness,in order to combine the global search ability of GA and the local search ability of heuristic method.Firstly,this paper describes the RCTTSP and presents the principle of the HGA,and then develops the algorithm with several experimental cases,lastly the HGA is contrasted with the serial method.The analytical result shows that the proposed HGA can improve the scheduling result with serial method efficiently.

关 键 词：资源受限 运输任务调度 混合遗传算法 启发式方法 串行调度 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]