双资源动态作业调度优化问题研究.doc

摘 要 车间作业调度问题（Job Shop Scheduling Problem）是生产制造系统研究的核心和重点内容之一，它对于提高资源利用率、提高生产率、提高产品质量、缩短产品交货期、降低生产成本、提高企业在市场中的竞争力具有非常重要的现实意义。 本文以加工周期为求解目标，基于遗传算法对受双资源制约的车间作业调度问题进行了研究。首先对车间作业调度问题和遗传算法进行了描述；其次分别给出了受单资源和双资源制约的静态调度问题的数学模型和求解过程；然后给出了动态事件的扰动分类，分别给出了机器故障、插入紧急工件、人员离岗三种典型动态事件的求解方法，并通过甘特图给出调度结果；最后通过实例对上述调度问题进行分析，表明本文提出的方法是有效的、可行的。 关键词：车间作业调度(JSP)；遗传算法；动态调度；双资源；甘特图  Abstract Job shop scheduling problem is the core of manufacturing systems. It can improve the resource utilization, improve productivity, improve the overall quality of products, shorten product delivery time and lower production costs. It has very important practical significance to improve enterprise in a market economys competitivenes. Make-span is used for the solving target in this paper. Job shop scheduling problem with dual resource constrained is studied based on genetic algorithm. Firstly, the job shop scheduling problem and genetic algorithms are described. Secondly, the mathematical model and solution procedure are given for the static scheduling problems with single resources and dual resource constraints. And then, the dynamic job shop scheduling is classified according to machine breaking down, urgent jobs coming, and working leaving. The scheduling results are given with gantt graph. Finally, the method proposed is tested through some examples, and the results show that it is effective and feasible. Keywords: Job shop scheduling problem (JSP); genetic algorithm; dynamic scheduling; dual-resource; gantt graph. 目录 摘 要 I Abstract II 1 绪论 1 1.1 引言 1 1.2 车间调度现状与优化方法 1 1.3 车间调度的发展趋势 6 1.4 遗传算法在车间调度中的应用 7 1.5 本文研究的意义 8 1.6 论文研究的主要内容及组织结构 9 2 作业车间调度问题 10 2.1 车间调度问题描述 10 2.2 车间调度问题的特点 10 2.3 车间调度问题的研究方法及策略 11 2.4 车间调度问题的分类 13 2.4.1 Job Shop 与Flow shop 比较 13 2.4.2 静态调度与动态调度 14 2.4.3 单一加工路线Job Shop调度问题 14 2.4.4 柔性Job Shop调度问题 16 3 遗传算法理论 18 3.1 遗传算法概述 18 3.2 遗传算法的发展与现状 19 3.3 遗传算法的基本概念 20 3.4 遗传算法的过程和流程 21 3.5 求解JSP调度问题的遗传算法 23 3.5.1 遗传算法的设计步骤 23 3.5.2 编码方式 23 3.5.3 适配值函数 27 3.5.4 遗传算子的设计 27 3.5.5 算法参数 29