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

An improved artificial bee colony algorithm for fuzzy flexible job-shop scheduling problem

中文关键词  车间调度  人工蜂群算法  混沌理论  局部搜索  左移策略

英文关键词  job shop scheduling  artificial bee colony algorithm  chaos theory  local search  left-shift strategy

中文摘要

      模糊柔性作业车间调度问题(FFJSP)是柔性作业车间调度问题(FJSP)的拓展, 具有很强的现实意义. 针对 FFJSP, 本文提出了一种基于领域搜索的改进人工蜂群算法. 该算法以最小化最大模糊完工时间为目标. 首先, 为了 提高初始种群的多样性, 引入混沌理论来初始化种群. 其次, 为了提高算法的局部搜索能力, 采用4种邻域结构对蜜 源进行邻域搜索. 为了进一步优化蜜源和加快种群的收敛速度, 采用了一种新颖的交叉操作. 并且在解码的过程中 采用左移策略, 从而很好地利用机器的空闲时间. 最后, 选取了3组通用数据集来测试算法的性能, 并与代表性算法 进行比较. 结果表明, 对于大部分实例, 本文所提出的的算法的结果要优于与之对比的算法.

英文摘要

      Fuzzy flexible job-shop scheduling problem (FFJSP) is an extension of flexible job-shop scheduling problem (FJSP), it has a strong practical significance. In this paper, an improved artificial bee colony algorithm based on neighborhood search is proposed to solve FFJSP. The objective is to minimize maximum fuzzy completion time. Firstly, chaos theory is used to initialize the population, which ensure the diversity of the initial population. In addition, In order to improve the local search ability of the algorithm, four neighborhood structures are adopted and a novel crossover operation is used to further optimize nectar source and accelerate the population convergence rate. The left-shift strategy is adopted during the decoding process, which can make good use of the idle time of the machine, so as to reduce the maximum fuzzy completion time. Finally, three sets of general data sets are selected to test the performance of the algorithm and compared with the representative algorithms. The results show that for most cases, the proposed algorithm is better than the comparison algorithms.