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

VIP免费

3.0 陈辉 2024-11-19 6 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

中文摘要

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

§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 课题的研究背景

先进制造作为 21 世纪企业的先进制造模式，综合了 JIT、并行工程、精益生

产等多种先进制造模式的哲理，其目的是要以最低成本制造出顾客满意的产品，

即是完全面向顾客的。在这种模式下如何进行组织管理，包括如何组织动态联盟、

如何重构车间和单元、如何安排生产计划、如何进行调度都是企业面临的问题。

其中车间作业调度问题与控制技术是实现生产高效率、高柔性和高可靠度的关键，

有效实用的调度方法和优化技术的研究与应用已成为先进技术实践的基础。

生产调度问题是涉及到运筹学、应用数学、人工智能以及计算机科学等学科

的综合性问题，它是研究在满足一定技术与资源约束条件下操作的排序，并且按

照排定的秩序给操作分配资源，最终使某个执行目标达到最优或近优的管理理论。

其研究的范围包括车间作业调度、流水车间调度问题和柔性车间调度问题等。生

产调度问题具有多约束、多目标、随机不确定性质的组合优化问题，寻找调度问

题的精确解是十分困难，它早已被证明是属于 NP-hard 性质的问题。研究有效的智

能算法来求解生产调度问题是一个具有应用价值和科学研究意义的课题。

自Johnson 在1954 年发表第一篇关于流水车间调度问题(Flow-shop Scheduling

Problem,FSSP)[1]的文章后，学者们便开始了对调度问题的广泛研究。经过 50 多年

的发展，调度问题的研究方法经历了从简单到复杂、从单一到多元的过程。已有

的调度方法可以分为优化调度方法和启发式调度方法。优化调度方法建立在数学

规划之上，通过精确求解解析模型获得最优解，或通过近似求解获得次优解。尽

管数学规划方法比较成熟，但只能有效的解决小规模优化问题，对于复杂的大规

模生产调度问题，随着目标数，设备数和任务数的增加，特别是柔性制造概念的

加入，其解析模型的规模急剧增大，一般优化方法难以求解，而启发式方法在这

方面显示了很大的优越性，启发式算法定义为一个基于直观或者经验构造的算法，

在可接受的花费（指计算时间、占用空间等）下，给出待解决组合优化问题每一

个实例的一个可行解，但不一定保证可得解的优越性。为了弥补这个缺陷，近年

来学者们借鉴达尔文的生物自然选择和遗传思想，发展了一类进化计算方法，通

过模拟生物进化的过程，先对问题的解变量进行编码，产生初始群体，考察群体

的适应性，如不满足收敛条件，则经过复制、选择、交叉、变异等算子操作，产

生下一代群体。一代又一代的“进化”，最终达到参数空间的全局最优点。典型的

有：模拟退火算法、遗传算法、禁忌搜索法、人工神经网络、蚂蚁算法、微粒群

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

算法等。

微粒群算法[2]，又称粒子群算法（Particle Swarm Optimization,PSO）是由美国

社会心理学家 James Kennedy 和电气工程师 Russell Eberhart 在1995 年提出的，是

继蚂蚁算法之后有一种新的群体智能算法，目前已经成为进化算法的一个重要分

支。微粒群算法自提出以来，在国外得到了相关领域众多学者的关注与研究。CEC

国际年会上，微粒群算法被作为一个独立的研究分支，与遗传算法、进化规划等

进化算法相提并论。它吸取了鸟儿觅食的行为特性，通过其内在的搜索机制，在

一系列困难的组合问题中取得了成效。该算法已经在著名的旅行商问题和车辆调

度问题中崭露头角，表现出了可靠而快速的寻优能力。该算法现已陆续渗透于其

他问题邻域，如工件排序、炼油厂的生产计划、二次分配问题、电力系统优化问

题等。但是微粒群算法还有许多问题需要进一步研究和解决，如早熟收敛的问题、

收敛性证明、处理复杂约束问题的能力、环境参数选择方法等。庆幸的是，微粒

