基于萤火虫算法的生产调度问题研究

VIP免费

3.0 刘畅 2025-01-09 7 4 4.03MB 73 页 15积分

侵权投诉

摘要

生产调度在现代企业生产管理环节中起着关键作用，对生产调度的算法研究

也是目前学术界的一个主要研究方向。在制造系统中，生产调度问题是理论研究

中最基本也是最重要的问题之一，传统精确求解算法在求解这些NP-hard难题时时

间呈指数级增长，适用性较差。近年来，许多智能优化算法在求解该类问题时，

显示出了强大的搜索能力和良好的应用效果，成为许多研究者的重要研究方向，

文中萤火虫算法是受萤火虫自然行为的启发发展而来的智能仿生算法，在求解连

续的函数优化和离散的组合优化问题时显示出算法的可行性和有效性。

首先，本文概述了萤火虫算法及生产调度问题的国内外研究现状，对萤火虫

算法的应用领域、解决生产调度问题的各种算法进行了阐述，并总结分析了目前

算法在解决优化问题时存在的不足以及解决方向。

其次，介绍了萤火虫算法的仿生原理、数学描述、步骤以及实现语言等，将

萤火虫算法应用于求解函数优化和组合优化问题。在处理函数优化方面，通过对

六个测试函数进行仿真，发现该算法有效的求解了低维和高维函数优化问题；针

对文中以最小化最大完工时间为目标的PFSP和JSP生产调度问题，萤火虫算法得到

了满意的结果，特别是对PFSP规模较小的Car类问题，大部分都能100%搜索到最优

解。通过对大量的仿真实例进行测试，并与另外两种智能优化算法做比较，萤火

虫算法的求解效果更好。仿真结果表明，萤火虫算法对函数优化和组合优化问题

是有效的，具有良好的全局收敛能力和较快的收敛速度。

最后，对本文的研究工作进行了总结，并探讨了萤火虫算法的进一步研究方

向。

本文对应用较少的萤火虫算法做了积极的探索，拓宽了智能优化算法在解决

实际复杂问题的方向，为相关研究提供一些有意义的参考和启发。

关键词：萤火虫算法函数优化 Flow-shop Job-shop

ABSTRACT

In modern corporation production management，the scheduling is playing a more

and more important role and the study of algorithms for solving scheduling problems is

one of the main academic aspect. In manufacturing systems, scheduling is the most

basic and important problem. The traditional algorithms are not good at solving these

NP-hard problems. In recent years, it shows strong abilities and good applications for

using intelligent optimization algorithms, and it becomes an important direction for

many researchers. Firefly algorithm in the paper is inspired by social behavior of

fireflies and belongs to one of swarm intelligence optimization way, it shows the

feasibility and effectiveness in solving continuous functions and discrete production

scheduling optimization problems.

Firstly, it summarizes the research status of firefly algorithm and production

scheduling at home and abroad, discusses the application field of FA and all kinds of

algorithms for solving production scheduling. In addition, it analyzes the insufficiency

of current algorithms and the solving direction.

Secondly, the paper introduces the bionic principle of firefly algorithm and

analyzes the mechanism of optimization by mathematics, steps as well as the language

of implementation. For continuous function optimization, tested six benchmark

functions instances, simulations and results indicate that FA has well optimal for both

low-dimensional and high-dimensional optimization functions. For discrete production

scheduling problems, aimed at minimize makespan, tested many benchmarks instances

of PFSP and JSP, FA obtains better results, especially for Car problems of PFSP, most

of which get the optimal solution and optimal rate is up to 100%. Compared with QPSO

and PSO, results validate its feasibility and validity of FA for continuous and discrete

space optimization, and shows better global convergence ability and faster convergence

speed.

Finally, conclusions are given. The potential improvement and applications of

firefly algorithm to solve optimization problems are also briefly discussed.

In this paper, it does some positive works about firefly algorithm, and gives the

direction of intelligent optimization algorithm for solving practical complex problems.

The results provide some meaningful reference and inspiration for related studies.

Key Words: firefly algorithm, function optimization, flow-shop

scheduling problem, job-shop scheduling problem

中文摘要

ABSTRACT

第一章绪论 .................................................................................................................... 1

1.1 引言 .................................................................................................................... 1

1.2 国内外研究现状 ................................................................................................ 2

