基于文化量子粒子群算法的车间调度研究

VIP免费
3.0 陈辉 2024-11-19 4 4 867.38KB 68 页 15积分
侵权投诉
摘 要
车间调度问题具有很强的工程背景，而且绝大部分都是 NP 难题，寻找出高效
的求解方法一直是该领域的研究热点。近似求解方法在车间调度领域运用的最广。
但是单一算法的性能势必有限，目前由两种以上近似算法混合的算法成为提升性
能的主要途径之一。文化算法是一类概念模型的全局优化算法，其思想是用进化
过程中积累的知识指导种群的进化，从而提高算法的性能和效率。因此本文将量
子粒子群优化算法纳入文化算法的框架，构建了文化量子粒子群优化算法，并将
其运用于车间调度问题的求解。
本文首先简单介绍了车间调度问题的概念、分类以及求解算法的研究进展情
况，并分析了各种算法的优缺点。
其次，在介绍量子粒子群优化算法和文化算法之后，构建了一种更适合求解
组合优化问题的离散量子粒子群优化算法，并将连续量子粒子群优化算法和离散
粒子群优化算法分别纳入文化算法的框架，构建了连续文化量子粒子群优化算法
和离散的文化量子粒子群优化算法。
再次，将构建的算法应用于流水车间调度和作业车间调度两种类型问题的求
解。针对不同类型的调度问题，设计相应的编码和终止条件。如对无等待流水车
间调度问题，将其转化为旅行商问题进行求解；对无等待作业车间调度加工时间
的计算，采用一种基于工件空隙的左移、右移的计算方法。利用 MATLAB 进行仿
真，通过与其他算法的比较，说明了文化量子粒子群优化算法在求解车间调度问
题的可行性和有效性。
最后，对文化量子粒子群优化算法求解车间问题的应用前景进行了展望。
关键词：量子粒子群优化算法 文化量子粒子群优化算法 文化算法
车间调度问题
ABSTRACT
Shop scheduling problem has a strong engineering background, and most of it are
belongs to NP problems. The solution of these problems is the key problems in the
study of shop scheduling theory. Approximate method has been the most widely used
methods to solve shop scheduling problems; however, the performance of a single
algorithm is not so good, so hybrid algorithm which formed by two or more
approximate algorithms has becomed one of the main ways to enhance the performance
of algorithm.Cultural algorithm is a kind of the global optimization algorithms which
has conceptual model, the main idea of cultural algorithm is to use knowledge
accumulated in the evolution to guide the evolution of populations,thereby improving
performance and efficiency of the algorithm. So the method that quantum particle
swarm optimization algorithm based on culture algorithm is proposed to be applied to
shop scheduling problem in this paper.
Firstly, this paper has a review of the concept、classification and studies of shop
scheduling problem and the characteristic of algorithms applied to solving the problems.
Secondly, this paper propose a discrete quantum particle swarm optimization that is
more suitable for sloving combinatorial optimization problems after introducing the
quantunm particle swarm optimization and culture algorithm .then construting
continuous quantum particle swarm optimization algorithm based on culture algorithm
and continuous quantum particle swarm optimization algorithm based on culture
algorithm through incorporating quantum particle swarm optimization algorithm into
the framework of culture algorithm.
Thirdly, this paper tries to apply quantum particle swarm optimization algorithm
based on cultural algorithm to solve flow shop scheduling problem and job shop
scheduling problem，The paper takes different terminating strategies to different kinds
of scheduling problems, for example, translates no wait flow shop scheduling problem
into traveling salesman problem to solving, for no wait job shop scheduling problem,
left 、right timetabling methods based on gap of jobs are proposed to calculate
processing time of processing sequence , and simulates with Matlab. The results show
that this algorithm is feasibility, validity and superiority comparing with the algorithms
in references.
Finally, this paper has a summarization of the work and a prospect of the study and
application of quantum particle swarm optimization algorithm based on cultural
algorithm.
Key word: Quantum Particle Swarm Optimization Algorithm,
Quantum Particle Swarm Optimization Algorithm Based
on Culture Algorithm, Cultural algorithm, Shop
Scheduling Problem
I
目 录
中文摘要
ABSTRACT
第一章 绪论 ..............................................................................................................1
§1.1 研究背景及意义........................................................................................... 1
§1.2 车间调度问题的国内外研究现状............................................................... 2
§1.2.1 车间调度问题的分类........................................................................... 2
§1.2.2 车间调度问题的特点........................................................................... 3
§1.2.3 求解车间调度问题的算法综述........................................................... 3
§1.3 本文主要研究的内容及结构...................................................................... 5
第二章 文化量子粒子群优化算法 ..........................................................................7
§2.1 粒子群优化算法.......................................................................................... 7
§2.1.1 连续的粒子群优化算法....................................................................... 7
§2.1.2 离散的粒子群算法............................................................................... 8
§2.1.3 粒子群优化算法的参数..................................................................... 10
§2.1.4 粒子群优化算法的改进..................................................................... 10
§2.2 量子粒子群优化算法................................................................................ 12
§2.2.1 基于量子理论的量子粒子群优化算法............................................. 12
§2.2.2 基于量子计算的量子粒子群优化算法............................................. 13
§2.2.3 两种类型量子粒子群优化算法的比较............................................. 17
§2.3 文化算法.................................................................................................... 18
§2.4 文化量子粒子群优化算法........................................................................ 19
§2.4.1 离散的量子粒子群优化算法............................................................. 20
§2.4.2 文化量子粒子群优化算法................................................................. 21
§2.4.3 文化量子粒子群算法与其他多种群结构的算法特点的比较......... 22
§2.5 本章小结.................................................................................................... 23
第三章 求解 Flow Shop 的文化量子粒子群优化算法 ....................................... 24
§3.1 求解 Flow Shop 的算法设计 ....................................................................24
§3.1.1 连续量子粒子群优化算法的设计..................................................... 24
§3.1.2 离散量子粒子群优化算法的设计..................................................... 25
§3.1.3 文化量子粒子群优化算法的设计..................................................... 25
§3.2 求解置换流水车间调度的文化量子粒子群优化算法............................ 26
§3.2.1 置换流水车间调度问题的描述......................................................... 27
II
§3.2.2 仿真测试.............................................................................................. 27
§3.2.3 仿真结果分析...................................................................................... 31
§3.3 求解无等待流水车间调度的文化量子粒子群优化算法........................ 32
§3.3.1 无等待流水车间调度问题的描述..................................................... 32
§3.3.2 仿真测试.............................................................................................. 33
§3.3.3 仿真结果分析...................................................................................... 36
§3.4 求解 Blocking 流水车间调度的文化量子粒子群优化算法....................36
§3.4.1 Blocking 流水车间调度的描述...........................................................37
§3.4.2 仿真测试.............................................................................................. 37
§3.4.3 仿真结果分析...................................................................................... 38
§3.5 求解模糊交货期流水车间调度的文化量子粒子群优化算法................ 38
§3.5.1 模糊交货期流水车间调度的描述...................................................... 38
§3.5.2 仿真测试.............................................................................................. 39
§3.5.3 仿真结果分析...................................................................................... 40
§3.6 本章小结.................................................................................................... 40
第四章 求解 Job Shop 的文化量子粒子群优化算法 .......................................... 42
§4.1 Job Shop 问题的描述 ..................................................................................42
§4.2 求解 Job Shop 的算法设计 .......................................................................42
§4.2.1 连续量子粒子群优化算法的设计..................................................... 42
§4.2.2 离散量子粒子群优化算法的设计..................................................... 43
§4.2.3 文化量子粒子群优化算法的设计..................................................... 43
§4.3 仿真测试..................................................................................................... 44
§4.4 仿真结果分析............................................................................................. 45
§4.5 本章小结..................................................................................................... 45
第五章 求解无等待 Job Shop 的文化量子粒子群优化算法 .............................. 47
§5.1 无等待 Job Shop 问题的描述 ....................................................................47
§5.2 时间表问题的求解.................................................................................... 48
§5.3 仿真测试..................................................................................................... 51
§5.4 本章小结..................................................................................................... 55
第六章 总结与展望 ................................................................................................56
参考文献................................................................................................................. 58
在读期间公开发表的论文和承担科研项目及取得成果..................................... 64
致谢......................................................................................................................... 65
第一章 绪论
1
第一章 绪 论
§1.1 研究背景及意义
伴随着金融危机的不断加剧，使得当今的市场竞争日趋激烈。作为我国国民
经济支柱的制造业面临着前所未有的挑战。我国的制造业在大部分行业还处于行
业的低端，尽管产业很大，但是利润不高，竞争力不强。经济学家郎咸平指出，“我
们被定义在价值最低端的制造业环节，而这个环节的特征就是耗费资源、破坏环
境、剥削劳动力”[1]。因此，进行产业升级和结构调整，引入先进的管理思想和生
产技术，降低制造成本，提高生产效率及资源的利用率，开拓国内市场，发掘新
的利润增长点，是当前国内制造业企业摆脱金融危机的关键。
车间调度是实现制造系统运筹技术、管理技术与优化技术发展的核心[2]。好的
调度方案能够大大提高资源的利用率、生产效率和操作管理水平，降低生产成本，
生产出更具有竞争力的产品，进而提高企业的竞争力。因此，车间调度的优化是
当前国内制造业企业摆脱金融危机的有效途径之一。
车间调度主要是针对一项可分解的工作（如产品制造），探讨在尽可能满足约
束条件（如交货期、工艺路线、资源情况）的前提下，通过下达生产指令，安排
其组成部分（操作）使用哪些资源、加工时间及加工的先后顺序，使产品的制造
时间或成本的最优化[3]。车间调度的优化属于组合优化问题,车间调度也称为作业
排序问题或者资源分配问题。它是一个交叉学科，涉及到计算机科学、机械制造、
管理科学与工程、数学和控制工程等学科的知识。因此，车间调度的研究越来越
受到学者的关注，是国内外的热点研究课题[4]。
车间调度研究主要分为车间调度的建模和求解车间调度算法的设计研究两个
方面。建模主要是指模型、规则、优化目标的研究；而算法的设计研究主要是指
算法的有效性、复杂度、收敛性和程序等。本文主要是对求解车间调度的算法进
行研究及设计。
鉴于车间调度研究的现实意义，通过对求解车间调度算法的研究及设计，找
到可行而且满意的调度方案同样具有重要的价值。绝大多数车间调度问题都是
NP-hard 问题[4]。当前求解车间调度的算法主要集中在近似求解算法上，如遗传算
法、粒子群优化算法和蚂蚁算法等，量子粒子群优化算法是近几年提出的一种近
似求解算法，也是目前学者比较关注的算法之一。尽管该算法具有较好的全局寻
优能力、较快的收敛速度等优点，但是单一算法求解车间调度问题的性能势必有
基于文化量子粒子群算法的车间调度研究
2
限。目前将两种以上的近似求解算法相结合的混合算法成为提升求解车间调度问
题性能的主要途径之一。所以，本文将量子粒子群优化算法纳入文化算法的框架，
构建了文化量子粒子群优化算法，并将该算法应用于具体的车间调度问题的求解。
§1.2 车间调度问题的国内外研究现状
1954 年 ， Johnson 首次提出了流水车间调度问题（Flow Shop Scheduling
Problems, FSSP）和解决两台机床的流水车间调度问题的方法，代表着车间调度研
究的开始。经过五十多年的发展，车间调度的理论和方法不断被完善。
§1.2.1 车间调度问题的分类
Graves[5]等人对车间调度问题进行了分类整理，按照不同的分类标准，车间调
度问题可以大致划分为 5类[2][4]：
按生产方式划分，车间调度可以划分为开环型车间调度（open shop）和闭环
型车间调度(closed shop)[6]。开环型车间调度主要是指在满足约束条件的前提下，
只考虑工件在机器上的加工顺序，不考虑库存。闭环型车间调度不仅要在满足约
束条件的前提下，考虑各工件在机器上的加工顺序，还要考虑库存。所以闭环型
车间调度要比开环型车间调度要复杂的多，但是闭环型车间调度更接近于实际的
问题。
按优化的目标划分，车间调度问题可以划分为单目标车间调度和多目标车间
调度。单目标车间调度只以一个目标作为目标函数(例如，调度的费用或调度的最
短流程时间)。多目标车间调度则是综合考虑多个需要优化的目标从而寻求最佳的
调度方案。
按生产环境划分，车间调度问题可以划分为确定型车间调度问题和随机型车
间调度问题。确定性调度问题是指在加工过程中的各项操作的时间以及其他的有
关参数是已知的、确定的。随机性车间调度是指在加工过程中各项操作的时间以
及其他有关参数可以是在一定区间变化的随机变量。
按工件的到达情况划分，车间调度可以划分为静态型车间调度和动态型车间
调度。静态型车间调度指在调度时，所有的工件均处于待加工状态。动态型车间
调度指在调度时，工件陆续到达，即陆续的进入待加工状态，要随时确定工件的
加工顺序。
按约束条件的特点划分，车间调度可以划分为单机调度（Single Machine Shop
Problems , SMSP）、并行机调度（Parallel Machine Shop Problems, PMSP）、流水车
摘要：

摘要车间调度问题具有很强的工程背景，而且绝大部分都是NP难题，寻找出高效的求解方法一直是该领域的研究热点。近似求解方法在车间调度领域运用的最广。但是单一算法的性能势必有限，目前由两种以上近似算法混合的算法成为提升性能的主要途径之一。文化算法是一类概念模型的全局优化算法，其思想是用进化过程中积累的知识指导种群的进化，从而提高算法的性能和效率。因此本文将量子粒子群优化算法纳入文化算法的框架，构建了文化量子粒子群优化算法，并将其运用于车间调度问题的求解。本文首先简单介绍了车间调度问题的概念、分类以及求解算法的研究进展情况，并分析了各种算法的优缺点。其次，在介绍量子粒子群优化算法和文化算法之后，构建了...

展开>> 收起<<
基于文化量子粒子群算法的车间调度研究.pdf

共68页,预览7页

还剩页未读， 继续阅读

相关推荐

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

开通VIP享超值会员特权

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

作者详情

相关内容

更多

推荐作者

热门标签

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