求解混合流水线调度问题的离散人工蜂群算法

《求解混合流水线调度问题的离散人工蜂群算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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问题编码本文采用简单工