基于智能水滴算法的复杂流水车间调度研究

VIP免费

3.0 侯斌 2024-11-19 4 4 784.22KB 51 页 15积分

侵权投诉

摘要

流水车间调度问题(Flow-Shop Scheduling Problem)是一个著名的 NP 难题，一

直是生产系统研究热点和难点，由于流水车间调度具有很强的约束条件，当调度

问题规模较大时很难找到全局最优解。

FSSP 是实际生产调度的一种简化模型，它

无论是在制造业还是在其他生产工业中都具有广泛的应用，其合理的调度算法更

是生产系统调度问题的一个重要研究方向。目前大多数国有制造企业在车间生产

过程中采用的是人工调度，调度时主要依靠调度经验，调度效率不高并且容易出

错。因此有效的调度方法对制造业降低生产成本、提高生产效率和资源利用率具

有重大意义，同时也受到越来越多学者的关注和研究。

考虑到实际生产运营的各个环节都客观存在干扰因素、学习效应和无等待，

为了更符合实际生产环境和应用需要，研究流水车间干扰调度、具有学习效应的

流水车间调度和无等待的流水车间调度不仅具有重要的理论意义，而且具有较高

的应用价值。这三种流水车间调度模型都比经典 Flow-shop 复杂，都属于强

NP-hard 问题。

本文首先介绍了国内外对流水车间干扰管理、具有学习效应和无等待的流水

车间调度问题的研究方法和现状，阐述了智能水滴算法的基本思想和应用原理，

智能水滴算法(IWD)是在蚁群算法的基础上发展而来的，它是一种新颖的群智能

算法。智能水滴算法模拟的是自然界中水流系统流动过程，当河流环境发生变化

即是水滴发生行动和反应。而变邻域算法(Variable Neighborhood Search VNS)是一

种高效的局部搜索算法，在此基础上提出了一种结合变邻域搜索和交叉操作的混

合智能水滴算法求解流水车间干扰管理、学习效应和无等待调度问题。本文中用

此改进后的算法用于求解这三种类型的复杂流水车间调度问题。运用 MATLAB7.0

语言编写软件程序。仿真实例结果表明改进后的智能水滴算法总能找到全局最优

解，大大提高了寻优速度和搜索能力，验证了智能水滴算法的可行性和优越性，

对以后进一步开展生产调度问题的研究有一定的帮助。

关键词：流水车间调度干扰管理学习效应无等待智能水滴算法

ABSTRACT

Flow-Shop Scheduling Problem is a known NP problem as a popular and difficult

research realm in production system, due to flow-shop with strong constraints

condition, when the scale is hard to find global optimal solution. the FSSP is a lot of

real production scheduling problem simplified model. Whether it is in the discrete

manufacturing industry or in process industry has broad applications as a certain

representation. The study of reasonable scheduling algorithm is an important aspect of

solving scheduling problem. Now most of the State-owned manufacturing enterprises

used in the production process of manually scheduling, schedule was largely dependent

on scheduling experience, scheduling is inefficient and error-prone. So the effective

scheduling methods is of great significance, which reduces production costs and

improve the economic efficiency in manufacturing industry, but also causes more and

more attention of scholars.

Considering the actual production and operation of the various links are objective

existence of interference factors, learning effect and no-wait. In order to meet the needs

of the actual production environment and application. The research on flow shop

scheduling with no-wait, flow-shop scheduling with learning effect and disruption

management on flow shop scheduling, which is not only of great theoretical

significance, and has a high application value. These three kinds of flow shop

scheduling model is more complex than the classical Flow-shop, belong to the strong

NP-hard problem.

This thesis first introduces domestic and foreign research methods and present

situation of interference management, flow shop with a flow shop scheduling problems

with learning effect and no-wait, expounds the basic idea and application principle of

intelligent water drops algorithm. Intelligent droplet algorithm (IWD) is based on the

Ant Colony algorithm development, Which is a novel algorithm of swarm intelligence.

IWD simulates natural water system flow, action and reaction are water droplets

occurred when the river environment change. In this article the algorithm for solving

complex scheduling problems.The variable neighborhood algorithm is a kind

of effective local search algorithm, combined with cross operation of hybrid

intelligent drop algorithm for disruption management on flow shop,learning effect and

no-wait on scheduling problem. With this improved Intelligent Water Drops algorithm

to solving complex production scheduling problems in this article, written in MATLAB

language programs using intelligent drop algorithms for solving scheduling problems.

IWD ensure the introduction of a global optimal solutions, simulation results. Which

show that the feasibility and effectiveness of smart drop algorithm, increases

scheduling efficiency for further production scheduling the help of research.

Key Words: flow-shop scheduling, disruption management, learning

effect, no-wait, intelligent water drops optimization

中文摘要

ABSTRACT

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

1.1 研究背景及目的 ................................................. 1

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

1.3 研究内容及重点 ................................................. 4

第二章智能水滴算法 .................................................. 6

2.1 自然界中的水滴 ................................................. 6

2.2 智能水滴算法 ................................................... 7

2.2.1 智能水滴算法的介绍 ......................................... 7

2.2.2 智能水滴算法的基本原理 ..................................... 8

2.2.3 智能水滴算法的改进 ........................................ 11

2.3 智能水滴算法的应用研究 ........................................ 12

第三章智能水滴算法应用 FLOW-SHOP 干扰仿真 ........................... 16

3.1 干扰管理概述 ...................................................16

3.2 FLOW-SHOP 干扰管理模型 .......................................... 17

3.3 智能水滴算法应用于 FLOW-SHOP 干扰仿真 ............................ 19

第四章具有学习效应的 FLOW-SHOP 干扰管理 ............................. 24

4.1 学习效应问题的描述 ............................................ 24

4.2 具有学习效应 FLOW-SHOP 问题的数学模型问题 ........................ 25

4.3 具有学习效应 FLOW-SHOP 干扰仿真 .................................. 29

第五章无等待的流水车间干扰管理 ..................................... 36

5.1 无等待的流水车间调度问题 ...................................... 36

5.2 具有无等待的流水车间干扰调度模型 .............................. 38

5.2.1 仿真测试 .................................................. 39

5.2.2 仿真结果分析 .............................................. 40

第六章总结与展望 ................................................... 41

参考文献 ......................................................... 43

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

致谢 .............................................................. 49

第一章绪论

本章最先阐述了研究背景及研究目的，然后对复杂流水车间调度相关问题和

近年来国内外对此类问题的研究现状、研究成果进行了概述，最后介绍了论文的

研究内容及重点。

1.1 研究背景及目的

随着科学技术的飞跃发展和经济的迅速提高、信息网络技术的加速，生产制

造业的市场竞争也越发激烈。绝大多数的企业更重视如何让所需产品生命周期更

短，产品质量更有保障、成本尽可能的降到最低、同时提供更优质的服务。在21

世纪，企业面临的另一难题就是生产中必须还要确保环境不受污染，绿色环保。

另外生产制造业若是想在市场站稳一席之地,就必须保证生产调度问题的及

时性和准确性。生产调度问题即是如何利用有限的资源来达到最高的生产效率，

它是计算机技术，管理学，运筹学等多门学科的综合考虑。因此,有效的调度技术

是降低制造生产成本和提高效率的主要因素, 对相关问题的研究都具有非常重要

的理论基础和实用价值。

然而实际生产调度的过程是“动态”而非“静态”时刻都在不断变化。目前

大多数所研究的流水线调度模型都是在理想的状态下,并没有考虑其他因素。因此

较为复杂的流水车间调度，自由车间调度以及作业车间调度更加复杂的生产调度

问题的应用研究存在明显的不足。然而在实际生产中,由于各种资源的约束、多种

干扰因素和加工工艺的限制,都会影响制造工期的完工时间，以致生产车间调度更

加复杂。流水线调度问题(FSP)是一种最典型的生产调度模型问题,同时也是研究人

员研究领域最多的NP完全问题。由于其特殊的NP-hard性，近年来流水线调度问题

一直是众多研究学者和工程领域所讨论的热点。复杂流水车间调度问题包括考虑

在原定调度中突然出现的干扰因素，生产过程中存在的学习效应及柔性资源的约

束等，实验证明复杂流水车间调度更是一个NP完全问题。如何把生产过程中遇到

的不可预料的因素有效的使用在不同的加工中心上,同时保障生产系统具有更高

效的运转能力。这将成为以后研究领域的一个关键问题。

本文研究了受干扰事件影响的流水车间调度问题(Flow Shop Scheduling

Problem FSP)、具有学习效应的FSP干扰管理和无等待的流水车间调度问题。根据

这些问题的特殊性和复杂性，提出了一种新颖的智能算法，从而更好的求得最优

解达到企业所需的经济目标。本文通过对智能水滴算法的基本原理和核心算法进

行研究，并将智能水滴算法运用于一类具有代表性的复杂流水车间调度问题中，

并构建了复杂流水车间调度问题作为本文的仿真实例，运用相对应的智能水滴算

法进行求解，并对其调度算法编码设计，用MATLAB语言实现，最后对其仿真结

上海理工大学硕士学位论文

果进行测试分析。同时验证了智能水滴算法的可行性和优越性，并证明对于复杂

流水车间干扰管理进行调度能有效的提高生产绩率。

为了更好的研究该算法的有效性以及达到其研究目的，本文查阅了大量的资

料和国内外学者对复杂流水车间调度问题的相关研究，并对有关的论文文献进行

了整理、归纳和总结，作为对本论文的理论依据。最后对本文所作的工作及得到

的结果进行了总结，并对智能水滴算法在流水车间调度问题上的未来研究方向进

行了有效的探讨和展望。

1.2 国内外研究现状

在20 世纪 50 年代初期国外学者Johnson[1] 研究了带准备时间的流水车间

( Flow-shop) 调度问题，此后，如何对流水车间调度问题的建模以及求解，一直是

众多研究者和理论界讨论的热点。绝大多数的流水车间调度问题早已被证明是非

确定性多项式NP难题，即便是一些小批量，简单的调度问题，也很难快速得到最

优解。近十几年以来，针对流水车间调度的算法研究取得了很多成果。20世纪60-70

年代提出了经典调度理论，重点研究调度的复杂性。直到70年代后期，许多研究

者又提出了一些新的生产调度方法。虽然在生产调度方法的研究己经有50多年,但

是如何更好的把理论研究运用到实际生产中，仍然存在很大的困难，需要以后更

多的学者进一步的突破。

在国外,从事生产调度领域的学者们利用最优化方法和启发式方法对各种流

水作业车间调度问题进行了研究,并取得了一些显著的成果。大多数研究者和专家

更关注生产调度的动态及复杂性与动态事件的研究，运用群智能优化算法来有效

解决流水车间调度问题，如运用粒子群算法、蝙蝠算法、萤火虫算法、遗传算法、

和声算法等，并且都取得了较好的研究成果。

在流水车间干扰管理方面，往往有许多不确定的事件发生,很容易打乱原定计

划的生产调度,使得原计划不可行。针对这种情况,干扰管理(disruption management)

最早由丹麦学者Clausen[2]提出。很快干扰管理就被学者所认可，并且迅速在医学，

工业，教育和服务行业等被广泛运用。近年来对于干扰管理的研究也越来越多，

目前干扰管理已经成功地运用到物流配送，航空调度和生产运营与管理等方面，

干扰管理问题已经发展成为运筹学，计算机科学，统计应用学和管理科学等综合

科学方面新的研究方向，对将来进一步的科学研究具有重要的应用意义。

2008年国内学者胡祥培[3]等人对干扰管理模型以及对应的算法求解进行了综

述，对在实际生产运作中发生的干扰事件，提出了相对应的干扰管理应急处理模

式。姜洋[4]对不确定事件的生产调度干扰管理问题进行了更深入的研究，根据企业

的实际生产要求，将不确定事件分为客观和受主客观影响的生产调度干扰管理，

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

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

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要流水车间调度问题(Flow-ShopSchedulingProblem)是一个著名的NP难题，一直是生产系统研究热点和难点，由于流水车间调度具有很强的约束条件，当调度问题规模较大时很难找到全局最优解。FSSP是实际生产调度的一种简化模型，它无论是在制造业还是在其他生产工业中都具有广泛的应用，其合理的调度算法更是生产系统调度问题的一个重要研究方向。目前大多数国有制造企业在车间生产过程中采用的是人工调度，调度时主要依靠调度经验，调度效率不高并且容易出错。因此有效的调度方法对制造业降低生产成本、提高生产效率和资源利用率具有重大意义，同时也受到越来越多学者的关注和研究。考虑到实际生产运营的各个环节...

展开>> 收起<<

基于智能水滴算法的复杂流水车间调度研究.pdf

共51页,预览6页

还剩页未读，继续阅读

基于智能水滴算法的复杂流水车间调度研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: