基于遗传算法的作业调度研究与应用

浙江大学,硕士学位论文,遗传算法,车间作业调度,机械工程

硕 士 学 位 论 文

论文题目 基于遗传算法的车间调度研究与应用

作者姓名 欧阳珍

指导教师 狄瑞坤 副教授

学科专业 机械制造及其自动化

所在学院 机械与能源工程学院

提交日期 二零零四年二月

浙江大学,硕士学位论文,遗传算法,车间作业调度,机械工程

浙 江 大 学

硕 士 学 位 论 文

基于遗传算法的车间调度研究与应用

姓 名 专 业 机械制造及其自动化

指导教师

浙江大学研究生院

二零零四年二月

浙江大学,硕士学位论文,遗传算法,车间作业调度,机械工程

A Dissertation Submitted to Zhejiang University

For the Degree of Master

The Research and Application on Job Shop

Scheduling Problem Based On GA

By

Ouyang Zhen

Advisors: Associate Prof. Di Ruikun

Zhejiang University

Hangzhou P.R.China, February 2004

浙江大学,硕士学位论文,遗传算法,车间作业调度,机械工程

摘要

计算机集成制造系统(CIMS)在制造业的广泛实施带来了良好的经济效益，正成为当前国内外各大中型企业研究和实施的热点。管理自动化是CIMS的分系统，是现代制造工厂的重要促成部分，计算机辅助生产计划、作业调度与控制是管理自动化的核心技术。生产计划与调度系统作为实施CIMS工程中的一个重要组成部分，是CIMS功能结构模型中不可缺少的一个层次，它对企业生产管理与控制系统有着重要的影响调度。因此，车间作业调度研究也成为广大学者的研究课题，具有重要意义。这一问题研究因其建模复杂性、计算复杂性、动态多约束、多目标性等特点，是组合优化问题范畴，被证明是典型NP困难问题，近几年各种智能计算方法逐渐被引入到作业调度问题中，如遗传算法、模拟退火算法、启发式算法等。

遗传算法(Geneti Algorithm，GA)是演化计算方法中应用最广泛之一，应用于全局搜索等参数优化计算领域，也适用于车间作业调度问题。它作为一种非确定性的拟生态随机优化算法在过去20年中得到了广泛的应用，由于其具有不依赖于问题模型的特性、全局最优性、随机转移性而非确定性、隐含并行性等特点，因此遗传算法更适合复杂问题的优化，比其他优化技术相比存在显著的优势，正越来越激起人们的广泛研究与应用

本文应用遗传算法求解复杂的车间调度问题。全文共分七个章节，首先在第一章绪论中论述了车间调度问题的重要性及其研究现状、方法。紧接着在随后的几个章节分别介绍了遗传算法的理论基础，作业车间调度问题、流水车间调度问题、机器调度问题的提前/拖期问题、虚拟车间作业调度问题的描述、研究策略、及遗传算法求解时的编码方式和性能比较，各章给出了具体实例，其仿真调度数据验证了遗传算法用于求解车间作业调度的可行性和有效性。最后在第七章总结及展望中简要的论述了本论文课题的进一步研究方向及其研究方法和策略。

在本论文课题的研究及应用过程中，作者做了以下主要研究工作和成果：

(1) 鉴于遗传算法容易出现过早收敛的问题以及局部搜索能力不强的问题，提出一种结合启发式算法改进的遗传算法，并将其运用于流水车间作业调度问题的求解。

(2) 针对混合流水车间调度问题，提出了一种基于遗传算法的求解方法，给出了染色体编码方法和相应的遗传算子，该编码方法使得遗传算法操作大大简化。

(3) 针对实际生产中存在的大量不确定性因素，研究了模糊流水线车间调度问题，并对嵌入领域搜索的混合遗传算法进行了仿真和结果比较。

(4) 对机器调度中的提前/拖期调度问题进行了描述，并将复杂的并行调度问题分成两个子问题，基于这种分解的思想，提出了一种基于遗传计算的解决策略，对各种不同规模的调度问题结果进行仿真。

(5)对CIMS系统中的虚拟车间调度作了简要的研究，设计了一种于回路调节原理的调度模型，可使虚拟车间融入整个生产网络，使之可成为一个动态、性能良好的生产系统。在此基础上，设计了一种调度算法，并用遗传算法对其求解。计算机模拟数据结果显示，该遗传算法能够较好地解决虚拟车间中调度问题。

关键词：生产调度，遗传算法，作业车间，流水车间，提前/拖期，虚拟调度

浙江大学,硕士学位论文,遗传算法,车间作业调度,机械工程

ABSTRACT

Computer Integrated Manufacturing System (CIMS) can greatly promote the synthesized economic profit of the enterprise when it is implemented widely in manufacturing fields, thus it has become the hotspot of research and implement in all kinds of enterprises. Management Automation System, one sub-system of CIMS, is an important part of modern manufacturing factory whose kernel technologies are CAPP, Job Shop Scheduling Problem (JSSP), etc, which are vital and indispensable. As a one part of enterprise produce system, JSPP affects it so much. So JSSP stirs many scholars’ research. JSSP characters as its complicated model construct and calculation, dynamic multi-restriction, and multi-objective. It is assemble optimization problem and has be …… 此处隐藏：22619字，全部文档内容请下载后查看。喜欢就下载吧 ……