基于量子微粒群算法的不确定条件下的生产调度问题

VIP免费
3.0 陈辉 2024-11-19 4 4 2MB 82 页 15积分
侵权投诉
摘 要
在制造系统中，生产调度问题是理论研究中最基本、最重要和最困难的问题
之一，以往近几十年的研究中，主要集中于纯确定型生产调度问题，对真实的生
产环境进行大量的限制、简化和假设。但随着市场竞争的日趋激烈，客户对产品
的要求越来越多样化，产品的生命周期逐渐缩短、产品的结构日益复杂等使得实
际的调度存在着大量的不确定因素，传统的模型难以得到满意的结果。
本文首先简要回顾了生产调度问题的分类及其调度方法的研究进展情况，分
析了在生产调度中存在的主要不确定因素：操作时间不确定性与交货期不确定性，
引入了模糊理论对其描述。着重介绍了量子微粒群算法的基本原理及算法流程，
该算法保留了微粒群算法的基本框架，并结合了量子计算的基本特性，如量子叠
加，量子旋转等。
其次，本文将量子微粒群算法用于求解几类典型的不确定条件下的生产调度
问题：多产品间歇调度、柔性的 Job-shop 调度、多资源约束的 Job-shop 调度以及
可重入的调度问题。文中针对这些生产调度问题的特点，设计了相应的解构造策
略，并利用 Visual C 编程仿真计算，通过分析，验证了本文算法求解生产调度优
化问题的可行性。
最后，对本文所做的工作及创新进行了总结，同时提出了文中的一些不足和
研究展望。
关键词:微粒群算法 量子计算 模糊生产调度
ABSTRACT
Production scheduling problem is the one of the most basic, important and difficult
theoretical research in a manufacturing system.In the past decades of research, most of
them mainly focused on purely deterministic production scheduling problem and
handled the real production environment with a large number of constraints, simplifying
and assumptions. But with the increasingly fierce market competition, customers have
become increasingly demanding product diversification, product life cycle is shorter and
more sophisticated structure of the product makes the actual scheduling a large number
of uncertainties, the traditional model has become difficult to obtain satisfactory results.
Firstly, this paper has a review of the studies of scheduling optimization problems
and the algorithm applied to solving the problems. This paper makes a analysis on the
uncertainties of production scheduling,mainly on uncertain operation time and uncertain
delivery time. Apply fuzzy theory to slove such uncertainties.This paper describes the
basic principle of quantum particle swarm optimization algorithm. It remains the model
of typical particle swarm optimization and introduces the quantum theory,such as
quantum cross-interference,quantum spin variation.
Secondly, this paper tries to solve the typical uncertain scheduling problems:
multiproduct batch plant scheduling,flexible Job-shop problem,multi-resource
constrained Job-shop problem and re-entrant scheduling problem. Then it makes
construction strategies to solve it. The paper simulates with Visual C. The results show
that this algorithm is feasibility.
Finally, this paper has a summarization of the work. At the same time, it brings
forward future research expectation.
Key Words: Particle Swarm Optimization Algorithm, Quantum
Theory, Fuzzy Production Scheduling
I
目 录
中文摘要
ABSTRACT
第一章 绪 论...................................................................................................................1
§1.1 课题的研究背景.............................................................................................1
§1.2 课题的国内外研究情况.................................................................................2
§1.2.1 量子微粒群算法国内外研究...............................................................2
§1.2.2 生产调度国内外研究...........................................................................4
§1.2.3 模糊调度的研究现状及发展情况.......................................................6
§1.3 本文主要研究内容..................................................................................6
§1.4 结束语......................................................................................................7
第二章 生产调度问题及其调度方法...........................................................................9
§2.1 引言.................................................................................................................9
§2.2 生产调度问题.................................................................................................9
§2.3 车间调度问题...............................................................................................10
§2.3.1 流水车间调度问题.............................................................................12
§2.3.2 作业车间调度问题.............................................................................13
§2.3.3 可重入型的调度问题.........................................................................13
§2.4 生产调度方法...............................................................................................15
§2.5 生产调度问题中不确定因素分析...............................................................17
§2.5.1 生产系统的不确定性.........................................................................17
§2.5.2 不确定性因素的处理方法.................................................................18
§2.5.3 模糊数.................................................................................................18
§2.5.4 模糊数的操作和比较.........................................................................19
第三章 量子微粒群算法的简介...................................................................................21
§3.1 引言...............................................................................................................21
§3.2 计算复杂性...................................................................................................21
§3.3 邻域的概念...................................................................................................22
§3.4 量子计算.......................................................................................................22
§3.4.1 量子物理学基础.................................................................................22
§3.4.2 量子算法及实现.................................................................................24
§3.5 微粒群算法...................................................................................................25
§3.5.1 微粒群算法的原理.............................................................................25
II
§3.5.2 微粒群算法的数学描述.....................................................................26
§3.5.3 微粒群算法的算法流程.....................................................................28
§3.6 量子微粒群算法的设计...............................................................................29
§3.6.1 量子微粒群算法的原理.....................................................................29
§3.6.2 量子微粒群算法的算法流程.............................................................31
§3.6.3 量子微粒群算法和微粒群算法的比较.............................................32
第四章 量子微粒群算法求解不确定条件下的多产品间歇生产调度调度问题.......34
§4.1 引言...............................................................................................................34
§4.2 多产品间歇生产调度问题的描述...............................................................34
§4.3 提前完工和拖期完工满意度.......................................................................36
§4.4 不确定条件下的多产品间歇生产调度问题的数学模型...........................36
§4.5 基于量子微粒群算法的模型求解...............................................................39
§4.5.1 编码与解码.........................................................................................39
§4.5.2 基于量子微粒群算法的求解流程.....................................................40
§4.6 应用算例及仿真结果分析...........................................................................40
§4.6.1 应用算例.............................................................................................40
§4.6.2 结果分析.............................................................................................43
§4.7 结束语...........................................................................................................44
第五章 量子微粒群算法求解不确定条件下的柔性 Job-shop 调度问题.................. 45
§5.1 引言...............................................................................................................45
§5.2 柔性 Job-shop 生产调度问题的描述.......................................................... 45
§5.3 拖期完工满意度...........................................................................................46
§5.4 不确定条件下的柔性 Job-shop 生产调度问题的数学模型...................... 46
§5.5 基于量子微粒群算法的模型求解...............................................................47
§5.5.1 编码与解码.........................................................................................47
§5.5.2 基于量子微粒群算法的求解流程.....................................................49
§5.6 应用算例及仿真结果分析...........................................................................49
§5.6.1 应用算例.............................................................................................49
§5.6.2 结果分析.............................................................................................53
§5.7 结束语...........................................................................................................53
第六章 量子微粒群算法求解不确定条件下的多资源约束 Job-shop 调度问题...... 54
§6.1 引言...............................................................................................................54
§6.2 多资源约束 Job-shop 调度问题的描述...................................................... 54
III
§6.3 拖期完工满意度...........................................................................................55
§6.4 不确定条件下的多资源约束 Job-shop 调度问题的数学模型.................. 55
§6.5 基于量子微粒群算法的模型求解...............................................................56
§6.5.1 编码与解码.........................................................................................56
§6.5.2 基于量子微粒群算法的求解流程.....................................................57
§6.6 应用算例及仿真结果分析...........................................................................58
§6.6.1 应用算例.............................................................................................58
§6.6.2 结果分析.............................................................................................61
§6.7 结束语...........................................................................................................61
第七章 量子微粒群算法求解不确定条件下的可重入生产调度问题.......................62
§7.1 引言...............................................................................................................62
§7.2 可重入生产调度问题的描述.......................................................................62
§7.2.1 组批计划设定.....................................................................................62
§7.2.2 轧批排序问题描述.............................................................................63
§7.3 提前完工和拖期完工满意度.......................................................................64
§7.4 不确定条件下的可重入生产调度问题的数学模型...................................64
§7.5 基于量子微粒群算法的模型求解...............................................................66
§7.5.1 编码与解码.........................................................................................66
§7.5.2 进化模式.............................................................................................67
§7.5.3 基于量子微粒群算法的求解流程.....................................................67
§7.6 应用算例及仿真结果分析...........................................................................68
§7.6.1 应用算例.............................................................................................68
§7.6.2 结果分析.............................................................................................70
§7.7 结束语...........................................................................................................70
第八章 结论与展望...................................................................................................72
参考文献.........................................................................................................................73
在读期间公开发表的论文和承担科研项目.................................................................78
及取得成果.....................................................................................................................78
致 谢...............................................................................................................................79
第一章 绪论
1
第一章 绪 论
§1.1 课题的研究背景
先进制造作为 21 世纪企业的先进制造模式，综合了 JIT、并行工程、精益生
产等多种先进制造模式的哲理，其目的是要以最低成本制造出顾客满意的产品，
即是完全面向顾客的。在这种模式下如何进行组织管理，包括如何组织动态联盟、
如何重构车间和单元、如何安排生产计划、如何进行调度都是企业面临的问题。
其中车间作业调度问题与控制技术是实现生产高效率、高柔性和高可靠度的关键，
有效实用的调度方法和优化技术的研究与应用已成为先进技术实践的基础。
生产调度问题是涉及到运筹学、应用数学、人工智能以及计算机科学等学科
的综合性问题，它是研究在满足一定技术与资源约束条件下操作的排序，并且按
照排定的秩序给操作分配资源，最终使某个执行目标达到最优或近优的管理理论。
其研究的范围包括车间作业调度、流水车间调度问题和柔性车间调度问题等。生
产调度问题具有多约束、多目标、随机不确定性质的组合优化问题，寻找调度问
题的精确解是十分困难，它早已被证明是属于 NP-hard 性质的问题。研究有效的智
能算法来求解生产调度问题是一个具有应用价值和科学研究意义的课题。
自Johnson 在1954 年发表第一篇关于流水车间调度问题(Flow-shop Scheduling
Problem,FSSP)[1]的文章后，学者们便开始了对调度问题的广泛研究。经过 50 多年
的发展，调度问题的研究方法经历了从简单到复杂、从单一到多元的过程。已有
的调度方法可以分为优化调度方法和启发式调度方法。优化调度方法建立在数学
规划之上，通过精确求解解析模型获得最优解，或通过近似求解获得次优解。尽
管数学规划方法比较成熟，但只能有效的解决小规模优化问题，对于复杂的大规
模生产调度问题，随着目标数，设备数和任务数的增加，特别是柔性制造概念的
加入，其解析模型的规模急剧增大，一般优化方法难以求解，而启发式方法在这
方面显示了很大的优越性，启发式算法定义为一个基于直观或者经验构造的算法，
在可接受的花费（指计算时间、占用空间等）下，给出待解决组合优化问题每一
个实例的一个可行解，但不一定保证可得解的优越性。为了弥补这个缺陷，近年
来学者们借鉴达尔文的生物自然选择和遗传思想，发展了一类进化计算方法，通
过模拟生物进化的过程，先对问题的解变量进行编码，产生初始群体，考察群体
的适应性，如不满足收敛条件，则经过复制、选择、交叉、变异等算子操作，产
生下一代群体。一代又一代的“进化”，最终达到参数空间的全局最优点。典型的
有：模拟退火算法、遗传算法、禁忌搜索法、人工神经网络、蚂蚁算法、微粒群
摘要：

摘要在制造系统中，生产调度问题是理论研究中最基本、最重要和最困难的问题之一，以往近几十年的研究中，主要集中于纯确定型生产调度问题，对真实的生产环境进行大量的限制、简化和假设。但随着市场竞争的日趋激烈，客户对产品的要求越来越多样化，产品的生命周期逐渐缩短、产品的结构日益复杂等使得实际的调度存在着大量的不确定因素，传统的模型难以得到满意的结果。本文首先简要回顾了生产调度问题的分类及其调度方法的研究进展情况，分析了在生产调度中存在的主要不确定因素：操作时间不确定性与交货期不确定性，引入了模糊理论对其描述。着重介绍了量子微粒群算法的基本原理及算法流程，该算法保留了微粒群算法的基本框架，并结合了量子计算...

展开>> 收起<<
基于量子微粒群算法的不确定条件下的生产调度问题.pdf

共82页,预览9页

还剩页未读， 继续阅读

相关推荐

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

开通VIP享超值会员特权

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

作者详情

相关内容

更多

推荐作者

热门标签

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