基于主动调度的编码方法及其在JSP中的应用

在对Jobshop问题进行具体描述的基础上,分析了目前利用遗传算法解决Jobshop问题的各种常用的编码方法,提出了一种新的编码方法.该编码方法与主动调度的构成步骤相结合,编码中基因的排列顺序就表示各工序的优先调度顺序,由此产生可行的调度方案,基于该编码方法是以不可重复的自然数为基因进行编码,在遗传操作过程中能采用类似TSP的遗传算子,从而避免了非法调度解的出现.采用该编码方法在遗传算法求解Jobshop问题的过程中,既能满足Jobshop问题的特性,又能体现遗传算法的较强的搜索能力.仿真结果也充分证明了该算法的有效性.

An Encoding Method Based on Active Schedule and Its Application to JSP

Based on describing the Job-shop scheduling problem concretely, various of common encoding methods are analyzed and a new encoding method is presented in this paper. This encoding method combines with the active schedule constructing steps and gene's order denotes priority dispatching sequence. Therefore, the feasible schedules are found. Because this encoding puts natural number into code, the genetic operators are similar to TSP, thus the illegal schemes are avoided. During the course of solving the Job-shop scheduling problem with Genetic Algorithm, this encoding not only can satisfy the characteristic of the Job-shop scheduling problem, but also can manifest the high ability of global optimization of Genetic Algorithm. The simulation results show that this algorithm is effective and efficient.