基于遗传算法求解Job Shop调度的编码新方法  

New encoding method for GA-based solution to Job Shop scheduling optimization

作　　者：周辉仁[1] 郑丕谔[1] 牛犇[1] 宗蕴[2] 

机构地区：[1]天津大学系统工程研究所,天津300072 [2]山东大学能源与动力学院,济南250100

出　　处：《计算机应用》2008年第2期294-296,304,共4页journal of Computer Applications

摘　　要：针对Job Shop调度问题,提出了一种新的遗传算法编码新方法。该方法根据问题的特点,采用一种按工序用不同编号进行的染色体编码方案,每一个编号包含工件工序号、对应的机器号、加工时间等所有信息,此编码与调度方案一一对应,并且该编码方案有多种交叉操作算子可用,不需要专门设计算子。算例计算结果表明,基于该编码方案的遗传算法是有效的,能适用解决Job Shop调度问题。通过比较,用该编码方案的遗传算法优化Job Shop调度操作简单并且收敛速度快。A new encoding method for a solution to genetic algorithm-based Job Shop scheduling problem was proposed. According to the characteristics of a specific problem, a job activities＇ number-dependent coding of chromosomes was designed, with each number including the number of a job activity of working parts, the number of a machine associated with the job activity, and all information in connection with duration of job activities. As a result, codes by the new encoding method correspond to the job scheduling schemed one-to-one and were able to match multiple cross operators without a special design of operators. Results from a case study show that the genetic algorithm with the help of new encoding method presents a powerful ability and＇ is able to effectively solve job shop scheduling problems. Through comparison, this algorithm has shown merits of simple operation and fast convergence.

关 键 词：JOB Shop调度 遗传算法 编码方法 工序 优化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP18[自动化与计算机技术—计算机科学与技术]