基于混合遗传算法的车间调度方法研究与应用.doc

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

摘  要

计算机集成制造系统(CIMS)在制造业的广泛实施带来了良好的经济效益，正成为当前国内外各大中型企业研究和实施的热点。管理自动化是CIMS的分系统，是现代制造工厂的重要促成部分，计算机辅助生产计划、作业调度与控制是管理自动化的核心技术。生产计划与调度系统作为实施CIMS工程中的一个重要组成部分，是CIMS功能结构模型中不可缺少的一个层次，它对企业生产管理与控制系统有着重要的影响调度。因此，车间作业调度研究也成为厂大学者的研究课题，具有重要意义。这一问题研究因其建模复杂性、计算复杂性、动态多约束、多目标性等特点，是组合优化问题范畴，被证明是典型NP困难问题，近几年各种H能计算方法逐渐被引入到作业调度问题中，如遗传算法、模拟退火算法、启发式算法等。
遗传算法(Genetic Algorithm GA)是演化计算方法中应用最厂泛之一，应用于全局搜索等参数优化计算领域，也适用于车间作业调度问题。它作为一种非确定性的拟生态随机优化算法在过去20年中得到了广泛的应用，由于其具有不依赖于问题模型的特性、全局最优性、随机转移性而非确定性、隐含并行性等特点，因此遗传算法更适合复杂问题的优化比其他优化技术相比存在显著的优势，正越来越激起人们的广泛研究与应用。
本文应用遗传算法求解复杂的车间调度问题。首先在第一章绪论中论述了车间调度问题的重要性及其研究现状、方法。紧接着在随后的几个章节分别介绍了遗传算法的理论基础，作业车间调度问题、流水车间调度问题、机器调度问题的描述、研究策略、及遗传算法求解时的编码方式和性能比较。在最后，简要地论述了本论文课题的进一步研究方向及其研究方法和策略。

关键词：生产调度，遗传算法，启发式，流水车间，作业车间

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 been proved as NP-hard problem. Many intelligent computation methods such as simulated Anneal Algorithm, Genetic Algorithm, heuristic algorithm, are introduced into scheduling problem in recent years.
As a method in eva luative computer field, GA is applied widely in parameter optimization such as global search. When it's applied in JSSP, there are several distinct merits compared with other methods. As an uncertain stochastic optimal algorithm, GA is applied in all kinds of fields in the past 20 years. And because of its independence, global optimization, and implicit parallelism in complex problem solving, GA is developed and applied in many fields by more and more people.
In this paper, GA is applied to solve complicated shop floor scheduling problem. The paper is divided into seven chapters. In the introduction, it states the significance, recent actuality and research methods of job shop scheduling problem. Then the succeed five chapters include the presentation of GA, the typical descriptions of job shop, flow shop, machine scheduling earliness-tardiness and virtual scheduling and its research strategy. The performance is compared when using different GA coding mode. The simulation scheduling results of several samples show GA's feasibility, reliability and validity in solving JSSP problems. The last chapter is conclusion and expectation and prospect of the research subject.

Key words: Production scheduling, Genetic Algorithm, Flow Shop, Job Shop.
 

目   录

摘  要 I
ABSTRACT II
1  引言 5
1.1 绪论 5
1.2 课题研究的目的和意义 5
1.3 国内外研究现状 6
1.4 课题的主要研究内容 7
2  车间调度问题的描述 8
2.1 车间调度问题的描述 8
2.2 车间调度问题的特点 9
2.3 车间调度问题的优化方法 9
2.4 车间调度问题的调度策略 11
    2.5 本章小结……………………………………………………………………………….12
3  遗传算法的简述 13
3.1 遗传算法的定义 13
3.2 遗传算法的生物学知识背景 14
3.2.1 达尔文生物进化论 14
3.2.2 孟德尔遗传学说 14
        3.2.3 DNA-遗传信息的载体………………………..………………………………… 15
3.3 遗传算法的基本思想 15
3.4 遗传算法的特点………………………………………………………………………..17
3.5 本章小结……………………………………………………………………………….17
4  经典车间调度问题 18
4.1 流水车间调度问题 18
4.1.1 概述 18
4.1.2 精确算法 19
4.1.3 启发式计算 20
4.2 作业车间调度问题 22
4.2.1 概述 23
4.2.2 古典作业车间调度模型 23
4.2.3 传统启发式 24
4.3 本章小结 27
5  基于遗传算法的作业车间调度问题 28
5.1 车间调度系统设计 28
        5.1.1 系统设计中的关键性问题………………………………………………………28
        5.1.2 调度系统设计的基本思想………………………………………………………29
        5.1.3 车间管理系统设计的基本思想…………………………………………………29
5.2 车间调度系统设计 30
        5.2.1 界面设计…………………………………………………………………………30
        5.2.2 程序设计…………………………………………………………………………31
5.3 本章小结……………………………………………………………………………….34
6  总结与展望……………………………………………………………………………...35
6.1 总结…………………………………………………………………………………….35
6.2 展望…………………………………………………………………………………….35
参考文献………………………………………………………….…………………………………………37
致谢……………………………………………………………………………………………...38