求解批量流水线调度问题的离散蜂群算法

A Discrete Artificial Bee Colony Algorithm for Lot-streaming Flow Shop Scheduling Problem

针对批量流水线调度问题,提出一种离散人工蜂群算法来优化最大完成时间。研究了计算最大完工时间的前向和后向方法,并提出插入邻域快速算法。与传统的人工蜂群算法不同,离散人工蜂群算法采用工件序列编码,运用扩展的NEH方法产生初始种群,使用自适应的移动选择策略和路径链接方法生成新解,利用基于插入邻域快速算法的局部搜索来加强局部开发能力。同时为了保持种群的多样性,防止算法陷入局部极小,当种群相似度达到一定值时进行算法重启。仿真实验表明该算法可行、高效。

A discrete artificial bee colony（DABC） algorithm was presented for solving the lot-- streaming flow shop scheduling problem（LFSP） with the objective of minimizing the maximum com- pletion time, i. e. , makespan. Two methods for calculating makespan, namely forward pass calcula tion and backward pass calculation were investigated respectively, and a speed--up approach to evalu- ate the whole insertion neighborhood was presented. Unlike the traditional ABC algorithm, in the proposed DABC algorithm, individuals were represented as discrete job permutations. An initialization taking advantage of an extended NEH（Nawaz--Enscore--Ham） heuristic was used to produce a popu- lation with certain diversity and quality. An adaptive strategy based on insert and swap operators and a path re--linking strategy were utilized to generate neighboring food sources. An effective local search based on insertion neighborhood was fused to enhance the algorithm ＇ s exploitation. At the same time, to maintain diversity of the population and avoid to trapping into a local optimum, a restart mechanism was performed when the similarity of the individuals in the population was larger than a given threshold value. Extensive experiments were provided and the comparisons show that the pro- posed DABC algorithm is effective and efficient for the LFSP.