改进人工蜂群算法求解柔性作业车间调度问题

Improved Artificial Bee Colony Algorithm for Flexible Job Shop Scheduling Problem

针对柔性作业车间调度问题,提出了改进的人工蜂群算法。算法采用基于混沌序列思想、SPT启发式规则和随机方式三种方式共同产生初始种群以保证初始解的质量。针对算法的搜索过程,引入相似度概念将种群分为先进和后进两个群,并针对两个群特点分别采用搜索范围不同的搜索策略以加强寻优性能;采用锦标赛选择策略代替原算法的轮盘赌选择方式以改善过早收敛现象;根据局部解特点,改变原来的未变个体的替换方式,采用按一定比例替换具有相同最优值的个体,保留当前最优的同时,又具有跳出局部最优解的能力。最后通过标准实例求解并与其它论文结果对比,证明了该改进算法的有效性。

An improved artificial bee colony algorithm was proposed for flexible job shop scheduling problem.In this paper,the working procedure and the machine were separated by two different encoded modes.The chaotic sequence thought and the shortest processing time heuristic rules and the random method were used to generate the initial population in order to guarantee its quality.In search process,the concept of similarity is introduced to divide the population into two groups and adopt two different search strategies to enhance the optimization performance;Replace the roulette selection strategy with the tournament selection strategy to solve the problem of premature convergence;Based on the characteristic of the local optimum solution,drop the primary replacement mode and replace the individuals with the same optimal value with those generated randomly in a certain proportion,so that the algorithm can preserve the current optimal solution and avoid falling into the local optimum solution.Finally,according to solve the standard instances and contrast with the other papers＇ results,v erify this improved algorithm having good peformances.