车间调度问题的遗传算法实现

摘   要

车间调度问题属于NP完全问题。目前调度问题的理论研究成果主要在集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。遗传算法是1种自适应全局优化概率搜索方法，现在很多研究者运用了遗传算法来试图解决车间调度问题。
本文从实际与理论两方面，研究了遗传算法在流水车间调度问题中的应用。在1般遗传算法的基础上设计了1个改进的遗传算法，来实现流水车间调度问题，并用数据实例验证算法的有效性。

关键词：车间调度；遗传算法；流水车间调度；改进遗传算法
 
Abstract

The Job-Shop Scheduling Problem  belongs to the complete problem of NP. At present, the results of the theories research in the scheduling problem are mainly focus on the scheduling problem which was based on the minimum time to finish the work. And the representative is the Job-Shop Scheduling Problem. Genetic Algorithm is a search meathod which can automatically adapt to the global optimization. Currently, a number of researches make use of the Genetic Algorithm to solve the Job- Shop Scheduling Problem.
   The thesis has researched the application of the Genetic Algorithm in the Flow-Shop Scheduling Problem both on the practice and theories. They have designed an improvement Genetic Algorithm on the basis of the usual Genetic Algorithm in order to carry out the Flow-Shop Scheduling Problem. And also they have validated the validity of this calculate through the real examples of data.
  
Keywords: The Job-Shop Scheduling ；Genetic Algorithm ；The Flow-Shop Scheduling；Improvement the Genetic Algorithm.