人工蜂群算法求解混合约束流水车间调度问题-《计算机技术与发展》

文章信息/Info

Title:: Artificial Bee Colony Algorithm for Flow Shop Scheduling Problem with Mixed Buffering Requirements

Author(s):: SUN Hou-quan; ZHANG Qi-liang; School of Electrical and Information Engineering,Jiangsu University of Science and Technology,Zhangjiagang 215600,China

Keywords:: discrete artificial bee algorithm; flow shop scheduling; makespan; mixed buffering requirements

摘要:: 流水车间调度问题是一类经典的组合优化问题,但传统的流水车间调度问题因忽视了不同工序间的缓冲约束,难以被应用于一些复杂的实际问题。据此,提出了一种不同工序具有不同缓冲约束的流水车间调度问题,并设计了离散人工蜂群算法 DABC(discrete artificial bee colony)进行求解。算法基于排列形式进行编码,以 PF_NEH(profile fitting & NEH)算法为基础构造初始解,提高初始种群初始解的质量;在雇佣蜂阶段,在迭代贪婪算法基础上提出了分段破坏迭代贪婪算法产生邻域个体;在观察蜂阶段,同时挑选较优解和较差解,并基于 Path-relinking 算法进一步挖掘搜索;在侦查蜂阶段,除了选择解的质量较差的个体被淘汰外,还设计了扰动策略使算法能跳出局部收敛。通过标准实例测试,验证了所提算法的有效性。

Abstract:: The flow shop scheduling is a classical combinatorial optimization problem,but the traditional flow shop scheduling is difficult to be applied to some complex practical problems because it ignores the buffer constraints between different processes. Therefore,we propose a new flow shop scheduling problem with different stage buffering requirements,and put forward the discrete artificial bee colony( DABC) to resolve it. In DABC,the permutation based encoding schemes is designed,PF_NEH algorithm is used to construct the initialpopulations to improve the quality of populations. In employed bee phase,on the basis of iterative greedy algorithm,the iterated greedyalgorithm with destruction operation of sections is proposed to generate the neighborhood individual. In onlooker bee phase,the better andworse solutions are selected together,and Path-relinking algorithm is proposed to make further search. In scout bee phase,in addition toeliminating worse individuals,perturbation strategy is designed to jump out of the local best. Effectiveness of the proposed algorithm isvalidated through a group of benchmark instances.