1.2.1 生产调度问题研究现状 ........................................................................ 2

1.2.2 萤火虫算法研究现状 ............................................................................ 3

1.3 本文主要研究内容及结构 ................................................................................ 4

1.4 本章小结 ............................................................................................................ 6

第二章生产调度问题及研究方法 ................................................................................ 7

2.1 引言 .................................................................................................................... 7

2.2 生产调度问题 .................................................................................................... 7

2.2.1 生产调度理论发展历程 ........................................................................ 7

2.2.2 生产调度的定义 .................................................................................... 9

2.2.3 生产调度问题的分类和特点 ................................................................ 9

2.3 解决生产调度问题的方法 ............................................................................... 11

2.3.1 精确算法 ............................................................................................... 11

2.3.2 近似算法 .............................................................................................. 12

2.4 生产调度研究中所存在的问题分析 .............................................................. 14

2.5 本章小结 .......................................................................................................... 15

第三章萤火虫算法简介 .............................................................................................. 16

3.1 引言 .................................................................................................................. 16

3.2 计算复杂性 ...................................................................................................... 17

3.3 萤火虫的生物学行为 ...................................................................................... 17

3.4 萤火虫算法 ...................................................................................................... 18

3.4.1 萤火虫算法的仿生原理 ...................................................................... 18

3.4.2 萤火虫算法的数学描述 ...................................................................... 19

3.4.3 FA 算法的具体步骤及流程图 ............................................................ 20

3.4.4 萤火虫算法的语言实现 ...................................................................... 21

3.5 本章小结 .......................................................................................................... 22

第四章萤火虫算法在连续函数优化中的应用 .......................................................... 23

4.1 引言 .................................................................................................................. 23

4.2 基于函数优化的萤火虫算法 .......................................................................... 24

4.3 仿真实验与结果分析 ...................................................................................... 24

4.3.1 求最大值的函数寻优 .......................................................................... 25

4.3.2 求最小值的函数寻优 .......................................................................... 29

4.4 本章小结 .......................................................................................................... 30

第五章萤火虫算法在置换流水车间调度中的运用 .................................................. 31

5.1 引言 .................................................................................................................. 31

5.2 置换流水车间调度概述 .................................................................................. 32

5.2.1 置换流水车间调度问题的目标 .......................................................... 32

5.2.2 置换流水车间调度问题的数学表示 .................................................. 32

5.3 萤火虫算法用于解决 PFSP 问题 ................................................................... 34

5.3.1 FA 算法的编码方式 ............................................................................ 34

5.3.2 适应度函数 .......................................................................................... 34

5.3.3 萤火虫算法解决 PFSP 的步骤 ........................................................... 34

5.4 仿真实验与结果分析 ...................................................................................... 35

5.4.1 测试问题与性能指标 .......................................................................... 35

5.4.2 算法参数基础分析 .............................................................................. 36

5.4.3 性能对比分析 ...................................................................................... 42

5.5 本章小结 .......................................................................................................... 45

第六章萤火虫算法在作业车间调度中的运用 .......................................................... 46

6.1 引言 .................................................................................................................. 46

6.2 作业车间调度概述 .......................................................................................... 46

6.2.1 Job-shop 调度问题及模型的描述 ....................................................... 46

6.2.2 Job-shop 调度问题的表示及复杂度 ................................................... 48

6.3 萤火虫算法应用于解决 JSP 生产调度问题 .................................................. 49

6.3.1 FA 求解 JSP 问题的编码设计 ............................................................ 49

6.3.2 求解 JSP 问题的萤火虫算法描述 ...................................................... 50

6.3.3 FA 求解 JSP 问题的具体步骤 ............................................................ 50

6.4 仿真实验与结果分析 ...................................................................................... 51

6.4.1 JSP 仿真实例介绍 ............................................................................... 51

6.4.2 FA 求解 JSP 问题的具体实例分析 .................................................... 52

6.4.3 FA 与QPSO、PSO 算法比较 ............................................................. 55

6.5 本章小结 .......................................................................................................... 60

第七章总结与展望 ...................................................................................................... 61

7.1 工作总结 .......................................................................................................... 61

7.2 未来展望 .......................................................................................................... 62

参考文献 ........................................................................................................................ 63

在读期间公开发表的论文和承担科研项目及取得成果 ............................................ 69

