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

Improved artificial bee colony algorithm for distributed and flexible job-shop scheduling problem

针对分布式柔性作业车间调度问题的特点,提出一种改进人工蜂群算法.首先,建立以最小化最大完工时间为优化目标的分布式柔性作业车间调度优化模型;然后,改进基本人工蜂群算法以使其适用于求解分布式柔性作业车间调度问题,具体的改进包括设计一种包含三维向量的编码方案,结合问题特点针对性地设计多种策略用于种群初始化,在雇佣蜂改良搜索操作中设计多种有效的进化操作算子,并在跟随蜂搜索操作中引入基于关键路径的局部搜索算子以提升算法的局部搜索能力;最后,利用扩展柔性作业车间通用测试集得到的测试数据设计实验验证算法性能,使用正交试验法优化算法参数设置.仿真实验结果表明,改进后的人工蜂群算法能有效求解分布式柔性作业车间调度问题.

This paper analyzes the characteristics of the distributed and flexible job-shop scheduling problem and proposes an improved artificial bee colony algorithm for solving the problem. Firstly, a scheduling model is established to minimize the makespan. Then, some improvements are applied to the basic artificial bee colony algorithm so that it can solve this problem effectively, including a three-dimension encoding scheme, effective population initialization method based on the characteristics of the distributed and flexible job-shop scheduling problem, many evolutionary operators are designed for the employed bee search phase, and what’s more, in onlooker bee phase, a local search operator based on the critical path is introduced to improve the local search capability of the algorithm. Finally, an experiment is designed to verify the performance of the algorithm based on the test data expanded from common benchmark of the flexible job-shop scheduling problem, and orthogonal test is used to optimize the parameters in the proposed algorithm. The results show that the improved artificial bee colony algorithm can effectively solve the problem.