流水车间调度问题是一类经典的组合优化问题,但传统的流水车间调度问题因忽视了不同工序间的缓冲约束,难以被应用于一些复杂的实际问题.据此,提出了一种不同工序具有不同缓冲约束的流水车间调度问题,并设计了离散人工蜂群算法DABC(discrete artificial bee colony)进行求解.算法基于排列形式进行编码,以PF_NEH(profile fitting&NEH)算法为基础构造初始解,提高初始种群初始解的质量;在雇佣蜂阶段,在迭代贪婪算法基础上提出了分段破坏迭代贪婪算法产生邻域个体;在观察蜂阶段,同时挑选较优解和较差解,并基于Path-relinking算法进一步挖掘搜索;在侦查蜂阶段,除了选择解的质量较差的个体被淘汰外,还设计了扰动策略使算法能跳出局部收敛.通过标准实例测试,验证了所提算法的有效性.%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 initial populations to improve the quality of populations. In employed bee phase, on the basis of iterative greedy algorithm, the iterated greedy algorithm with destruction operation of sections is proposed to generate the neighborhood individual. In onlooker bee phase, the better and worse solutions are selected together, and Path-relinking algorithm is proposed to make further search. In scout bee phase, in addition to eliminating worse individuals, perturbation strategy is designed to jump out of the local best. Effectiveness of the proposed algorithm is validated through a group of benchmark instances.
展开▼