致谢 .............................................................................................................................. 70

第一章绪论

1.1 引言

随着计算机科学技术的发展，优化算法的发展十分迅速，有资料显示：在 2008

年以前，信息化优化的应用程度较低，2009 年以后，企业意识到信息化优化的好

处，更多企业开始应用信息化优化算法。2010 年，其优化算法的应用市场规模比

2009 年增长了 43.6%，达 6000 万元；未来三年，预计市场增长率将保持在每年

45%-50%左右，到 2013 年，优化算法的应用市场价值将达到 2.3 亿[1, 2]。

作为我国实体经济重要组成部分的制造业也发生了诸多变化，它们将面临着

更加激烈与严酷的竞争，企业要想在市场中占有一席之地，必须拥有自身独特的

优势，不断提高自身产品的质量、满足客户交货期的要求，另外在服务、成本、

客户体验等各个方面都要更加的完善，要做好这些，是对企业的一大挑战，企业

必须具备快速响应客户需求的能力，即在有限的时间、以有优势的成本生产出客

户需要的“个性化产品”，这种“个性化产品”经常是指客户各式各样的需求，企业需

要生产的产品也是多品种、小批量的，国际生产工程学会（CIRP）在 2000 年就总

结出了至少 40 种不同的先进制造模式，而这些模式存在的基础都是优化的生产调

度[3]，可见生产调度在制造业中的重要性，制造系统的优势也逐渐体现在生产调度

的及时行和准确性上。

一般来说，企业生产管理分为计划、调度和控制三个阶段[4]。企业的一切生产

活动都是与企业的计划有关，宏观上企业会对自身内部的资源和能力、外部的市

场和环境等因素进行仔细评估后，企业对产品需求及供应原料等做出预测，而编

制出企业的中长期计划，从而有计划地安排企业生产的产品数量、种类以及产品

的完成期限，充分的利用好企业的内外部资源。生产调度是制造系统的基础，它

是根据企业的长远计划或由客户的需求来制定的，企业的生产计划也是需要在生

产调度系统中完成的。生产调度分解了生产计划，协调从原料、生产到发货的各

个工序，对整个生产过程进行平衡与控制，并对突发情况及时调节，以保证生产

的连续性，降低生产成本。因此，优化生产调度对提高企业的成本和效益是很有

利的。

对生产调度问题的研究已有很长一段时间，本质上生产调度的要解决的问题

就是在满足机器设备和技术约束条件下，合理安排机器、加工路线、加工时间等

资源，达到整个系统操作的最优。调度问题最先是在生产制造行业中提出的，后

基于萤火虫算法的生产调度问题研究

来用到其他多个领域，如航空、交通等。总之，为了提高企业在市场上的竞争能

力，使企业能够高效低耗敏捷快速的生产，寻求一个良好、准确、快速、合理的

生产调度方法，缩短企业产品的完工周期，加强企业面对激烈竞争的应变能力，

是非常有必有的。

生产调度本质上也属于优化问题，随着问题规模的增加，运用传统的精确优

化算法已不能在有效的时间里找到最优解，在实际中也得不到运用，寻找高效的

智能算法成为一研究热点，本文主要探讨了智能仿生算法—萤火虫算法在优化问

题中的一些应用。

1.2 国内外研究现状

调度优化问题是一研究比较热点的问题，学者们一直在对它进行着探讨和研

究，随着科学技术的发展，理论及算法都得到了迅速的发展，人们对该问题的研

究也越来越深入，下面简单介绍生产调度及萤火虫算法在国内外的研究现状。

1.2.1 生产调度问题研究现状

随着先进制造技术和计算机技术的发展，生产方式也跟着发生了变化，生产

调度问题也形成了不同的种类，根据作业方式的不同可分为单机调度、流水车间

调度(Flow-shop)、作业车间调度(Job-shop)以及平行机调度问题，其中平行机调度

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

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

学者们对于经典调度问题的探索一直没有间断。何洋林的文化进化算法[5]、夏

梦雨的演化博弈算法[6]都在求解 Flow-shop 问题中得到了较理想的结果；刘延风，

刘三阳结合了 NEH 启发式算法和蚁群优化方法结合起来，有效的处理了 Car 和

Taillard 系列的 FSP 问题[7]；王娟，王建运用自适应调节策略较好的解决了基本蚁

