求解JSP的遗传算法中不可行调度的方案  

A Method to Resolve Unfeasible Scheduling of JSP by GA

作　　者：谢胜利[1] 黄强[2] 董金祥[2] 

机构地区：[1]温州师范学院计算机科学系,浙江温州325003 [2]浙江大学人工智能研究所,浙江杭州310027

出　　处：《计算机集成制造系统-CIMS》2002年第11期902-906,共5页

基　　金：国家教育部博士点基金资助项目 ( 2 0 0 0 0 33554 )~~

摘　　要：在作业车间调度问题中 ,存在大量的不可行调度解 ,严重影响了遗传算法查找最优调度的质量。本文通过作业车间调度问题数学模型的图论形式 ,深入分析了产生不可行调度的原因及其特征 ,得出了一个可行调度的充要条件。由此 ,提出了遗传算法求解作业车间调度新的编码方法 ,能够彻底避免产生不可行调度解 。There are a number of unfeasible scheduling solutions in the Job-shop Scheduling Problem(JSP), it seriously affects the quality of Genetic Algorithms(GA) searching for the best solution. We put forward the graphical theory model of JSP, and analyze the cause of unfeasible scheduling and its characteristic, then educe the sufficient and necessary condition that a feasible scheduling solution requires. We improve on the encoding schema of GA to solve JSP, it reduces occurrence of the unfeasible scheduling solution, then enhances the quality of GA .

关 键 词：JSP 遗传算法 作业车间调度问题 不可行调度 遗传编码 柔性制造系统 数学模型 

分 类 号：O224[理学—运筹学与控制论] TH165[理学—数学]