超启发式遗传算法求解模糊柔性作业车间调度

Hyper-heuristic genetic algorithm for solving fuzzy flexible job shop scheduling problem

中文关键词  三角模糊数排序  模糊加工时间  柔性作业车间  超启发式算法

英文关键词  triangular fuzzy number sorting  fuzzy machining time  flexible job shop  hyper-heuristic algorithm

中文摘要

      本文提出一种混合超启发式遗传算法(hybrid hyper-heuristic genetic algorithm，HHGA)，用于求解一类采用三角模糊数表示工件加工时间的模糊柔性作业车间调度问题(fuzzy flexible job shop scheduling problem，FFJSP)，优化目标为最小化最大模糊完工时间（即makespan）. 首先，详细分析现有三角模糊数排序准则性质，并充分考虑取大操作的近似误差和模糊度，设计一种更为准确的三角模糊数排序准则，可合理计算FFJSP和其他各类调度问题解的目标函数值. 其次，为实现对FFJSP解空间不同区域的有效搜索，HHGA将求解过程分为两层，高层利用带自适应变异算子的遗传算法对6种特定操作（即6种有效邻域操作）的排列进行优化；低层将高层所得的每种排列作为一种启发式算法，用于对低层相应个体进行操作来执行紧凑的变邻域局部搜索并生成新个体，同时加入模拟退火机制来避免搜索陷入局部极小。最后，仿真实验和算法比较验证了所提排序准则和HHGA的有效性.

英文摘要

      In this paper, a hybrid hyper-heuristic genetic algorithm (HHGA) is proposed to minimize the maximum fuzzy completion time (i.e., makespan) for the fuzzy flexible job shop scheduling problem (FFJSP), in which the job’s processing time is represented by using triangular fuzzy number. Firstly, after analyzing the properties of the existing sorting rules on triangular fuzzy number in detail, and fully considering the approximate error and the ambiguity of the operation of taking the bigger, a more accurate triangular fuzzy number sorting rule is designed, which can reasonably calculate the objective function values of the solutions for FFJSP and other various scheduling problems. Secondly, to realize the effective search in different regions of FFJSP’s solution space, HHGA divides the solving process into two layers. The upper layer uses the genetic algorithm with adaptive mutation operator to optimize the permutation of six special operations, i.e., six effective neighbor operations. The lower layer uses each permutation obtained from the upper layer as a heuristic to perform operations on the corresponding individual of the lower layer for executing a compact variable neighborhood local search and generating new individual, and meanwhile adds the simulated annealing mechanism to overcome the local-optimality trap. Finally, simulation experiments and algorithm comparisons verify the effectiveness of the proposed sorting rules and HHGA.