群算法易陷入局部最优的缺点，并运用到 FSP 问题仿真中[8]；何建佳结合运用文

化进化机制和 QPSO 的思想有效的解决了置换流水调度问题[9]；王小芹，王万良，

徐新黎提出了一种新的量子染色体解码方法，先在结构上利用系列量子找到次优

解，再集中对次优解进行交叉变异操作，最终找到了最优解[10]；李铁克等研究了

等待时间受限的 FSP 问题[11, 12]；田野，刘大有提出一种混合的元启发式算法

HDCPSO 求解 FSP[13]；唐海波[14]、金超[15]等人分别运用知识进化粒子群算法及

QPSO 算法求解了具有模糊交货期的 FSP 问题。

柳毅用改进微粒群算法求解 Job-shop 问题[16]；丁书斌和 Cheng Na 分别在遗传

第一章绪论

[17]和模拟退火[18]的作用下设计了混合遗传算法求解 Job-shop 问题；周辉仁等[19]和

朱颢等[20]分别提出改进的遗传算法和和改进的蚂蚁算法求解 JSP 问题；吴宇明用

遗传蚁群算法有效地仿真了 JSP 国际标准数据库中的 43 个问题[21]；叶伟等[22]、唐

海波等[23]、刘长平等[24]分别运用协同优化算法、混合粒子群算法及量子蚁群算法

求解 JSP；周安阳改进后的免疫算法解决了生产调度问题[25]；金静文针对实际性在

静态调度的基础上设计的相应的动态调度算法，解决柔性资源动态组合的生产调

度问题[26]。

1.2.2 萤火虫算法研究现状

萤火虫算法是通过模拟自然界中萤火虫个体的发光行为而发展起来的，目前为

止文献中出现了两种萤火虫算法版本。

版本 1：GSO (glowworm swarm optimization)，是由印度学者 Krishnanand 和

Ghose 于2005 年最早提出，它是一种群体智能式启发算法，主要是用于群体机器

人协同运作，寻找多峰值函数的峰值问题中[27]。GSO 算法是利用萤火虫发光的特

性来根据其区域决策半径寻找邻居，区域决策范围的大小会受邻居数量影响，当

邻居密度愈低，萤火虫的决策半径会加大以利寻找更多的邻居；当邻居密度愈高，

它的决策半径则会缩小。最后，大部分的萤火虫会聚集在多个位置上。愈亮的邻

居拥有愈高的吸引力吸引此萤火虫往这个方向移动，这样，所有个体向邻域结构

内位置较优的萤火虫移动，从而实现位置进化。在 2006 年，Krishnanand 等学者又

先后提出两种新的半径更新方式[28, 29]；2007 年，作者采用简化的方式对 GSO 算法

的收敛性进行了数学推导说明，为算法的理论奠定了初步基础[30]；2009 年，作者

在文献中给出了 GSO 算法的流程图以及伪代码[31]。该算法自 2005 年提出来以后，

算法的提出者一直在不断努力的改进，同时也得到了其他学者的关注。2011 年，

张军丽、周永权基于 Powell 方法，对基本 GSO 算法进行改进，取得很好的效果[32]。

刘佳昆、周永权提出了具有主从结构的并行人工萤火虫群优化算法[33]；王改革等

人运用 GSO 算法优化 BP 神经网络的目标威胁估计，具有良好预测能力[34]；方瑛，

曾宇将 GSO 与启发式算法 BL 规则相结合，很好的解决了布局问题[35]；程魁，马

良等人提出基于元胞自动机的元胞萤火虫算法，有效地求解了多选择背包问题[36]。

版本 2：FA (firefly algorithm)，由剑桥学者 Yang Xin-she 于2008 年提出，它是

根据荧光亮度决定的相对吸引度来实现萤火虫的移动，从而实现位置的更新[37]。

2009 年，提出者 Yang 将FA 算法用到求解多目标函数优化问题上，取得了满意的

结果[38]；同一年，Lukasik S 和Zak S[39]将该算法应用到出来连续约束优化问题上，

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

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

15 积分 4人已下载

立即下载 VIP免费下载

基于萤火虫算法的生产调度问题研究.pdf

共73页,预览8页

还剩页未读，继续阅读

基于萤火虫算法的生产调度问题研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: