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

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]。企业的一切生产

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

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

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

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

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

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

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

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

利的。

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

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

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

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

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

15 积分 4人已下载

立即下载 VIP免费下载

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

共73页,预览8页

还剩页未读，继续阅读

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

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: