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

多目标柔性作业车间调度问题算法设计

作　者: 卢太苹
导　师: 黄荷姣
学　校: 哈尔滨工业大学
专　业: 计算机科学与技术
关键词: 作业车间调度 Petri网 遗传算法
分类号: TP301.6
类　型: 硕士论文
年　份: 2009年
下　载: 128次
引　用: 0次
阅　读: 论文下载
 

内容摘要


调度问题具有很长的研究历史,同时又分为好多类型,如流水车间、作业车间等。其中作业车间调度问题是一类满足任务配置和顺序约束要求的资源分配问题,是最困难的组合优化问题之一。柔性作业车间调度是作业车间调度的扩展调度问题,它比经典作业车间调度更贴近实际生产,同时也更复杂,它可以这样描述:给定一个工件的集合和一个机器的集合,每个工件又由若干道工序组成;每道工序需要在多台给定的机器上非间断地加工一段时间,每道工序同一时刻只能在一台机器上加工,每台机器同一时刻最多只能加工一道工序。调度的目的是寻找一个解决方案,这个方案满足时间跨度最小、成本最低、库存最小和设备利用率最高等目标。时间跨度、总提前期和总延迟时间是本文的三个主要优化目标。本文主要对单个资源的柔性作业车间调度进行建模和分析,并且针对单资源共享问题,给出共享合成后系统的特征以及满足的特性。调度问题是NP问题,求得最优解是调度问题的难点,因此更多的时候是退而求其次求得次优解或是一个方法所能得到的所有解中的最优解。本文使用时间Petri网对柔性作业车间调度问题进行建模,对所建立的模型进行死锁和资源竞争分析,最后使用改进的遗传算法对调度问题模型进行求解。本文使用遗传算法对调度问题的Petri网模型进行求解,使用变迁的激发序列对染色体进行编码,交叉、变异等遗传算法的操作都是对Petri网的基本元素进行操作,和空间元素无关,克服了空间状态爆炸问题。该方法适用于求解任何可以使用Petri网描述的调度问题,从而提高了算法的通用性。同时,本文提出了基于成本的多目标调度问题的解决方案,把要优化的目标统一转化为总成本,使用成本来评价解的优劣更为直观,更能体现企业生产者的愿望。本文针对具体的调度实例,分别使用普通遗传算法和自适应遗传算法进行了模拟。仿真实验表明,本文所提出的建模以及求解方法,可以有效地解决柔性作业车间调度问题。

全文目录


摘要  4-5
Abstract  5-10
第1章 绪论  10-18
  1.1 课题来源  10
  1.2 课题研究的背景和意义  10-11
  1.3 车间调度问题的特点及性能指标  11-12
    1.3.1 车间调度问题的特点  11
    1.3.2 车间调度的性能指标  11-12
  1.4 车间调度方法  12-13
    1.4.1 运筹学方法  12
    1.4.2 启发式方法  12-13
  1.5 本文相关内容研究现状及发展趋势  13-16
    1.5.1 柔性作业车间调度及其研究现状  13-14
    1.5.2 Petri 网应用背景及在调度问题中的应用现状  14-15
    1.5.3 FJSP 的发展趋势  15-16
  1.6 本文的内容和组织安排  16-18
    1.6.1 本文的内容  16-17
    1.6.2 本文的结构  17-18
第2章 Petri 网导论  18-26
  2.1 引言  18
  2.2 Petri 网基本概念  18-21
  2.3 Petri 网的运行规则  21-22
  2.4 Petri 网的基本性质  22-23
  2.5 几种扩展Petri 网  23-25
    2.5.1 时间Petri 网  23-24
    2.5.2 颜色Petri 网  24
    2.5.3 概率Petri 网  24-25
    2.5.4 容量Petri 网  25
    2.5.5 抑制弧Petri 网  25
  2.6 本章小结  25-26
第3章 遗传算法  26-34
  3.1 遗传算法的产生与发展  26
  3.2 基本遗传算法  26-30
    3.2.1 遗传算法的基本概念  26-27
    3.2.2 遗传算法的设计  27-28
    3.2.3 遗传算法的基本步骤  28-30
  3.3 自适应遗传算法  30-32
    3.3.1 自适应遗传算法的原理  30-31
    3.3.2 参数的自适应调整  31-32
  3.4 遗传算法的特点  32-33
  3.5 本章小结  33-34
第4章 柔性车间调度建模与求解  34-43
  4.1 引言  34
  4.2 柔性作业车间调度  34-35
  4.3 问题建模  35-36
  4.4 系统模型分析  36-39
    4.4.1 系统死锁分析  36-37
    4.4.2 系统冲突分析  37-38
    4.4.3 系统模型具有的性质  38-39
  4.5 基于Petri 网模型的遗传算法设计  39-42
    4.5.1 编码  39
    4.5.2 适应度函数  39-40
    4.5.3 初始化种群  40
    4.5.4 选择  40-41
    4.5.5 交叉  41-42
    4.5.6 变异  42
  4.6 本章小结  42-43
第5章 实际问题测试分析  43-50
  5.1 引言  43
  5.2 问题描述  43
  5.3 建模  43-45
  5.4 使用遗传算法求解  45-48
  5.5 本章小结  48-50
第6章 基于成本的多目标调度问题的研究  50-57
  6.1 引言  50
  6.2 问题描述  50-51
  6.3 具体调度实例分析  51-54
  6.4 可视化模块的设计  54-56
  6.5 本章小结  56-57
结论  57-58
参考文献  58-61
攻读硕士学位期间发表的学术论文及其它成果  61-63
致谢  63

相似论文

  1. 基于差分进化算法的JSP环境下成套订单研究,F273
  2. 天然气脱酸性气体过程中物性研究及数据处理,TE644
  3. 压气机优化平台建立与跨音速压气机气动优化设计,TH45
  4. 移动计算环境下检查点技术研究与Petri网建模,TP301.1
  5. 基于遗传算法的模糊层次综合评判在高职教学评价中的应用,G712
  6. 部队人员网上训练与考核系统的开发,TP311.52
  7. 基于并行算法的模糊综合评价模型的设计与应用,TP18
  8. 基于神经网络的牡蛎呈味肽制备及呈味特性研究,TS254.4
  9. 基于遗传算法的中短波磁天线的设计及实现,TN820
  10. 基于遗传算法的柑橘图像分割,TP391.41
  11. 基于混合自适应遗传算法的动态网格调度问题研究,TP393.09
  12. 基于遗传—牛顿算法的公交优化调度,TP18
  13. 基于遗传算法优化的BP网络对生物柴油制备工艺的优化,TE667
  14. 基于云理论和蜜蜂进化型遗传算法的纹理合成研究,TP391.41
  15. 基于遗传算法和粗糙集的聚类算法研究,TP18
  16. 基于遗传算法的淠史杭灌区渠系配水优化编组模型的研究,S274
  17. 基于逻辑Petri网的Web服务组合建模与分析,TP393.09
  18. 遗传算法在物流仓储优化中的应用研究,F259.2
  19. 基于遗传算法的矿山资源优化调度模型的研究,O224
  20. 磁流变阻尼器的力学特性及其在火炮反后坐中的应用研究,TB535.1
  21. 模糊预测函数控制改进算法的研究及应用,TP273

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com