欢迎来到天天文库
浏览记录
ID:28152808
大小:80.50 KB
页数:9页
时间:2018-12-07
《求解混合流水线调度问题的离散人工蜂群算法》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、求解混合流水线调度问题的离散人工蜂群算法摘要:本文给出了一种离散的人工蜂群算法(HDABC)用于求解混合流水车间调度(IIFS)问题。采用工件排序的编码方式,并设计了四种邻域结构。靡佣蜂依次分派到解集屮每个解,采用结合问题特征的局部搜索策略完成挖掘搜索工作。跟随蜂随机选择两个解并挑选较优者作为当前解,完成进一步的探优过程。侦察蜂采用三种策略跳出局部极小。通过34个同构并行机HFS问题和2个异构并行机HFS实际调度问题的实验,并与当前文献中的典型算法对比,验证了本文提出的算法无论在算法时间还是在求解质量上,都具备良好的性能。关键词:混合流水车间
2、调度;人工蜂群;局部搜索;邻域结构屮图分类号:TP18文章标识码:A文章编号:1007-3221(2015)01-0157-07引言调度问题是工业工程领域中关键技术问题,混合流水线(HybridFlowShop,HFS)调度问题属于NP—难问题,是调度问题的一个特例,由于其广泛存在于生产流程中,已成为近年来的研究热点。在11FS中,加工流程划分为几个阶段,每个加工阶段由若干同型或异构机床组成,任何一个工件需要严格按照相同的加工顺序依次流经每个加工阶段,到达任意阶段时,可以从多个并行机床中选择一个进行加工。文献是最早采用分支一定界法求解HFS问
3、题的文献,之后出现了许多不同的算法。按照加工阶段的不同,HFS-般分为三种类型:2-阶段HFS、3-阶段HFS和m-阶段HFS。当前,m-阶段HFS由于更贴近生产实际而成为研宄热点。研宄m-阶段HFS的主要文献有:1998年,Portman设计了一种遗传算法和分支一定界相结*合的方法;Neron给出了在5-阶段下求解HFS问题的优化算法;Oguz则设计了一种基于遗传算法的混合方法;Ruiz等针对顺序决定的准备时间的HFS开发了一种基于遗传算法的方法;Janiak则采用基于禁忌搜索和模拟退火的启发式方法;此外,Niu等设计了量子启发式免疫算法;
4、Kahrama设计了一种并行贪婪优化算法;Liao等提出了一种结合瓶颈机床的粒子群优化算法。上述优化算法用于求解HFS问题,有些收敛能力不足,有些则易于陷入局部极小。人工蜂群(ArtificialBeeColony,ABC)算法是一种新的群体智能优化方法,由Karaboga等于2005年首次提出,主要应用于求解连续函数优化问题。文献针对ABC方法应用到离散问题领域,提出了离散人工蜂群算法,并应用求解流水线调度。文献则把离散ABC方法应用到求解柔性作业车间调度(FlexiblejobShopschedulingProblem,FJSP)问题中。
5、上述文献表明,ABC算法由于有效平衡了全局搜索和局部搜索能力,可以有效应用于求解复杂调度问题。本文结合ABC算法的特点,提出了一种求解11FS问题的离散ABC方法。1问题描述与定义HFS问题如下:假设有M个机床个工件和s个加工阶段。每个加工阶段si包含mi个同型或异构的并行机床,每个工件Ji通过加工阶段si时,可任选其中一个机床进行加工。为构建HFS问题模型,定义如下符号:Mi为加工阶段i中的并行机床集合;pijk为工件j在加工阶段i选择机床k的加工时间(pijk^O);sij为工件j在加工阶段i的开工时间;cij为工件j在加工阶段i的完工时
6、间;L为极大数。如果在加工阶段i工件j选择机床k进行加工否则在加工阶段i,如果工件j和h在同一机床上加工,并且j是h的紧前工作否则有了上述符号,HFS问题的模型如下:其中,不等式约束(2)描述同一工件的工序间的先后约束关系,不等式约束(3)限制同一个机床上有紧前关系的工件间不允许出现加工时间重叠,等式约朿(4)定义每个工件的每个加工阶段只能选择一个机床加工。2基本人工蜂群算法人工蜂群算法是由Karaboga等于2005年提出的一种新的群体智能优化算法,是模拟蜜蜂寻找食物的过程而演化的仿生过程。在基本ABC中,食物源(foodsource)和人
7、工蜜蜂(artificialbees)是基本构成要素。人工蜜蜂又被分为三种,即雇佣蜂(Employedbees)、跟随蜂(Onlookerbees)和侦察蜂(Scoutbees)o雇佣蜂的任务是在随机食物源周围进一步挖掘,以便找到更好的食物源;在雇佣蜂把挖掘后的信息带回后,守在蜂巢中的跟随蜂按照一定概率选择较好的食物,进一步搜索挖掘;当某些食物在经过一定周期后,未曾发生改变,则派出侦察蜂随机搜索新的食物源。ABC算法中基木控制参数包括:解集大小SN,解无更新而被丢弃的周期大小Ls,雇佣蜂数目E,,跟随蜂数目os,侦察蜂数0Ss和终止条件。3混
8、合算法框架基本ABC用子求解连续优化问题,因而,应用于求解离散调度问题需要进行离散化。结合问题特征,本文对基本ABC算法进行离散化设计。3.1问题编码本文采用简单工
此文档下载收益归作者所有