基于微粒群算法的车间作业调度问题研究

VIP免费
3.0 陈辉 2024-11-19 4 4 1.9MB 79 页 15积分
侵权投诉
I
目 录
中文摘要
ABSTRACT
第一章 绪论 .....................................................................................................................1
§1.1 研究背景及意义 ....................................................................................................1
§1.2 国内外研究现状 ....................................................................................................2
§1.3 本文主要研究工作 ................................................................................................3
第二章 车间作业调度问题 ...........................................................................................4
§2.0 引言 ........................................................................................................................4
§2.1 调度问题及其描述 ................................................................................................4
§2.1.1 调度问题 .............................................................................................................4
§2.1.2 车间作业调度问题的特点 .................................................................................5
§2.1.3 车间作业调度问题的目标 .................................................................................6
§2.1.4 生产作业调度问题的类型 .................................................................................6
§2.1.5 Flow Shop 和Job Shop 调度问题 ..................................................................... 9
§2.2 排序问题的三参数分类法 ..................................................................................10
§2.3 工件加工描述 ......................................................................................................11
§2.3.1 工件加工资料和特性的描述 ...........................................................................11
§2.3.2 机器加工环境的描述 .......................................................................................12
第三章 微粒群算法的基本原理和算法分析 ...............................................................13
§3.0 引言 ......................................................................................................................13
§3.1 微粒群算法原理与流程 ......................................................................................14
§3.1.1 微粒群算法的原理 ...........................................................................................14
§3.1.2 算法流程 ...........................................................................................................15
§3.2 微粒群算法改进和分析 ......................................................................................16
§3.2.1 基本微粒群算法的社会行为分析 ...................................................................16
§3.2.2 与其它进化算法的比较 ...................................................................................17
§3.2.3 两种基本进化模型 ...........................................................................................18
§3.2.4 带惯性权重的微粒群算法 ...............................................................................19
§3.2.5 微粒群算法参数效能的统计分析 ...................................................................19
§3.3 微粒群算法的研究方向 ......................................................................................24
第四章 基于微粒群算法的 Flow Shop 调度 ............................................................... 25
§4.1 Flow Shop 调度问题描述 ................................................................................... 25
II
§4.1.1 Flow Shop 调度问题的假设条件及符号说明 ................................................ 25
§4.1.2 Flow Shop 调度问题的目标 ............................................................................ 27
§4.1.3 计算复杂性与 NP 完全问题 ........................................................................... 29
§4.1.4 Flow Shop 调度问题的发展过程及现状 ........................................................ 30
§4.2 Flow Shop 调度问题的模型表示 ....................................................................... 30
§4.2.1 Flow Shop 调度问题的几种解决方法 ............................................................ 30
§4.2.2 对几种主要的启发式方法的评价 ...................................................................31
§4.2.3 Flow Shop 调度问题模型表示 ........................................................................ 33
§4.3 Flow Shop 调度问题的微粒群算法编码方式 ................................................... 33
§4.3.1 基本微粒群算法的编码 ...................................................................................33
§4.3.2 Flow Shop 问题的编码 .................................................................................... 35
§4.3.3 求解 Flow Shop 调度问题的 PSO 算法 ..........................................................36
§4.4 改进的 PSO 算法及参数设置 ............................................................................ 37
§4.4.1 PSO 算法局部最优的解决方案 ...................................................................... 37
§4.4.2 微粒参数及终止条件 .......................................................................................37
§4.5 实例分析 ..............................................................................................................37
§4.5.1 编码 ...................................................................................................................37
§4.5.2 算法程序 ...........................................................................................................38
§4.5.3 实例数据及参数设置 .......................................................................................38
§4.5.4 结果分析 ...........................................................................................................38
第五章 基于微粒群算法的 Job Shop 调度 ..................................................................40
§5.0 引言 ......................................................................................................................40
§5.1 Job Shop 调度问题描述 ......................................................................................40
§5.1.1 Job Shop 调度问题的假设条件及符号说明 ...................................................40
§5.1.2 Job Shop 调度问题的目标 ...............................................................................41
§5.1.3 计算复杂性与可计算性 ...................................................................................41
§5.1.4 Job Shop 调度问题的发展过程及现状 ...........................................................43
§5.2 基于自适应变异的典型 Job Shop 调度问题 .....................................................48
§5.2.1 典型 Job Shop 问题数学描述 ..........................................................................48
§5.2.2 自适应变异的微粒群优化算法描述 ...............................................................49
§5.2.3 实例分析 ...........................................................................................................50
§5.3 基于混合微粒群的柔性 Job Shop 调度问题 .....................................................56
§5.3.1 问题描述 ...........................................................................................................56
§5.3.2 柔性 Job Shop 调度问题的几种解决方法 ......................................................56
III
§5.3.3 基于混合微粒群算法描述 ...............................................................................56
§5.3.4 实例分析 ...........................................................................................................62
第六章 结论与展望 ...................................................................................................66
附 录 .............................................................................................................................67
参考文献 .........................................................................................................................74
在读期间公开发表的论文和承担科研项目及取得成果 .............................................77
致 谢 .............................................................................................................................78
第一章 绪论
1
第一章 绪论
§1.1研究背景及意义
生产调度是制造系统的一个研究热点，车间作业调度是一个典型的 N-P Hard
问题，也是一个前沿性的研究课题已经受到学术界和工业界的广泛关注。柔性制
造系统作为一类复杂的人造系统，具有复杂性、递阶结构、不确定性、多目标、
多约束、多资源相互协调等特点。鉴于其重要的应用价值和理论意义，相关的分
析与控制的研究方法已受到工业界和控制界的广泛关注。
再者，随着加入 WTO，制造业竞争的加剧，制造业普遍面临着许多全球性问
题，自然资源日益匮乏，客户对产品的要求越来越多样化，产品的生命周期逐渐
缩短，产品的结构日益复杂，如何运用有限的资源，降低产品的生产成本，缩短
产品的制造周期，保证及时交货，提高企业信誉，赢得更多的客户，成为制造业
在竞争中生存的一个重要条件。有效的利用现有的资源，合理的制定企业和车间
生产计划，确保生产车间较高的生产能力和效率，是当务之急。
此外，有效的调度方法已经成为先进制造技术实践的基础和关键。以往的车
间调度工作时由生产管理人员手工完成的。随着经济的迅猛发展，产量的增加，
加上市场激烈竞争要求企业快速反应，排定企业作业计划光靠人工显然是不行的。
因为作业计划涉及到庞大的企业信息流，当人工经过一段时间排定完一份作业计
划时，因企业的动态情况，市场的需求又发生了变化，信息可能已经过时，这样
的手工方式是跟不上现代化生产需要的。排定一个作业计划要考虑规格、品种、
标准、工具、工艺路线、交付期等许多参数，工作量是相当庞大的，手工编制作
业计划不能实现制作计划的快速实时性，不能完成及时的信息反馈，不能与管理
计算机联网，不能实现整个企业的信息共享。优良的调度策略对于提高生产系统
的最优性、提高经济效益，有着极大的作用。
生产调度的制造系统的一个研究热点，也是理论研究中最为困难的问题之一。
调度的任务是根据生产目标和约束，为每个加工对象确定具体的加工路径、时间、
机器和操作等。优良的调度策略策略对于提高生产系统的最优性、提高经济效益，
有着极大的作用。目前，对调度理论的研究已受到广泛的关注，并取得了较大的
进展，但还是很不成熟。其中，对调度问题的复杂性研究已成为工程背景很强的
一个应用数学分支。在算法研究方面，基于知识的方法和算法技术相结合的趋势
正变得日趋显着，概率分析方法在算法效率和性能方面的研究日益增多。对于难
以求解的最优解的问题，给出多项式时间的搜索方法具有很大的现实意义，同样，
基于微粒群算法的车间作业调度研究
2
算法的随机性分析也是比较有效地分析手段。算法研究中，最优化性能的渐进性
分析具有理论指导性，而基于启发式算法的误差估计来确定次优解则无疑同样具
有很大的意义。由于约束条件的存在导致难以建立数学模型，纯数学的方法往往
不易奏效，也不易处理并发现象，因此，从工程中“满意”即可的实际需求出发，寻
求满足约束条件的快速有效的优化算法正变得更有现实意义。迄今，计算复杂性
理论表明，多数调度问题都属于 NP 难题，目标解的搜索涉及解空间的组合爆炸。
线性规划、动态规划、分支定界和梯度下降等传统方法，或是需要目标函数的特
殊信息，或是复杂度大，或是优化性能差，因而一般只能处理小规模问题，难以
高效高质量地求解复杂问题。
人们正是由于意识到基于计算和数值式的优化技术的弱点，以及调度问题的
约束性、非线性、不确定性、大规模性、多目标性等复杂性，才开始研究和发展
了统计式全局搜索技术和人工智能的方法，例如模拟退火、遗传算法、禁忌搜索、
进化规划、进化策略、神经网络方法、Lagrangian 松弛方法和混沌优化等。这些优
化算法通过模拟或揭示某些自然现象、过程和规律而得到发展，以人类认识和理
解客观事物的知识、经验等作为解决问题的方法，其思想和内容涉及数学、物理
学、生物进化、人工智能、神经科学和统计力学等，为解决复杂问题提供了新的
思路和手段。迄今，这些算法独特的优点、机制及其非凡的优化能力，引起了国
内外学者的广泛重视，并掀起了该领域的研究热潮，而且在诸多领域得到了成功
应用，较满意地解决了一大批传统优化方法难以解决的复杂问题。为此，国际上
已设立了相应的学术协会和诸多相关的学术期刊与会议。
微粒群算法是由美国社会心理学家 James Kennedy 和电气工程师 Russell
Eberhart 在1995 年共同提出的[1]，是继蚂蚁算法之后有一种新的群体智能算法，
目前已经成为进化算法的一个重要分支。微粒群算法自提出以来，在国外得到了
相关领域众多学者的关注与研究。CEC 国际年会上，微粒群算法被作为一个独立
的研究分支，与遗传算法、进化规划等进化算法相提并论。
§1.2 国内外研究现状
在1954 年，Johnson 对两台机床的 Flow Shop 型调度问题进行了研究后，便
开始了对调度问题的广泛研究。经过近 50 年的发展，车间调度问题的研究方法经
历了从简单到复杂、从单一到多元的过程，大体有如下几种类型:数学规划方法
（mathematical programming）、枚举方法与拉氏松弛法（lagrangian relaxation）、人
工智能技术、人工神经网络优化（neural network ，NN）、 遗传算法(genetic
algorithms)、邻域搜索技术中的模拟退火法（simulated annealing）和禁忌搜索法（tabu
第一章 绪论
3
search）、 离散事件动态系统(Discrete Event Dynamic System，DEDS)的解析模型、
Petri 网方法、启发式规则方法 、模糊逻辑的方法（fuzzy logic）、 基于仿真的方
法。
1995 年由美国社会心理学家 James Kennedy 和电气工程师 Russell Eberhart 共
同提出的微粒群算法自提出以来[1]，在国外得到了相关领域众多学者的关注和研
究。CEC 国际年会上，微粒群算法被作为一个独立的研究分支，与遗传算法。进
化规划等进化算法相提并论。据不完全统计，短短几年内，国外针对微粒群算法
研究完成的博士论文有十余篇；在进化计算。神经网络以及人工智能等 IEEE 的国
际学术会议上，均有众多论文涉及该领域。但是在国内在该领域的研究刚刚起步，
只是有些综述和介绍性的文章。将微粒群算法运用到生产调度研究中还是比较新
颖的，值得做进一步深入研究。
§1.3 本文主要研究工作
首先，介绍国内外有关车间作业调度问题的研究现状。包括车间作业调度问
题的基本概念、分类、研究水平等。
简述微粒群算法基本理论概述。包括微粒群算法的基本知识、基本思想、特
点、基本操作等。针对传统微粒群算法初始种群的选择，种群速度的定义，如何
保证种群的多样性，如何防止陷入局部最优解等问题，提出有效的改进方法。
针对特定的调度问题，
Flow Shop 和Job Shop 调度问题，运用微粒群算法求解
调度问题，针对以上求解算法存在的问题，与其他进化算法相结合，进一步分析
总结提出一种有效的混合微粒群算法，并与上述的算法结果进行较，做出可行性
与有效性分析。
最后，讨论车间作业调度问题的进一步研究方向。
摘要：

I目录中文摘要ABSTRACT第一章绪论.....................................................................................................................1§1.1研究背景及意义....................................................................................................1§1.2国内外研究现状..........................................

展开>> 收起<<
基于微粒群算法的车间作业调度问题研究.pdf

共79页,预览8页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：陈辉 分类：高等教育资料 价格：15积分 属性：79 页 大小：1.9MB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 79
评分 收藏
分享
立即下载 VIP免费下载
客服
关注