群算法具有开放式结构，可以较方便的同其他方法结合或引入其他思想构成新的

算法，从而对微粒群算法中存在的不足加以弥补。

1996 年，Grover 提出量子搜索算法[3]，证明量子计算机在穷尽搜索问题中，

比经典计算机有

的加速，用此算法，可以仅用 2亿步就可代替经典计算机大

约

1035 

步计算。量子计算的并行性、指数级存储容量和指数加速特征展示了其

强大的运算能力。关于量子计算更为永恒和令人激动的理由是它所导致的思考物

理学基本定律的心得，以及它为其他科学技术所带来的有创见的方法。有效利用

量子理论的原理和概念，将会在应用中取得明显优于传统智能计算模型的结果。

因此，关于结合量子计算和进化计算的算法应运而生，例如量子退火算法、量子

遗传算法、量子克隆进化算法、量子神经网络。结合了量子计算的进化算法，有

效的克服早熟现象，加快了算法的收敛速度。但迄今为止，量子进化算法还处于

萌芽阶段，无论是理论还是应用都还未成熟，对它的速度的提高还没有严格的数

学分析和证明。但是深入研究量子计算和其他进化算法的相互作用，不断产生具

有重要意义的概念和方法，对于解决 NP-hard 肯定具有巨大突破。

§1.2 课题的国内外研究情况

§1.2.1 量子微粒群算法国内外研究

Sun 等人于 1994 年从量子力学的角度出发提出了一种新颖的 PSO 模型，这种

模型以 DELTA 势阱为基础，认为粒子具有量子行为，并根据这种模型提出了基于

量子行为的粒子群优化算法(Quantum Particle Swarm Optimization,QPSO)[4]，在量子

第一章绪论

空间中，粒子可以在整个可行解空间中进行搜索，因而 QPSO 算法的全局搜索性

能远远优于标准的 PSO 算法。自此之后，QPSO 算法得到广泛的关注，学者们开

始将 QPSO 算法应用于解决各类复杂的 NP-hard 难题中。

目前量子微粒群算法的应用极为广泛，用于经典组合优化问题：旅行商

（Traveling Salesman Problem,TSP）问题[5]，调度问题[6-7]，函数优化[8-9]等。还有用

于解决现代生活中的各类问题：图像颜色分割[10]，布局问题[11]，投资组合优化[12]，

二维热传导反问题[13]，车辆路径优化问题[14]等。但是量子微粒群算法在组合优化

领域仍处于起步阶段。Shor 和Grove 的研究成果能够证明在量子效应下计算具备

强大的并行能力[15]，而在经典的计算机中求解组合优化问题上是否能利用这种并

行能力仍然需要进一步的研究和试验来验证。虽然量子微粒群算法已经在一些连

续优化问题中体现较好的寻优能力，但是在部分组合优化问题中也暴露出了不足。

特别是用于解决生产调度问题的量子微粒群算法研究成果相对较少，在很大程度

上正是因为这类算法的缺陷，目前量子微粒群算法的不足主要体现在以下几个方

面：

1) 困难的编码和解码使得个体构造的可行性得不到保障，目前所通用的编码方式

使码的存储需要较大的空间。

2) 优化中的逻辑判断分类太多，造成量子比特的更新操作繁琐。

3) 量子微粒群算法独特的进化模式造成进化后期探索效果不显著。

鉴于量子微粒群算法的上述不足，学者们考虑对微粒群算法进行变化来达到

改善的目的，将算法的编码或更新操作加以调整，使得算法在优化过程中每一个

环节都在最大程度上发挥其作用。近几年，国内的许多学者在这方面个做了大量

的研究，取得了显著的成效。

殷志锋将量子算法与微粒群算法相结合，构造了嵌入式粒子群量子进化算法

和量子二进制粒子群算法这两种算法量[16]，对 QPSO 做了深入的研究，新的混合

