求解高维多目标调度的新型人工蜂群算法

Novel Artificial Bee Colony Algorithm for Solving Many-objective Scheduling

高维多目标连续优化问题已得到广泛研究,而高维多目标组合优化问题的进展相对较小,虽然人工蜂群(Artificial Bee Colony,ABC)算法已成功应用于多种生产调度问题,但很少被用来求解高维多目标调度问题,而且高维多目标调度自身的研究进展也非常小。针对高维多目标柔性作业车间调度问题,文中提出了一种新型ABC算法以同时优化最大完成时间、总延迟时间、总能耗和机器总负荷。与常规柔性作业车间调度问题不同,上述问题考虑了总能耗,使其成为绿色调度问题。新型ABC具有明显不同于现有ABC算法的新特点,其跟随蜂(onlooker bee)的数量小于引领蜂(employed bee),引领蜂侧重于全局搜索,而跟随蜂只进行局部搜索,通过两类蜜蜂彼此各异的搜索方式来避免算法陷入局部最优。同时,该算法将跟随对象限定为质量较好的部分引领蜂和外部档案成员,其他引领蜂无法成为跟随对象,以避免计算资源浪费在较差解的搜索上,并给出了侦查蜂(scout)新的处理策略。测试实例的仿真实验表明,高维多目标调度问题中非劣解数量占种群规模的比例明显低于高维连续优化问题。将新型ABC与多目标遗传算法和变邻域搜索进行比较,实验结果表明,新型ABC在求解高维多目标调度方面比对比算法更有优势,计算结果更好。

Many-objective continuous optimization problem has been considered extensively while there are few studies on many-objective combination optimization problem.Artificial bee colony(ABC)algorithm has been successfully applied to solve various production scheduling problem,but ABC is seldom used to solve many-objective scheduling problem and many-objective scheduling problem itself is also seldom handled.Aiming at multi-objective flexible job shop scheduling problem,a new ABC algorithm is proposed to optimize simultaneously maximum completion time,total tardiness,total energy consumption and total workload.Unlike the general flexible job shop scheduling problem,the above problem is green scheduling one because of the inclusion of total energy consumption.The new ABC has new characteristics which are obviously different from the existing ABC algorithm.Its number of onlooker bees is less that of employed bees,employed bee focuses on global search while onlooker bee only carries out local search,which avoids the algorithm from falling into local optimization through the different search methods of two kinds of bees.At the same time,onlooker bee just selects some best employed bees or members of external file,and some employed bees cannot become follower objects to avoid wasting computing resources on search for poor solutions.A new strategy is adopted to handle scout.The simulation results show that the ratio of the number of non-dominated solutions to population scale for many-objective scheduling problem is notably less than the same ratio for many-objective continuous optimization problem.Compared with multi-objective genetic algorithm and variable neighborhood search,the computational results show that ABC has better results than two comparative algorithms on solving the considered many-objective scheduling.