摘要
作业调度问题 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.
出处
《南开大学学报（自然科学版）》
CAS
CSCD
北大核心
2008年第2期98-102,共5页
Acta Scientiarum Naturalium Universitatis Nankaiensis
基金
国家自然科学基金(70572045)
关键词
作业调度
遗传算法
双目标
调整算子
全局收敛性
JSP
genetic algorithm
double objective
adjustment operator
global convergence
