文献类型：会议论文

英文题名：Minimizing Total Tardiness on Parallel Machines Based on Genetic Algorithm

作者：Wang, Chengyao[1];Li, Zhan[1];Zhu, Shuqin[1]

第一作者：王成尧

通讯作者：Wang, CY[1]

机构：[1]Beijing Union Univ, Teacher Coll, Dept Comp Sci & Technol, Beijing 110107, Peoples R China

第一机构：北京联合大学师范学院

通讯机构：[1]corresponding author), Beijing Union Univ, Teacher Coll, Dept Comp Sci & Technol, Beijing 110107, Peoples R China.|[1141711]北京联合大学师范学院;[11417]北京联合大学;

会议论文集：20th Chinese Control and Decision Conference

会议日期：JUL 02-04, 2008

会议地点：Yantai, PEOPLES R CHINA

语种：英文

外文关键词：Parallel machines; total tardiness; genetic algorithm; encoding space; solution space

摘要：The problem of scheduling jobs on parallel machines to minimize total tardiness is NP problem. The properties of p//(T) over bar problem were discussed. Base on the properties, the decoding function Block Decoding Algorithm (BDA) of Genetic Algorithm (GA) was designed. Between the encoding space and the solution space, the element numbers of the encoding space are not necessary large than elements of the solution space, It only necessary that at least one element in encoding space corresponds an optimal solution by the decoding function. The encoding space of this paper is n-list space which element is a permutation of n elements. It is proved that at least one optimal solution is corresponded to a permutation of encoding space by the BDA. By the computational experiments, The performance of GA is best than four Heuristic Algorithms (WI,DS,TPI,KPM).