基于遗传算法的生产调度.doc

STYLEREF 标题 1 \* MERGEFORMAT Abstract PAGE I 摘 要 作业车间调度问题(Job-shop Scheduling Problem, 简称JSP)是一类满足任务配置和顺序约束要求的资源分配问题，是一类典型的NP-hard问题，至今没有找到可以精确求得最优解的多项式时间算法。有效地调度方法和优化技术的研究与应用，对于制造企业提供生产效率、降低生产成本有着重要的作用，因此越来越受学者们的关注。 遗传算法是基于“适者生存”的一种高度并行、随机和自适应优化算法，它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。 本文系统介绍了作业车间调度问题以及遗传算法的基本原理，并针对作业车间调度问题的特点，设计了一种遗传算法。最后使用Matlab编写程序求解Job Shop调度问题。并对两类典型的FT类问题FT06和FT10进行测试。 关键词：车间调度，遗传算法，Job Shop问题 Abstract Job shop scheduling problem (Job-shop Scheduling Problem, referred to as JSP) is a class of constraints to meet the tasks required to configure and order the allocation of resources.It is a kind of typical NP-hard problem, which has not found the optimal solution to get accurately obtained polynomial time algorithm. Effective methods and optimization techniques in scheduling research and applications, take an important role in manufactur enterprises production efficiency, reduce production costs, so more and more attention by scholars. Genetic algorithm is based on the survival of the fittest in a highly parallel, random and adaptive optimization algorithm, it will solve the problem that a chromosome of the survival of the fittest process, through chromosome group of evolving from generation to generation, including reproduction, crossover and mutation operations, and eventually converge to the best adapt to the environment, the individual, and thus obtain the optimal solution or a satisfactory solution. This paper introduced the job-shop scheduling problem and the basic principles of genetic algorithms, to sove job shop scheduling problem, we designed a genetic algorithm, and using Matlab programming sove Job Shop Scheduling Problem. Finally test two typical kinds of problems FT06 and FT10. Keyword: Production scheduling, Genetic algorithm, Job Shop problem 目录（续） 目录 目 录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc263979931 摘 要 PAGEREF _Toc263979931 \h I HYPERLINK \l _Toc263979932 Abs