用改进的遗传算法求解作业调度问题  

An Approach to JSP by Improved Genetic Algorithm

作　　者：陈飞[1] 王秀峰[1] 

机构地区：[1]南开大学信息技术科学学院,天津300071

出　　处：《南开大学学报（自然科学版）》2008年第2期98-102,共5页Acta Scientiarum Naturalium Universitatis Nankaiensis

基　　金：国家自然科学基金(70572045)

摘　　要：作业调度问题 JSP(Job Shop Scheduling Problem)是典型的组合优化问题.文中用改进的遗传算法来解决作业调度问题,在遗传算法中设计了一种调整算子,并证明了算法能够收敛到全局最优解;同时提出一种新的求解 JSP 问题的双目标函数、双种群遗传算子.每个种群侧重一个目标,各从不同侧面深度挖掘问题的信息,用以优化问题的解,两个种群再通过混合交叉得到更好的解,较大地提高了算法的收敛速度.This paper presents a new improved genetic algorithm （GA） which aims at solving JSP （Job Shop Scheduling Problem） in which a new adjustment operator is introduced such that the chromosomes satisfy the constraints more but not completely. Moreover, we use Markov chain to prove the global convergence of this new genetic algorithm. Based on which, we design an approach including double objectives and double population, which use the information from different points, to solve the JSP more efficiently. Finally, a simulation is presented to show the validity of the proposed approach.

关 键 词：作业调度 遗传算法 双目标 调整算子 全局收敛性 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]