基于遗传算法的生产调度

摘 要

作业车间调度问题(Job-shop Scheduling Problem, 简称JSP)是一类满足任务配置和顺序约束要求的资源分配问题，是一类典型的NP-hard问题，至今没有找到可以精确求得最优解的多项式时间算法。有效地调度方法和优化技术的研究与应用，对于制造企业提供生产效率、降低生产成本有着重要的作用，因此越来越受学者们的关注。

遗传算法是基于“适者生存”的一种高度并行、随机和自适应优化算法，它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。

本文系统介绍了作业车间调度问题以及遗传算法的基本原理，并针对作业车间调度问题的特点，设计了一种遗传算法。最后使用Matlab编写程序求解Job Shop调度问题。并对两类典型的FT类问题FT06和FT10进行测试。

关键词：车间调度，遗传算法，Job Shop问题

I

Abstract

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 \adaptive optimization algorithm, it will solve the problem that a \of the survival of the fittest process, through \generation, including reproduction, crossover and mutation operations, and eventually converge to the \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

目录

目 录

摘 要 ···································································································· I Abstract ·································································································· II

第一章 绪论 ··························································································· 1

1.1车间调度研究的目的和意义 ······························································ 1 1.2 车间调度的研究现状 ······································································ 2 1.3 本文安排 ····················································································· 3

第二章 车间调度问题综述 ········································································· 4 2.1 车间调度问题 ··············································································· 4

2.1.1 车间调度问题的描述 ······························································ 4 2.1.2 车间调度的性能指标 ······························································ 4 2.1.3 车间调度问题的分类 ······························································ 5 2.1.4 实际调度问题的特点 ······························································ 5 2.2 车间调度问题的研究方法 ································································ 6 2.3 车间调度研究中存在的主要问题 ······················································· 9 2.4 本章小结 ····················································································· 9

第三章 遗传算法理论综述 ········································································ 10 3.1 遗传算法的形成和发展 ·································································· 10 3.2 基本遗传算法 ·············································································· 11 3.3 基本遗传算的实现技术 ·································································· 13

3.3.1 编码方法 ············································································· 13 3.3.2 适应度函数的确定 ································································ 14 3.3.3 选择算子 ············································································· 14 3.3.4 交叉算子 ············································································· 15 3.3.5 变异算子 ············································································· 15 3.3.6 算法参数的选取 ··································································· 16 3.3.7 算法终止条件的确定 ····························································· 16 3.4 遗传算法的应用 ··········································································· 17 3.5 本章小结 ···················································································· 17

第四章 Job Shop调度问题的遗传算法研究 ·················································· 18 4.1 Job Shop调度问题描述 ··································································· 18 4.2 Job Shop调度的参数设计 ································································ 19

4.2.1 基本流程图 ·········································································· 20 4.2.2 编码方式的确定 ··································································· 20 4.2.3 适应度函数 ·········································································· 21 4.2.4 遗传算子的设计 ··································································· 21 4.2.5算法参数的设计 ···································································· 22 4.3 Job Shop调度的Matlab实现 ···························································· 22