车间作业调度问题的染色体非完整表示方法

Chromosome with incomplete representation for Job shop scheduling problems

提出了一种用于解决车间作业调度问题的新的遗传染色体编码方法———非完整编码。其特征是基因数少于工序数。剩余基因采用简单的启发式规则方法进行解码。考证结果表明,非完整表示方法能够在合理的时间内得到临近最优解,通过删除高冗余和很少有实际意义的尾部基因,可以使遗传更有效。

We present genetic algorithm with an incomplete representation and apply it to the Jobshop scheduling problems.The important characteristic lies in that the number of genes is less than the number of operations.The rest of the schedule is completed by a simple heuristic rule.The results imply that the nearly best solution can be found in a national time interval by incomplete genes presentation.And incomplete genes presentation make the genetic algorithms more efficient by canceling high redundancy at the tail of the chromosome and little significance of rear genes.