基于多目标的量子粒子群算法应急调度问题研究

VIP免费
3.0 陈辉 2024-11-19 5 4 1.19MB 66 页 15积分
侵权投诉
目 录
中文摘要
ABSTRACT
第一章 绪 论 .................................................................................................................1
§1.1 课题的来源及意义 .............................................................................................. 1
§1.2 多目标优化算法的研究现状 .............................................................................. 2
§1.3 本文的内容安排 .................................................................................................. 5
第二章 生产调度问题及其优化方法 ............................................................................ 7
§2.1 调度问题的表述及其发展过程 .........................................................................7
§2.2 生产调度问题的描述与分类 .............................................................................7
§2.2.1 生产调度问题的描述 ......................................................................................7
§2.2.2 生产调度问题分类 ............................................................................................ 9
§2.3 生产调度问题的特点 ....................................................................................... 11
§2.4 生产调度问题的优化方法 ...............................................................................12
§2.5 本章小结 ...........................................................................................................12
第三章 量子粒子群算法的基本原理和研究进展 ...................................................... 13
§3.1 引言 ...................................................................................................................13
§3.2 粒子群算法 ......................................................................................................... 13
§3.2.1 粒子群算法的原理 .......................................................................................... 13
§3.2.2 粒子群算法基本流程 ...................................................................................... 14
§3.2.3 基本粒子群算法的社会行为分析 ................................................................. 15
§3.3 量子粒子群算法 ...............................................................................................17
§3.3.1 量子计算相关理论 ........................................................................................17
§3.3.1.1 量子位的表示方法 ....................................................................................... 17
§3.3.1.2 量子计算的基本特性 .................................................................................. 18
§3.3.2 量子粒子群优化算法 ....................................................................................19
§3.3.2.1 量子进化算法 .............................................................................................19
§3.3.2.2 量子粒子群优化算法 .................................................................................20
§3.4 本章小结 ...........................................................................................................24
第四章 多目标优化的量子粒子群算法 ...................................................................... 25
§4.1 多目标优化问题描述 .......................................................................................25
§4.2 多目标量子粒子群算法 ...................................................................................26
§4.2.1 多目标量子粒子群优化算法粒子的比较及个体极值选取策略 ................. 27
§4.2.2 多目标量子粒子群优化算法全局极值选取策略 ......................................... 28
§4.2.3 PARETO 最优解集的构造策略 .......................................................................28
§4.2.4 约束处理策略 ................................................................................................29
§4.3 多目标量子粒子群算法实现步骤 ................................................................. 30
§4.4 算法实验 ...........................................................................................................32
§4.5 本章小结 ...........................................................................................................32
第五章 基于多目标的柔性作业车间调度问题研究 ................................................ 33
§5.1 引 言 ................................................................................................................. 33
§5.2 问题描述 ...........................................................................................................33
§5.3 求解方案 ...........................................................................................................34
§5.4 仿真实验 ...........................................................................................................36
§5.5 本章小结 ...........................................................................................................38
第六章 基于不确定加工时间和随机机器故障的多目标流水车间应急调度问题研
究.....................................................................................................................................39
§6.1 引 言 ................................................................................................................. 39
§6.2 问题描述 ...........................................................................................................40
§6.3 求解方案 ...........................................................................................................43
§6.4 实例求解 ...........................................................................................................44
§6.5 本章小结 ...........................................................................................................47
第七章 基于 MQPSO 的紧急订单调度问题研究 ....................................................49
§7.1 引 言 ................................................................................................................. 49
§7.2 问题描述和模型建立 .......................................................................................50
§7.3 滚动窗口再调度 ...............................................................................................51
§7.4 应急调度算法设计及流程 ...............................................................................53
§7.5 实例求解 ...........................................................................................................54
§7.6 本章小结 ...........................................................................................................56
第八章 总结与展望.................................................................................................... 57
参考文献 .........................................................................................................................59
第一章 绪论
1
第一章 绪 论
§1.1 课题的来源及意义
随着经济的发展和社会的进步，先进制造业以逐渐成为国民经济的物质基础
和工业化的产业结构主体，被认为在民富国强的发展道路上起着举足轻重的作用。
新中国成立 60 多年来，特别是改革开放 30 余年来的发展成果告诉我们，我国以
国内巨大的消费市场需求为基础，并制定了一系列十分优惠的对外政策，吸引了
大量的资金和外国的优秀技术，经济规模也迅速走在了世界的前列，国力增强，
经济实力和国际地位明显得到增强。
科学技术的发展和进步，把制造业也带入了信息化和电子化的新时代。制造
业的竞争也日渐激烈和白热化。而资源匮乏、产品多样化和个性化要求的提高、
JIT
生产方式的推出，都使制造业面临着越来越多的困难和挑战。利用有限的资源配
置，通过合理控制和有效降低生产成本、缩短生产和制造周期、确保及时和准时
交货，来不断发掘新的经济效益和社会效益生长点，不断提高市场占有率和社会
信誉，成为摆在各个企业面前的严峻话题。
开展企业生产调度的研究，就是企业根据具体的生产环境的约束条件下，出
于优化生产目标的目的，为工件的加工制定科学合理有效的加工序列，合理分配
加工资源、科学调配加工时间、统筹制定操作环节等，使产品的制造时间或者成
本等执行目标达到最优化或者近似优化的满意状态，业已成为制造业企业生产管
理的核心和关键环节，它直接关系着企业的产出效率和生产成本，有效的计划与
调度算法结合详细准确的外围信息能最大限度地提高企业的效益，满足客户的需
求，最终提高企业的竞争力和发展力。
生产调度问题涉及到应用数学、生产管理、运筹学、人工智能和计算机科学
等诸多学科交叉，其实际的生产调度问题因为其自身具有的诸多复杂性，例如多
约束性、多目标性、不确定性、动态随机性、大规模、多极小等特点，已被证明
是属于 NP-hard 问题，也使其成为具有较高难度的研究热点。
传统的对于生产调度的研究基本都是在基于确定性的前提条件下开展的，例
如确定的工件集合、确定的加工时间、稳定连续的加工设备等等。但是在实际生
产中，随机环境下的生产才是正常真实的情况。例如作业到达时间的不确定性、
作业加工时间的随机性、机器故障、库存不足、交货期变化或模糊等情况，都对
实际的调度提出了更大的挑战。本文中对这类不确定性条件下的生产调度问题称
为“应急调度”。
基于多目标的量子粒子群算法应急调度问题研究
2
而一般生产调度的目标性能指标可以是成本最低，可以是降低库存费用，可
以是缩短生产周期，也可以是提高设备的利用率等。调度目标大致可以分为以下
三类：[1]
（1）最大化生产能力。包括最大生产率、最短生产周期等，可以概括为在固
定或无限的产品需求下，最大化生产能力以提高经济效益。
（2）最小化生产成本。包括最大化利润、最小化运行费用、最小投资和最大
收益等。
（3）最大化客户满意度。包括最短的拖期延迟、最小化交货提前或者拖后惩
罚等。
实际的生产调度还因为诸如社会、经济、生产等客观环境条件的变化，其调
度优化目标、寻优策略等均不尽相同。对这种多目标性的、应急性的生产调度的
研究一直以来都是一种未能很好解决的理论难题，也吸引了国内外众多学者和一
线生产调度人员的关注和探讨。
粒子群优化算法（Particle Swarm Optimization，PSO）是 1995 年由 Kennedy
工程师和 Eberhart 博士等[2,3]提出来的，他是一种基于种群搜索和群体进化的自适
应迭代计算技术。这种新型的算法对问题最优化解的搜索是通过种群间的粒子个
体协作来完成和实现的。而基于量子进化思想与粒子群算法相结合的量子粒子群
算法（Quantum Particle Swarm Optimization，QPSO），利用量子理论中的叠加
态特性，来保证种群保持多样性，通过量子旋转门来完成粒子的位置和速度的更
新。该算法基于具有计算简单、容易实现、收敛速度快和调整参数少等优点，相
比传统的粒子群算法具有更好的稳定性和收敛性。
近年来，量子粒子群算法作为一种新兴的群智能优化算法，被很多学者应用
于求解多目标优化问题，取得了理论和现实上的验证，取得了一定的研究成果。
本文将建立基于多目标的量子粒子群算法的实数编码模型，尝试解决应急调度的
两目标优化问题，也为该算法处理多目标优化问题作出参考。
§1.2 多目标优化算法的研究现状
多目标优化问题（Multi-objective Optimization Problem，MOP）的最早出现，
可以追溯到18世纪70年代。Franklin于1772年提出多目标矛盾如何协调的问题。而
国际上一般公认的最早正式提出多目标优化问题是法国的经济学家V．Pareto在
1896年提出的。当时他从政治经济学的角度，把很多不便于比较的目标总结为多
目标优化问题。1944年，Von．Neumann和J．Morgenstem又从博弈论的角度，提出
多个决策而又彼此互相矛盾的多目标决策问题。1951年，T．C．Koopmans从生产
第一章 绪论
3
与分配的活动分析中提出了多目标优化问题，并且第一次提出了Pareto最优解的
概念。1968年，Z．Johnsen系统地提出了关于多目标决策模型的研究报告，这是
多目标最优化这门学科开始发展的一个转折点，这也是对Pareto正式提出的多目
标优化问题的系统总结和提升。到现在为止，多目标最优化不仅在理论上取得很
多重要成果，而且在应用领域上也越来越显示出它的强大生命力。
多目标优化问题中的各个目标可能是通过决策相互制约，对其中一个目标的
优化可能就要以牺牲其他目标为代价，又往往由于度量单位的不一致，想客观的
评价多目标问题解的方案的优劣性是非常难的。与单目标优化的本质区别就在于，
多目标问题的解方案不是唯一的，而是存在一个最优解的集合，即所谓的Pareto
最优解集或非劣解集。所谓Pareto最优解意义在于，找不到一个解，可以使至少
一个目标更优而其他目标不被劣化。
多目标优化对技术工程师和学者来说都是一个非常重要的研究课题，不仅因
为大多数问题都具备多目标的特征，而且在科学研究和工程实践中许多优化问题
都与多目标优化相关。过去的几十年间，在数学界和运筹学界，涌现出了很多种
方法来处理具有多个优化目标的多目标问题。
早在1967年，Rosenberg在其博士学位论文中就曾提到可用遗传算法求解多目
标优化问题，但直到1985年，Schafferf[4]研究多目标优化问题时，提出向量评价
的遗传算法(Vector Evaluated Genetic Algorithm，VEGA)，至此开创了用遗传
算法求解多目标优化问题的先河。
多目标进化算法经过1985年—1994年的缓慢发展期、1994年—2003年的快速
发展期和之后的全面发展期，现如今已经发展成为进化算法应用研究的热点之一，
同时，它已成为介于进化计算与经典多目标优化领域的一个独立的分支。除传统
的简单加权聚集法（将多目标问题转化为单目标优化问题，然后用单目标优化问
题的方法求解）之外，根据算法思想是否使用Pareto占优的概念可将其分为基于非
Pareto的方法和基于Pareto的方法两类。前一类方法的典型代表有Schaffer提出的
VEGA、Fourman[5]的基于字典序方法、极大极小方法等等。
基于
Pareto
方法的基本思想是基于“Pareto最优个体”的概念对群体中的各个
个体进行排序，依据排序次数来进行选择计算依据，使得排在前面的
Pareto
最优个
体优先进入下一代群体中，这样经过若干代数的迭代之后最终可以获得多目标优
化命题的
Pareto
解集。其典型算法包括MOGA、NSGA等。
对于多目标进化算法的设计与理论探究，国内也呈现出硕果渐丰、方兴未艾
的情况。在算法设计方面，孙艳丰等[6]将遗传算法（GA）用于多目标0-1规划问题；
王宇平等[82.83]结合正交设计、均匀设计与遗传算法等理论，给出了求解多目标优
基于多目标的量子粒子群算法应急调度问题研究
4
化问题的混合计算新方法，并从理论和算例上证明了其全局收敛性；崔逊学[7-10]
在对多目标进化算法开展系统的研究的基础上，提出了多目标协调进化算法，这
种算法可以求解高维多目标优化问题；雷德明等[11] 提出了多目标混沌进化算法，
算法思想是通过混沌变量在适应度 最大的几个个体附近搜索新的最后个体，引导
种群迭代进化。
近十多年来，已发表多篇多目标调度的综述论文。Nagar等[12]对1990年以前有
关常规性能指标的研究进行了回顾，他们只讨论了四种类型的问题：单机双目标
问题、单机多目标、多机双目标和多机多目标问题。T’kindt等[13]针对100多篇论文，
也只讨论了三种类型的问题：单机作业车间、并行机作业车间和流水车间。
Hoogeveen[14]专门研究了一些特殊调度问题，如提前-拖后（E/T）调度、具有可控
加工时间的调度、同时逼近和新模型等。Lei[15]对多目标确定性调度和多目标不确
定调度的研究进行了详细回顾，指出了未来研究的新趋势。
1995年以来发表了多目标生产调度方面的论文90多篇，涉及到的主要方法有
EA、GA、TS、SA、GP、ACO、DE、启发式算法、局部搜索和规划方法等。大
部分已发表论文研究确定性调度，多目标模糊调度的研究相对较少，而多目标随
机调度的文献更少。由于实际生产调度问题大多数同时具有不确定性和多个冲突
目标，对多目标模糊或随机调度的研究值得人们在未来进行深入的思考和研究。
Sun等人于1994年基于量子力学的理论基础，提出了一种新的PSO算法模型，
这种模型以DELTA势阱为基础，认为粒子可表现出量子行为，并进一步根据这种
模型提出了基于量子行为的粒子群优化算法(Quantum Particle Swarm
Optimization,QPSO)[4]，在量子空间中，粒子可以在整个可行区域内进行搜索，因
而QPSO算法具有更好的全局搜索性能。之后，QPSO算法受到人们的广泛关注，
QPSO算法也被应用于解决各类复杂的NP-hard问题当中。例如旅行商问题（TSP）
等经典组合优化问题的求解当中，并取得了一定的研究成果。
同时，作为一种新型的优化方法，量子粒子群算法在解决多目标优化问题方
面也显示出很好的性能。Moore[16]在强化个体和群体的搜索能力方面作出了成绩，
Ray[17]通过把Pareto占优及进化计算的思想引入到微粒群算法，设计了可行的多目
标优化算法，并通过设计拥挤度来保持个体的多样性；Parsopoulos[18]利用动态权
重提高算法的搜索能力；Hu在文献[19]中提出了采用动态邻域的思想，并采用类似
字典排序的方法，采用每次只针对一个目标函数进行优化的多目标优化思想来求
解。虽然取得了一定的成绩，但是总体来说，对于多目标的量子粒子群进化算法
的研究和应用仍处于起步发展阶段，一些理论问题仍然没有得到比较好的验证，
还缺乏非常权威的研究成果，有待深入的实践和探索。
摘要：

目录中文摘要ABSTRACT第一章绪论.................................................................................................................1§1.1课题的来源及意义..............................................................................................1§1.2多目标优化算法的研究现状...............................................

展开>> 收起<<
基于多目标的量子粒子群算法应急调度问题研究.pdf

共66页,预览7页

还剩页未读， 继续阅读

相关推荐

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

开通VIP享超值会员特权

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

作者详情

相关内容

更多

推荐作者

热门标签

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