运用遗传算法解决平行机台最小总拖期问题  

MINIMIZING TOTAL TARDINESS ON PARALLEL MACHINES BASED ON GENETIC ALGORITHMS

作　　者：王成尧[1] 赵东岩[1] 肖建国[1] 

机构地区：[1]北京大学计算机研究所电子出版新技术国家工程研究中心,北京100871

出　　处：《信息与控制》2003年第5期418-421,共4页Information and Control

摘　　要：最小化平行机台总拖期问题 (p∥ T)是调度领域中的一个NP问题 ,本文运用GA算法寻求该问题的近似优解 .本文证明在GA算法中为了找到问题的最优解 ,编码空间可以小于解集空间 .根据这个思想 ,在GA的编码空间设计中 ,本文分析了平行机台最小化总拖期问题的特性 ,设计了编码空间和解码方式以保证在编码空间存在最优解 ,减小搜索范围 .最后 ,本文通过数值仿真对该方法与一些启发式算法进行了比较 。In this paper, near optimal solutions to scheduling jobs on parallel machines to minimize the total tardiness ( p∥ ), which is an NP problem, are addressed by a Genetic Algorithm. It is proved in this paper that the encoding space may be smaller than the solution space for finding an optimal solution in a GA algorithm. Based on this articulation and analysis of properties of the p∥ problem, the encoding space and decoding function are deliberately designed to reduce the searching efforts. Finally, the GA algorithm presented in this paper is compared with some heuristics through numerical examples, and the result shows that the GA algorithm is superior over others methods.

关 键 词：遗传算法 最优解 平行机台 最小化总拖期问题 目标函数 

分 类 号：O242.23[理学—计算数学]