基于微粒群算法的车间作业调度问题研究
VIP免费
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 调度问题，运用微粒群算法求解
调度问题，针对以上求解算法存在的问题，与其他进化算法相结合，进一步分析
总结提出一种有效的混合微粒群算法，并与上述的算法结果进行较，做出可行性
与有效性分析。
最后，讨论车间作业调度问题的进一步研究方向。
基于微粒群算法的车间作业调度研究
4
第二章 车间作业调度问题
§2.0 引言
车间作业调度问题长期以来一直是理论界研究的重点领域，随着国际市场上
产品竞争的日益加剧，企业界也因竞争的压力开始对该问题的研究投入极大的关
注。拥有良好的作业调度技术，可以提高企业的生产、经营和管理的效率，增强
企业的核心竞争力，特别是在全球经济一体化的大趋势下，对于加入 WT O 的中
国而言，研究作业调度问题更有深远的现实意义。另一方面，由于信息技术的发
展突飞猛进，越来越多的企业需要引入基于信息技术的复杂的生产制造与管理系
统，如 CIMS，AP S 等，这些新系统依赖于生产作业调度问题的理论与技术的突
破。当然，计算机技术也推动着该问题的研究向着新的方向发展。过去，理论界
传统的生产作业调度理论研究主要集中在运筹学、管理科学和工业工程领域中，
而最新的生产作业调度问题的研究己经大大拓宽，一个明显的特征是在该问题的
研究中广泛涉及模糊数学、系统模拟、进化计算、神经网络、专家系统、控制理
论等理论方法，也正是这些优化方法为作业调度理论的研究开辟了新的思路与空
间。
§2.1 调度问题及其描述
§2.1.1 调度问题
调度问题通[2]常指对生产过程的作业计划，譬如工件在机器上的加工顺序、生
产批量的划分等。就生产方式而言，调度问题可分为开环车间（Open Shop）型和
闭环车间（Closed Shop）型。开环调度问题，也称加工排序问题，它本质上只研
究工件的加工顺序，即订单所要求的产品在所有机器上的加工排序，其中订单均
来源于顾客，不考虑库存的设立。闭环调度问题除研究工件的加工顺序之外，还
涉及各产品批量大小的设置，即在满足生产工艺约束条件下寻找一个调度策略，
使得确定的生产批量和相应的加工顺序下的生产性能指标最优，其中顾客需求的
产品均由库存提供，生产任务一般只有产品存储策略决定。
显然，闭环调度问题要比开环调度问题复杂得多。鉴于批量大小和排序间的
耦合性，寻求批量大小和排序的有效同时处理的方案很困难，目前处理闭环问题
的常用近似方法是，首先确定批量大小，然后确定加工顺序。
对于m台机器（Machine）
}M,M,{M m21
对n个工件(job)
}J,J,{J n21
的加工
第二章 车间作业调度问题
5
过程，所谓调度就是分配各个工件在机器上的加工时间。调度通常用甘特图
(Genttchart)表示。
§2.1.2 车间作业调度问题的特点
车间作业调度是车间内部在短期内组织生产活动的行动依据。它与中长期生
产计划相比，具有两个特点:一是计划周期缩短，把中长期生产计划的计划周期逐
步细化到月、旬、周、日，甚至小时的具体计划:二是计划内容更加具体，把中长
期车间计划的各项指标层层落实到各车间、工段、班组、工作地甚至职工个人。
这些特点决定了进行作业调度时需根据中长期生产计划的要求和车间的具体情
况，把企业的计划任务与临时任务具体分配到各工段、班组、工作地以及职工个
人，规定他们在月、旬、周、日，甚至小时内应完成的产品品种、数量，投入产
出的期限与进度。
编制一个车间作业计划就是确定操作顺序、分配资源、制定批量标准。在实
际的作业调度工作中要注意考虑五个因素[3]:
(1)计划期的衔接
任何调度方案总是从某个时间点上开始执行，并跨越某个时段，它总是在前
一个调度方案的基础上进行调整和修订，因此，要注意调度的继承性、可扩展性
和兼容性。
(2)批量大小和换装成本
离散部件可分批生产，大批量可减少机器起动和换装次数，小批量则减少在
制品库存量和增加调度的机动性。一个好的调度方案应根据其目标和条件来灵活
确定其批量的大小。
(3)加工JIM序
在实际生产环境中，加工顺序是十分复杂的，甚至是动态变化的，因不同的
机器有不同的加工时间和加工特性(如新设备与旧设备，通用设备与专用设备等)，
因此，加工顺序依赖于机器的选择。一个好的调度方案应该对各种加工顺序有高
度的弹性。
(4)随机事件的扰动
在实际生产过程中有大量的随机事件，如急件、缺货、缺勤、机器故障，以
及加工时间和交货期的变化，都对生产调度方案产生影响。
(5)绩效准则和多项目标
企业管理的目标是寻求成本最小化、设备和资源利用最大化，而调度所追求
的目标往往也包括作业压力最小化(如提高计划稳定性、减少混乱、安抚客户)，从
摘要：
展开>>
收起<<
I目录中文摘要ABSTRACT第一章绪论.....................................................................................................................1§1.1研究背景及意义....................................................................................................1§1.2国内外研究现状..........................................
相关推荐
-
跨境电商商业计划书模版VIP免费
2025-01-09 27 -
跨境电商方案范文VIP免费
2025-01-09 14 -
创业计划书VIP免费
2025-01-09 18 -
xx生鲜APP计划书VIP免费
2025-01-09 12 -
跨境电商创业园商业计划书(盈利模式)VIP免费
2025-01-09 8 -
跨境电商计划书VIP免费
2025-01-09 13 -
绿色食品电商平台项目计划书VIP免费
2025-01-09 22 -
农产品电子商务商业计划书VIP免费
2025-01-09 9 -
农村电商平台商业计划书VIP免费
2025-01-09 13 -
生鲜商城平台商业计划书VIP免费
2025-01-09 21
作者：陈辉
分类：高等教育资料
价格：15积分
属性：79 页
大小：1.9MB
格式：PDF
时间：2024-11-19
