Abstract: In this paper, we propose a hybrid discrete artificial bee colony(HDABC)algorithm for solving the hybrid flow-shop scheduling(HFS)problems. In the hybrid algorithm, each solution is coded by a job-permutation 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 considered, in terms of searching quality, diversity, robustness and convergence ability.

Key words: hybrid flow shop scheduling, artificial bee colony algorithm, local search, neighborhood structure

摘要： 本文给出了一种离散的人工蜂群算法(HDABC)用于求解混合流水车间调度(HFS)问题。采用工件排序的编码方式,并设计了四种邻域结构。雇佣蜂依次分派到解集中每个解,采用结合问题特征的局部搜索策略完成挖掘搜索工作。跟随蜂随机选择两个解并挑选较优者作为当前解,完成进一步的探优过程。侦察蜂采用三种策略跳出局部极小。通过34个同构并行机HFS问题和2个异构并行机HFS实际调度问题的实验,并与当前文献中的典型算法对比,验证了本文提出的算法无论在算法时间还是在求解质量上,都具备良好的性能。

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