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

Solving Hybrid Flow-shop Scheduling Problems by a Hybrid Discrete Artificial Bee Colony Algorithm

作　　者：李俊青[1,2] 潘全科[1,2] 王法涛[1,3] 

机构地区：[1]聊城大学计算机学院,山东聊城252059 [2]东北大学流程工业综合自动化国家重点实验室,辽宁沈阳110819 [3]北京邮电大学经济管理学院,北京100876

出　　处：《运筹与管理》2015年第1期157-163,共7页Operations Research and Management Science

基　　金：国家自然科学基金项目(61104179,61174187,61374187)

摘　　要：本文给出了一种离散的人工蜂群算法(HDABC)用于求解混合流水车间调度(HFS)问题。采用工件排序的编码方式,并设计了四种邻域结构。雇佣蜂依次分派到解集中每个解,采用结合问题特征的局部搜索策略完成挖掘搜索工作。跟随蜂随机选择两个解并挑选较优者作为当前解,完成进一步的探优过程。侦察蜂采用三种策略跳出局部极小。通过34个同构并行机HFS问题和2个异构并行机HFS实际调度问题的实验,并与当前文献中的典型算法对比,验证了本文提出的算法无论在算法时间还是在求解质量上,都具备良好的性能。In this paper , we propose a hybrid discrete artificial bee colony （ HDABC ） algorithm for solving the hybridflow-shop scheduling（HFS）problems.In the hybrid algorithm, each solution is coded by a job-permuta-tion mechanism .Four neighborhood structures are designed .The employed bees are assigned to each solution in the population set , to complete the local search task with a detailed designed local search approach .Onlooker bees randomly fetch two updated solutions and select the better one as the current solution , and then complete a further exploitation process .The scouts help the algorithm jump out of the local best by applying three different approaches .Then, the proposed algorithm is tested on the 34 identical parallel machines HFS and two un-related parallel machines HFS problems .The performance comparisons with other efficient algorithms are provided .It is concluded that the proposed algorithm is competitive to the compared existing algorithms for the problem consid -ered, in terms of searching quality , diversity, robustness and convergence ability .

关 键 词：混合流水车间调度 人工蜂群 局部搜索 邻域结构 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]