算法不但继承了 PSO 的优点，而且在全局收敛性能和搜索速度上表现了很好的成

效。

须文波等运用并行的 QPSO 解决有约束的优化问题[17]，通过采用粒子群系统

的并行化的量子化模型提高全局搜寻能力，在解决约束问题时采用不固定的多阶

段任务补偿函数以提高收敛性，实验结果显示改进的 QPSO 的最优值和运行时间

比传统的 PSO 有很大的提高，而且运行所用的时间资源接近线性减少。

刘心报等运用混合 QPSO 文章使用混合量子粒子群优化算法求解作业车间调

度问题，并设计了一种基于工序的编码方式[6]；为了克服量子粒子群优化算法容易

陷入局部最优的缺点，将模拟退火算法引入量子粒子群优化算法，使算法具有跳

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

出局部最优的能力并增强其全局搜索能力，形成量子粒子群-模拟退火调度算法，

仿真结果表明混合算法具有良好的全局收敛性能。

卞锋、毛力等通过引入交换子和交换序，对基本 QPSO 算法进行改造，成功

地将 QPSO 应用于求解 TSP 中[5]。同时引入遗传算法中变异算子的概念，克服传

统PSO 算法中粒子在落入局部最优解时导致搜索能力下降的缺点。在实验表明本

文算法在解决 TSP 时QPSO 算法具有更强的搜索能力，收敛速度更快。

虽然 QPSO 算法还处于萌芽阶段，很多地方还需挖掘和应用，但是现已有诸

多学者通过改进 QPSO 算法来解决 NP-hard 难题，而且也取得了很好的效果，足

见QPSO 算法在优化方面的巨大潜力。

§1.2.2 生产调度国内外研究

近年来，随着先进制造技术和计算机技术的发展，生产调度的涵义有所推广，

从而与实际生产更为接近。随着需求的变化，生产方式随之改变，生产调度的问

题也按作业方式的不同形成了很多典型的分类，从最基本的单机调度问题，作业

车间(Job-shop)调度问题，流水车间(Flow-shop)调度问题，平行机调度问题等发展

为提前/拖期调度，模糊调度，动态调度，应急调度等。根据问题的特点，展开了

以问题为中心的各种研究。

学者们对于经典调度问题的探索一直没有间断。柳毅运用改进微粒群算法求

解Job-shop 问题[18]。丁书斌和 Cheng Na 分别在遗传[19]和模拟退火[20]的作用下设计

了混合遗传算法求解 Job-shop 问题，吴正佳的改进蚁群算法[21]，夏梦雨的演化博

弈算法[22]，何洋林的文化进化算法都在求解 Flow-shop 问题中得到了较理想的结果

[23]。徐震浩结合免疫算法和分枝定界方法所构造的混合算法有效地提高了求解

Flow-shop 调度问题过程中的搜索效率[24]。

根据车间的实际情况，研究的问题模型更趋向实际运作环境。李素粉针对提

前/拖期问题[25]，以惩罚费用最小为目标，对加工排序进行优化后，对提前完工的

产品适当地加入空闲时段，使其按时完工。宋晓宇从关键路径入手，形成了基于

块上工件的邻域结构，配合禁忌搜索对模糊加工时间的 Job-shop 问题进行优化[26]。

柳毅在微粒群算法基础上，通过引入禁忌搜索算法和动态设置惯性权重等方法，

将其应用于提前/拖期问题[27]。周国华从客户满意度出发，设计了根据交货期的客

户满意函数，运用遗传算法求解模糊交货期的 Flow-shop 调度问题[28]。宋晓宇设计

了基于关键工序的邻域搜索方法的禁忌搜索，并将其结合蚁群算法用于求解模糊

Job-shop 调度问题[29]。王万良考虑流程工业间歇生产的中间产品存储策略，并对

存储策略为混合情况下操作时间不确定的模糊问题进行了研究[30]。张晴展开讨论

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

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

展开>> 收起<<

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

共82页,预览9页

还剩页未读，继续阅读

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

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: