用SFLA算法解决NW调度问题.docx
- 文档编号:10379370
- 上传时间:2023-05-25
- 格式:DOCX
- 页数:42
- 大小:392.43KB
用SFLA算法解决NW调度问题.docx
《用SFLA算法解决NW调度问题.docx》由会员分享,可在线阅读,更多相关《用SFLA算法解决NW调度问题.docx(42页珍藏版)》请在冰点文库上搜索。
用SFLA算法解决NW调度问题
目录
1绪论1
1.1组合优化问题1
1.2调度问题2
1.3本文结构3
2生产调度问题4
2.1生产调度问题4
2.2流水车间调度问题8
3蛙跳算法10
3.1蛙跳算法简介10
3.2蛙跳算法国内外研究情况11
3.3蛙跳算法原理12
3.4蛙跳算法的相关研究15
3.5蛙跳算法的优缺点17
4零等待策略(NW)的Flowshop调度问题18
4.1零等待策略(NW)的Flowshop调度问题数学模型18
4.2仿真分析19
4.3小结30
5总结与展望31
5.1本文总结31
5.2展望31
参考文献32
致谢35
1绪论
1.1组合优化问题
由于科学技术突飞猛进地发展,随着人们在生活和工作中碰到各种各样的问题,而解决这些问题的方案又有许多,其中组合优化问题日益得到了国内外的广泛重视。
组合优化问题是一种离散最优化问题,就是在给定约束条件下,求出使目标函数极小(或极大)的变量组合问题。
优化是个古老的课题,它所研究的问题是在众多方案中寻找最优方案。
长期以来,人们对优化问题进行探讨和研究。
早在17世纪,英国Newton和德国Leibnitz发明的微积分就蕴含了优化的内容。
而法国数学家Cauchy则首次采用梯度下降法解决无约束优化问题,后来针对约束优化问题又提出了Lagrange乘数法。
人们关于优化问题的研究工作,随着历史的发展不断深入。
但是,任何科学的进步都受到历史条件的限制,直到二十世纪四十年代,计算机的应用被大量运用于这个问题,至此,优化问题的研究不仅成为一种迫切需要,而且有了求解的有力工具。
因此,优化理论和算法迅速发展起来,形成一门新的学科。
至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。
这些优化技术在实际应用中正发挥越来越大的作用。
不过随着人类生存空间的扩大,以及认识世界和改造世界范围的拓宽,常规优化方法已经无法处理人们所面对的复杂问题,因此高效的优化算法成为科学工作者的研究目标之一[1]。
优化方法涉及的工程领域很广,问题种类与性质繁多。
归纳而言,最优化问题可以分为无约束问题与约束优化问题两大类。
若决策变量
的解空间为
,则该问题为无约束最优化问题;若决策变量
的解空间受到一些约束函数的限制,则该问题被称为约束优化问题。
按对象是连续状态还是离散状态,最优化问题也可分为函数优化问题和组合优化问题两大类,其中函数优化问题的对象是一定区域内的连续变量,而组合优化问题是解空间中的离散状态[1]。
1.1.1无约束最优化与约束优化
最优化问题的一般形式为
(1-1)
其中
其中
是决策变量,
为目标函数,
为约束集或可行域。
特别地,如果约束集
,则最优化问题(1-1)称为无约束最优化问题;
(1-2)
其中
约束最优化问题通常写为
(1-3)
这里
和
分别是等式约束的指标集和不等式约束的指标集,
是约束函数。
当目标函数和约束函数均为线性函数时,我们把问题称为线性规划。
当目标函数和约束函数中至少有一个是变量
的非线性函数时,则问题称为非线性规划。
此外,根据决策变量、目标函数和要求的不同,最优化还被分成了整数规划、动态规划、网络规划、非光滑规划、随机规划、几何规划、多目标规划等若干个分支[1]。
1.1.2函数优化与组合优化
函数优化问题通常可描述为:
令
为
上的有界子集(即变量的定义域),
为
维实值函数,所谓函数
在
域上全局最小化就是寻求
使得在
域上全局最小。
典型的组合优化问题有旅行商问题(TravelingSalesmanProblem,TSP)、时间表问题(TimetablingProblem,TTP)、加工调度问题(SchedulingProblem,如Flow-Shop,Job-Shop)、0-1背包问题(KnapsackProblem)、装箱问题(BinPackingProblem)、图着色问题(GraphColoringProblem)、聚类问题(ClusteringProblem)等[2]。
1.2调度问题
调度问题(Scheduling)是组合优化问题的一种,它是根据生产目标和约束条件为每个加工对象确定具体的加工路径、时间、机器和操作方式等,在一定的约束条件下,合理地分配资源(Resource)完成一批给定的任务(Task)或作业(Job),获得某些性能指标(PerformanceCriterion)如完成时间或生产成本等的最优化。
这里的资源是一种泛指,如人员、金钱、机器、工具、材料和能源等,而任务也可以有不同的解释,从制造系统的机器分配到计算机系统的信息处理等。
在有些文献中调度问题也被称为排序问题(Sequencing)。
但“排序”与“调度”存在一定的区别,以生产车间的机器加工为例,“排序”主要考虑的是所有机器上一个工件序列的分配和置换问题。
而“调度”不仅考虑次序问题(包括被加工对象“工件”的次序和提供加工对象“机器”的次序),而且更重要的是对时间的分配。
因此,有些学者认为“排序”是一种特殊的调度,“调度”一词也被更广泛的使用。
生产调度是在生产任务和产品产量需求给定的情况下,确定较合理的生产方案,即在满足单元设备的处理能力和生产工艺要求的前提下,对给定的单元装置进行任务的分配或重分配,包括对各产品在生产时间和空间(生产流程线)的规划,使生产任务得以完成[1]。
优良的调度对于增强企业的竞争能力、提高经济效益有着极大的作用。
调度问题中一个非常典型的问题是FlowShop问题。
自从Johnson在2003年发表了第一篇关于流水车间调度问题的文章以来,流水车间调度问题引起了许多学者的关注,提出了许多解决的方法,整数规划和分枝定界法是寻求最优解的常用方法,但流水车间调度问题是NP完全问题,对于一些大规模甚至中等规模的问题,整数规划和分枝定界法仍不是很有效。
因此又相继提出一些启发式算法,最近一些智能搜索算法也被应用于解决FlowShop调度问题,如禁忌搜索方法、模拟退火算法、遗传算法、蚁群算法等。
其中无等待流水线(NWFlowshop)调度问题是一个具有广泛应用背景和重要理论价值的组合优化问题,是许多实际生产调度过程的简化模型,广泛存在于炼钢、食品加工、化工和制药等工业领域。
随着当代科技的进步,研究方向逐渐转变到如何使效率最大化,这就要建立在有效的理论基础上。
本文通过蛙跳算法(SFLA)来解决零等待调度问题[2]。
1.3本文结构
本文第二章从总到分的介绍生产调度问题,分为流水线调度问题及零等待流水线调度问题;第三章介绍蛙跳算法概念、基本原理及相关研究情况,并为零等待调度问题编程进行铺垫,第四章为进NW的调度问题的编程及其仿真,包括编程内容,仿真结果等;第五章为全文的总结,包括完成全文的过程及自我感觉的不足之处等。
2生产调度问题
2.1生产调度问题
2.1.1生产调度问题简介
生产调度是指在满足约束的条件下确定工件的加工顺序使得目标函数达到最优。
其中FlowShop调度问题是一种典型的组合优化问题,它具有很强的工程应用背景,其特点是单个工件在各个机器阶段上的加工顺序是相同的。
该调度问题是一种典型的NP完全问题,随着问题规模的增大,解的规模将成指数增长。
因此,开发高效的优化算法具有极其重要的理论和应用价值。
求解这一问题的传统方法仅能处理小规模问题,并且存在计算量太大的缺点。
另有一些启发式算法虽能达到快速求解,但是存在求解质量不高、对向题的依赖性过强以及一旦完成决策就无法再修改等问题[2]。
调度是在满足某些约束(作业的先后关系、预定的完成时间、最早开始时间和资源能力等)的条件下对操作(作业)的排序,按照排序的次序给它们分配资源和时间,并且使某个执行目标达到最优(如总的执行时间、拖期时间和生产费用等)。
调度理论源于对制造车间生产计划与控制的研究,从诞生之日起它就引起了管理科学家和应用数学家等的重视,人们在这个领域发表了大量的文献著作,还有一些学者从不同的广度和深度考察了调度理论的发展状况。
经过几十年的研究与探索,调度理论逐渐发展成为一个比较完整的科学理论,在企业的生产中得到了一定程度的应用。
由于企业车间的生产计划与控制问题在所有调度问题中最具典型性,所以对车间调度问题的研究一直在调度理论中占据主导地位。
特别是近几年,更多领域的研究人员都对车间调度问题产生了浓厚的兴趣,他们各自用不同的技术和方法对这个问题进行了更为广泛、深入、细致的研究,取得了丰硕的成果。
生产调度,即对生产过程进行作业计划,作为一个关键模块,是整个先进生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机技术发展的核心。
有效的调度方法和优化技术的研究与应用,是实现先进制造和提高生产效益的基础和关键。
改善生产调度方案,可大大提高生产效益和资源利用率,进而增强企业的竞争能力。
生产调度问题是在一定的时间内,进行可用共享资源的分配和生产任务的排序,以满足某些指定的性能指标。
简单地说,生产调度问题就是按时间分配资源来完成任务的问题。
生产调度问题一般可以描述为:
针对某项可分解的工作,在一定约束条件下,如何安排其组成部分(操作)所占有的资源、加工时间、先后顺序,以获得产品制造时间或成本等最优。
从数学规划的角度来说。
生产调度问题可表述为等式或不等式约束下,对目标函数所进行的优化。
生产调度问题主要集中在车间的计划与调度方面。
制造系统的生产调度是针对一项可分解的工作(如产品制造),探讨在尽可能满足约束条件(如交货期、工艺路线、资源情况)的前提下,通过下达生产指令,安排其组成部分(操作)使用哪些资源、其加工时间及加工的先后顺序,以获得产品制造时间或成本的最优化。
在理论研究中,生产调度问题常被称为排序问题或资源分配问题。
生产调度中涉及的资源包括:
原料、设备(加工、存贮、运输)、人力、资金、能源等。
资源的详细分配受到产品的生产工艺的限制。
调度问题受到工厂管理方法的影响,调度问题的优化目标、优化策略随不同的管理方法而变化,因而其优化数学模型也不同。
可以这样说:
很难用一个生产环境的调度方案,去解决另一个生产环境的生产调度,因为几乎每一个生产环境都是唯一的。
由于生产环境的动态性,生产领域知识的多样性,调度问题的复杂性,必须将人、数学方法和信息技术结合起来研究生产领域的管理调度问题[3]。
2.1.2生产调度问题研究近况
调度问题的研究始于20世纪50年代,S.M.Johnson提出了解决n/2/F/
和部分特殊的n/3/F/
问题的优化算法,这是调度理论的开始;直至五十年代末期,许多研究成果主要是针对规模较小的单机和简单的流水车间问题,提出了解析优化方法,研究范围较窄,但是这些研究却成为经典调度理论的基石。
六十年代,多是利用混合或纯整数规划、动态规划和分枝定界法解决一些有代表性的问题,如Story的研究。
同时也有人开始尝试用启发式算法研究此问题,如Gavett提出的方法。
六十年代末期,经典调度理论体系初步形成。
七十年代,人们开始了算法复杂性的研究,多数调度问题被证明属于NP-完全问题或NP-难问题,难以找到多项式算法,因此开始关注启发式算法。
Panwalkar总结和归纳出了113条调度规则,并对其进行了分类。
七十年代末期,经典调度理论趋向成熟。
八十年代初期,Stephen等从三个方面对调度进行了重新考察,对未来发展做了分析和预测,认为理论与实际的结合将会成为研究热点。
这个富有挑战性的课题吸引了机械、计算机、管理等诸多领域的学者,许多跨学科的方法被应用到研究中。
其中最引人注目的就是以Carnegie-Mellon大学的M.Fox为代表的学者们开展的基于约束传播的ISIS研究,它标志了人工智能开始真正应用于调度问题。
八十年代后期,Giffler等人总结了生产调度的理论和实践方面的最新研究进展,从七个方面论述了生产调度的技术和方法,认为生产调度无论在理论还是实践上都已突破了传统界限[3]。
九十年代至今,各种方法在生产调度问题的研究中得到了充分的发挥,同时新的研究手段层出不穷。
纵观目前国内外的研究成果,从总体趋势上来讲,经典调度理论依然是调度理论不可动摇的基石,但智能调度理论己崭露头角,逐渐趋于成熟,且二者的融合也将会成为一种趋势。
2.1.3生产调度问题的分类及特点
车间调度问题的分类,根据研究的侧重点不同有多种分类方式,如按照资源约束种类和数量划分,分为单资源车间调度、双资源车间调度、多资源车间调度,本文研究的零等待策略的流水车间调度问题则属于按照零件和车间的构成划分:
(1)流水车间调度(Flowshop):
在这种车间中,每个零件都有相同的加工路径。
这样,机床设备的布局如同流水线一样,零件一次从流水线的一端浸入,最后从另一端流出。
(2)作业车间调度(Jobshop):
在这种车间中,机床设备的布局可以是任意的,因此零件的加工路径也是任意的,并且各零件的工序内容和数量也是任意的。
这是一种最一般的车间调度形式。
(3)开放式车间调度(Openshop):
每个零件的工序之间的加工次序是任意的。
零件的加工可以从任何一道工序开始,在任何一道工序结束。
(4)单车间调度(Singleshop):
在这种车间中,每个零件只能有一道工序[3]。
其他的分类方法还有按照零件的加工特点划分,例如分为静态车间调度、动态车间调度等,这里不再赘述。
车间调度问题的特点具有建模的复杂性,计算的复杂性,动态的随机性,多约束性,多目标性。
(1)复杂性:
车间中工件、机器、缓存和搬运系统之间相互影响、相互作用。
每个工件要考虑它的加工时间、安装时间和操作顺序等因素,因而相当复杂。
调度问题是在等式或不等式约束下求指标的优化,在计算量上往往是具有NP特性,随着问题规模的增大,其计算量急剧增加,使得一些常规的方法无能为力,对于这一点已经证明。
(2)随机性:
在实际的作业车间调度系统中存在很多随机的和不确定的因素,环境是不断变化的,在运行过程中会遇到多种随机干扰,比如工件到达时间的不确定性、作业的加工时间也有一定的随机性,而且生产系统中常出现一些突发偶然事件,如设备的损坏、修复、作业交货期的改变等,故作业车间调度过程是一个动态的随机过程。
(3)多约束性:
车间调度问题中资源的数量、缓存的容量、工件加工时间以及工件的操作顺序等都是约束。
此外还有一些人为的因素,如要求各机器上的负荷要平衡等。
(4)多目标性:
实际的车间调度问题是多目标的,而且这些目标之间往往是发生冲突的。
调度目标分为三类:
基于作业交货期的目标、基于作业完成时间的目标和基于生产成本的目标[3]。
2.1.4生产调度问题的调度策略
由于车间调度问题的复杂性,各种不同的具体问题往往有很多不同的解决方法,因此需要从策略上去考虑调度问题,以支持生产调度高层次的决策部分。
(1)并行和分布策略
一般调度问题很复杂,一旦问题规模加大就更难求解,因此不少研究者提出并行或分解的策略来解决调度问题。
多智能体系统的研究是目前分布式人工智能领域的研究热点。
大量的研究表明多智能体系统特别适用于解决复杂问题,尤其是那些经典方法无法解决的单元间有大量交互作用的问题。
由于调度问题的复杂性和并发性等特点,最近多智能体已在调度上得到了较多的应用。
多智能体系统不但速度快、可靠性高、可扩展性强、能处理带有空间分布的问题。
对不确定性数据和知识有较好的容错性;而且由于是高度模块化系统,因而能澄清概念和简化设计。
因此它必将得到更加广泛的应用。
(2)分解或成组策略
利用分解和成组调度策略可以大大降低问题的计算复杂性和规模,求得调度问题的较优解。
成组技术基本思想是根据工件、机器等之间的相似性将它们分组,利用组内的相似性降低问题的计算复杂性和规模,求得调度问题的较优解,同时优化系统的一些性能指标。
(3)动态重调度策略
由于实际的加工系统具有随机性和不确定性,特别在动态环境下,调度本身就是不断地动态重调度的过程。
基于目前的研究,动态调度的触发方式主要有:
周期调度、事件驱动调度、连续调度、以及周期与事件调度相结合的混合调度等。
滚动优化的思想很早就被应用于生产调度。
与常规调度方法相比,滚动调度可避免生产的大幅度波动,在滚动调度中,对某一些区间内的工件(工件窗口)进行调度,但按时间只对此区间内的部分工件进行实际加工,然后再向工件窗口中加入新工件来形成滚动。
滚动调度不仅可以应付刑S中的不确定性和突发偶然事件,而且每次只对工件窗口内的工件进行调度,可使问题求解规模大大减小。
(4)多目标决策
实际调度问题往往是多目标的,如最短生产期、最大生产利润,而且这些目标往往相互冲突。
对多目标优化问题,数学规划中的处理方法有约束法、评价函数法、功效函数法、分层序列法等。
(5)人机交互策略
为了取得好的调度结果,并考虑实际调度中存在的各种复杂因素,往往需要好的人机交互策略去启发和利用调度决策者的经验和知识。
大量的研究成功表明在目前的知识条件下人机交互策略是解决困难问题的一条有效途径[3]。
2.2流水车间调度问题
2.2.1流水车间调度问题的描述
流水车间调度问题一般可以描述为
个工件要在
台机器上加工,每个工件需要经过
道工序,每道工序要求不同的机器。
个工件在
台机器上加工的顺序相同,工件
在机器
上的加工时间是给定的,设为
。
问题的目标是确定
个工件在每台机器上的最优加工顺序,使最大流程时间达到最小。
对该问题常常作如下假设:
(1)每个工件在机器上的加工顺序是给定的;
(2)每台机器同时只能加工一个工件;
(3)一个工件不能同时在不同机器上加工;
(4)工序不能预订;
(5)工序的准备时间与顺序无关,且包含在加工时间中;
(6)工件在每台机器上的加工顺序相同,且是确定的。
令
表示工件
在机器
上的加工完成时间,
表示工件的调度,那么,对于无限中间存储方式,
个工件、
台机器的流水车间调度问题的完工时间可表示为:
(2-1)
(2-2)
(2-3)
最大流程时间为
,调度目标就是确定
,使得
最小[3]。
2.2.2流水车间调度问题的求解方法
流水车间调度问题的求解方法很多,启发式算法比较常见。
启发式算法(Heuristicalgorithm)是相对于最优算法提出的。
一个问题的最优算法是求解该问题的最优解而启发式算法是在可接受费用内寻找最好的解,但不一定能保证所得解的可行性和最优性,甚至在多数情况下,无法阐述所得解同最优解的近似程度。
事实上,在实际问题中,最优算法因问题的难度使其计算时问随问题规模的增加以指数速度增加,使人无法接受。
这时只能通过启发式算法求得问题的一个可行解。
启发式算法可定义为:
一个基于直观或经验构造的算法,在可接受的花费(指计算时间、占用空间等)下,给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度不一定事先可以预料。
3蛙跳算法
3.1蛙跳算法简介
蛙跳算法是新发展起来的一种启发式算法,它通过启发函数(某一数学函数)进行启发式搜索,从而找到问题的解。
事实上,蛙跳算法结合了以遗传行为为基础的Memetic算法和以社会行为为基础的粒子群优化PSO算法的优点。
3.1.1Memetic算法
Memetic算法是一种通过启发式搜索解决优化问题的群智能算法,受Dawkin提出的meme概念的启发而出现的。
1989年,由Moscato第一次使用这种算法。
"memetic"来自于单词"meme",meme指的是寄存于人或动物的大脑中能指导他们的行为并能传播的信息。
meme的内容,被称为memotype,类似于基因中的染色体。
一个想法或信息直到它被重复或传播才能成为一个meme。
所有可传播的知识都是memetic。
这种算法和遗传算法相似,不同的是,在MAs中,组成染色体的元素被称为memes,而不是基因。
Memetic算法的特征是所有的染色体和后代可以在进化之前通过局部搜索获得一些经验。
这样,Memetic算法通常被描述为增加了局部搜索的遗传算法[1]。
3.1.2粒子群算法
粒子群优化(ParticleSwarmOptimize,PSO)算法由Kennedy和Eberhart于1995年提出的,是一种基于群智能(SwarmIntelligence)方法的演化计算技术。
PSO算法通过模拟鸟群的捕食行为来实现优化问题的求解。
首先在解空间内随机初始化乌群,鸟群中的每一只鸟称为“粒子”,这些“粒子”具有位置和速度两个特征,在解空间内以某种规律移动,经过若干次迭代后找到所求解问题的最优解。
在每一次迭代中,粒子通过跟踪两个极值来更新自己的速度和位置。
第一个是粒子本身的最优解
,另一个极值是整个粒子群目前找到的最优解
。
PSO的速度、位置算是表示如下:
(3-1)
式中,
为粒子
在第
次迭代中的速度;
为粒子
在第
次迭代中的位置;
为粒子
的个体极值;
为在第
次迭代中的全局极值;
为在区间[0,1]上的随机数;
为惯性权重;
是认知系数,调节向
的飞行步长;
是社会系数,调节向
的飞行步长。
迭代过程中,粒子的速度和位置都限制在特定的范围内,同时
和
不断更新,最后输出
就是全局最优解[1]。
3.2蛙跳算法国内外研究情况
目前仅有很少的关于蛙跳算法的研究,相关的成果如下:
2003年Eusuff和Lansey首次将这种算法用来解决管道网络扩充中的管道尺寸最小化问题,在SFLA基础上提出了一个计算模型SFLANET,并且为了评价该模型的性能在一些实例上进行了测试[4]。
2005年Elbeltagi等在连续优化和离散优化方面将遗传算法、Memetic算法、微粒群算法、蚁群算法和蛙跳算法五种进化算法的模型和结果进行了比较[5]。
实验结果表明:
蛙跳算法在解决某些连续函数问题时成功率和收敛速度优于遗传算法,近似于粒子群算法[5]。
2006年Eusuff等将发展了的蛙跳算法用于解决组合优化问题,通过具体应用得出:
蛙跳算法是一种解决组合优化问题的有效工具,在收敛效果和速度上优于遗传算法[4]。
2007年,AlirezaRahimi,Vahed等提出了混合多目标蛙跳算法HMOSFLA用于解决多目标的混合型装配线排序问题,且HMOSFLA的性能优于MOGA,这一优势在求解大型问题时尤为突出[4]。
国内学者直到2007年才开始对蛙跳算法予以关注,相关成果更是很少,主要成果包括:
2007年,王辉,钱锋讨论了四种群体智能优化算法一蚁群算法、微粒群算法、人工鱼群算法和混合蛙跳算法,对其算法的原理、发展及应用进行了综述。
提出了群体智能优化算法统一框架模式,并对群体智能优化算法进一步发展进行了讨论[6]。
2007年,李英海等针对蛙跳算法局部更新策略引起的更新操作前后个体空间位置变化较大,容易降低收敛速度这一问题,提出了一种基于阈值选择策略的改进混合蛙跳算法。
通过不满足阈值条件的个体分量不予更新的策略,减少了个体空间差异,从而改善算法性能[7]。
蛙跳算法是一种新兴的群智能算法,对于该算法的研究还处于非常初步的阶段,仅有极少的文献,不过已经显示出较大的潜力,存在很大的发展空间。
(1)适用范围。
SFLA的应用仅在函数优化、聚类、组合优化、多目标优化方面有较少的应用,并且其应用大多数还和具体问题相关,仅停留在研究阶段,其它的很多应用还尚未开始。
显然,SFLA不会仅仅局限于目前的这些领域。
如果将SFLA引入机器学习、自动控制等领域,将大大地促进算法的研究和发展。
(2)数学基础。
SFLA的有效性在一些实例和数值实验中得到证明,但并没有给出收敛性、收敛速度估计、分布性、多样性等方面的数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- SFLA 算法 解决 NW 调度 问题