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

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

作　　者：李尚函 胡蓉[1,2] 钱斌 张梓琪[1] 金怀平 LI Shang-han;HU Rong;QIAN Bin;ZHANG Zi-qi;JIN Huai-ping(School of Information Engineering and Automation,Kunming University of Science and Technology,Kunming Yunnan 650500,China;School of Mechanical and Electronic Engineering,Kunming University of Science and Technology,Kunming Yunnan 650500,China)

机构地区：[1]昆明理工大学信息工程与自动化学院,云南昆明650500 [2]昆明理工大学机电工程学院,云南昆明650500

出　　处：《控制理论与应用》2020年第2期316-330,共15页Control Theory & Applications

基　　金：国家自然科学基金项目(51665025,61963022);云南省应用基础研究计划重点项目;云南省教育厅科学研究基金项目(2017ZZX149)资助.

摘　　要：本文提出一种混合超启发式遗传算法(HHGA),用于求解一类采用三角模糊数表示工件加工时间的模糊柔性作业车间调度问题(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.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TH165[自动化与计算机技术—控制科学与工程]