学位论文 > 优秀研究生学位论文题录展示

基于高级死锁检测的制造系统生产调度研究

作　者: 史文博
导　师: 吴智铭
学　校: 上海交通大学
专　业: 控制理论与控制工程
关键词: 离散制造系统高级死锁调度有向图模型缓冲区回溯Benchmark Problems Makespan
分类号: TH165
类　型: 硕士论文
年　份: 2009年
下　载: 35次
引　用: 1次
阅　读: 论文下载

内容摘要

在当今的制造领域,越来越多柔性制造系统已经取代了传统的大批量单一种类加工制造系统,而现代企业也越来越多地把柔性制造系统作为提高他们竞争能力的有效手段。因此,怎样能够更好的控制柔性制造系统的加工流程,使得系统中的工件能够更快速,更安全的完成加工流程一直以来都是学术界和工业界关注的重点之一。在这种高度自动化的柔性制造系统中,资源高度共享。当工件进入系统并竞争有限资源时,如果缺乏有效的调度和控制方法,就会发生死锁现象。死锁现象会给自动制造系统的生产能力带来巨大的损失,因此对死锁的有效处理是获得高生产率的必要条件。然而过去大部分的研究者的研究工作总是以系统中有无限缓冲区为前提的,即使系统中出现死锁现象,也能够通过对缓冲区的使用来解决死锁问题,因此死锁问题并没有引起足够重视。然而一些新型的制造领域由于空间的限制或者其他方面因素的考虑,无法配备足够的缓冲区甚至根本没有缓冲区。比如,大型客机头部的制造,由于客机头部的体积太大,不可能在制造过程中配备足够的缓冲区。另外,半导体芯片的光刻加工车间中往往也没有缓冲区的存在,芯片只要进入系统就肯定被放置某一个加工机器上。因此,在这些系统中,死锁问题就是不得不考虑的一个影响系统调度的重要因素。过去的一些研究者对简单的死锁现象已经有着比较深入的研究,但是对于更为复杂的潜在死锁(高级死锁)仍然没有好的解决方法。除了以制造系统为背景的实际问题中存在死锁现象,死锁同样是一个经典的理论问题,特别是在计算机科学研究中,死锁的研究经常被用来作为验证计算机软件是否能够正常工作的手段之一。因此本文以制造系统为背景,运用有向图模型对制造系统进行建模,并基于有向图模型提出了高级死锁的检测算法。该算法能够有效地检测出系统中的二级死锁和三级死锁,从而能够提前避免死锁的发生。此外,基于该死锁检测算法以及改进深度搜索方法和一些启发式规则,本文分别针对有限缓冲区制造系统提出了新的在线调度算法用来改进调度结果的Makespan以及针对无缓冲区制造系统提出了一种新的无死锁调度算法。后者能够在很短的时间内获得大规模制造系统的无死锁调度结果,从而解决了大规模制造系统无死锁调度的难题。本文的最后部分,将本文介绍的调度算法应用于研究者们常用的Job-Shop Discrete Manufacturing Systems Benchmark Problems,实验得出的数据很好的证明了本文调度算法的良好效果。因此,希望本文对死锁问题的探索以及提出的调度算法能够被应用于现实的制造系统当中,并且对其他的离散事件系统死锁问题有良好的启示作用。

全文目录

摘要  5-7
ABSTRACT  7-12
第一章柔性制造系统简介  12-18
  1.1 柔性制造技术的产生  12
  1.2 柔性制造系统的组成和特点  12-15
    1.2.1 柔性制造系统的组成  12-14
    1.2.2 柔性制造系统的特点  14-15
  1.3 柔性制造系统的级别和适用范围  15-16
  1.4 柔性制造系统的优势  16-17
  1.5 柔性制造系统中的死锁问题  17
  1.6 本论文的组织结构  17-18
第二章制造系统车间调度问题  18-24
  2.1 车间调度的重要性  18
  2.2 车间调度的分类  18-20
  2.3 车间调度的研究  20-21
  2.4 调度优先规则和启发式方法  21-23
    2.4.1 分派规则和优化目标  22
    2.4.2 启发式方法仿真调度  22-23
  2.5 死锁研究在调度问题上的重要性  23
  2.6 本章小节  23-24
第三章柔性制造系统中的死锁问题  24-34
  3.1 前言  24
  3.2 死锁问题的定义及特点  24-27
  3.3 解决死锁问题的策略  27-28
  3.4 制造系统建模方法及其对应的死锁描述  28-34
    3.4.1 Petri 网方法  29-31
    3.4.2 图论方法  31-33
    3.4.3 自动机方法  33-34
  3.5 本章小结  34
第四章基于有向图模型的高级死锁检测  34-49
  4.1 前言  34-35
  4.2 有向图模型  35-36
  4.3 一级死锁  36-37
  4.4 潜在死锁环  37-39
  4.5 二级死锁  39-42
    4.5.1 二级死锁定义和一般形式  39-40
    4.5.2 二级死锁的一般结构  40-41
    4.5.3 二级死锁的检测算法  41-42
  4.6 三级死锁  42-45
    4.6.1 三级死锁定义  42
    4.6.2 三级死锁的一般形式  42-45
    4.6.3 三级死锁的检测算法  45
  4.7 高级死锁  45-47
  4.8 本章小结  47-49
第五章基于高级死锁检测的离散制造系统生产调度  49-64
  5.1 有限缓冲区离散制造系统生产调度  50-56
    5.1.1 前言  50
    5.1.2 拥有中心缓冲区的离散制造系统生产调度  50-54
    5.1.3 启发式节点生成程序  54-55
    5.1.4 清空缓冲区程序  55-56
  5.2 无缓冲区离散制造系统无死锁调度  56-62
    5.2.1 前言  56-57
    5.2.2 无死锁调度算法  57-62
  5.3 本章小结  62-64
第六章制造系统调度算法仿真实验  64-77
  6.1 有限缓冲区制造系统调度算法实验  64-69
  6.2 无缓冲区制造系统无死锁调度算法实验  69-76
  6.3 本章小结  76-77
第七章总结与展望  77-79
A. 附录  79-83
  A.1 无死锁调度算法步骤  79-80
  A.2 二级死锁检测算法步骤  80-81
  A.3 三级死锁检测算法步骤  81-83
参考文献  83-86
致谢  86-87
攻读硕士学位期间已发表或录用的论文  87

基于高级死锁检测的制造系统生产调度研究

内容摘要

全文目录

相似论文