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

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (31): 34-38.

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

王剑^1,2,王红卫^1,2

1.华中科技大学系统工程研究所,武汉 430074
2.图像信息处理与智能控制教育部重点实验室,武汉 430074

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-11-01 发布日期:2007-11-01
通讯作者: 王剑

Resource-constrained transport task scheduling based on hybrid genetic algorithm

WANG Jian^1,2,WANG Hong-wei^1,2

1.Systems Engineering Institute,Huazhong University of Science and Technology,Wuhan 430074,China
2.Key Laboratory of Image Processing and Intelligent Control,Wuhan 430074,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-11-01 Published:2007-11-01
Contact: WANG Jian

摘要/Abstract

摘要： 在利用串行调度启发式方法解决资源受限的运输任务调度问题（RCTTSP）的基础之上,提出了一种混合遗传算法（HGA）。该算法通过对运输任务执行优先次序进行基因编码,利用串行调度方法获得初始种群,并在遗传个体调度目标值与适应值确定的过程中使用了局部搜索启发式规则,从而充分地结合了遗传算法的全局搜索与启发式方法的局部搜索能力。首先对RCTTSP进行了描述,给出了混合遗传算法的基本原理,然后针对测试案例进行实现,并与单纯使用串行调度方法进行了比较。结果显示,该混合遗传算法能有效地改进调度效果。

Abstract: 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.

王剑^1,2,王红卫^1,2. 基于混合遗传算法的资源受限的运输任务调度[J]. 计算机工程与应用, 2007, 43(31): 34-38.

WANG Jian^1,2,WANG Hong-wei^1,2. Resource-constrained transport task scheduling based on hybrid genetic algorithm[J]. Computer Engineering and Applications, 2007, 43(31): 34-38.