超启发式交叉熵算法求解模糊分布式流水线绿色调度问题  

Hyper-heuristic cross-entropy algorithm for green distributed permutation flow-shop scheduling problem with fuzzy processing time

作　　者：钱斌[1,2] 佘明哲 胡蓉[1,2] 郭宁[1] 向凤红[1] QIAN Bin;SHE Ming-zhe;HU Rong;GUO Ning;XIANG Feng-hong(College of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China;Yunnan Key Laboratory of Artificial Intelligence,Kunming University of Science and Technology,Kunming 650500,China)

机构地区：[1]昆明理工大学信息工程与自动化学院,昆明650500 [2]昆明理工大学云南省人工智能重点实验室,昆明650500

出　　处：《控制与决策》2021年第6期1387-1396,共10页Control and Decision

基　　金：国家自然科学基金项目(51665025,61963022)。

摘　　要：针对实际生产过程中普遍存在的加工时间不确定性,采用模糊数表示工件的加工时间,以同时最小化模糊最大完工时间和模糊总能耗为优化目标,建立模糊分布式流水线绿色调度问题(green distributed permutation flow-shop scheduling problem with fuzzy processing time,GDPFSPFPT)的模型,进而提出一种超启发式交叉熵算法(hyper-heuristic cross-entropy algorithm,HHCE)进行求解.首先,HHCE采用一种新颖的三角模糊数排序准则合理计算个体的目标函数值,可在算法搜索过程中较准确发现优质解区域;其次,HHCE在高层利用基于贡献率的评价方法确定8种特定邻域操作所构成的各排列的优劣,同时采用交叉熵(cross-entropy,CE)方法学习较优排列的信息并生成新排列,进而在低层把高层生成的每个排列作为一种启发式算法,对低层相应个体执行一系列邻域操作,以实现对问题解空间较多不同区域的搜索;然后,HHCE将基于非关键路径的节能策略用于对低层每代种群中的较优个体执行局部搜索,从而进一步提高算法获取低能耗非劣个体或解的能力;最后,仿真实验与算法对比表明,HHCE可有效求解GDPFSPFPT.For dealing with the processing time uncertainty widely existing in the real-world production process, this paper uses fuzzy number to represent each job’s processing time, and establishes a model of the green distributed permutation flow-shop scheduling problem with fuzzy processing time(GDPFSPFPT), whose optimization objectives are the fuzzy maximum completion time and the fuzzy total energy consumption. The, a hyper-heuristic cross-entropy algorithm(HHCE) is proposed for solving the GDPFSPFPT. Firstly, the HHCE algorithm adopts a novel ranking rule of triangular fuzzy number to reasonably calculate the objective function values of individuals, which is helpful in finding the promsing regions more accurately during the search process. Secondly, in the upper layer, the HHCE algorithm utilizes an evaluation method based on the contribution rate to estimate the permutations constructed by eight special neighbor operations, and also uses the cross-entropy(CE) method to learn the information of better permutations and generate new permutations. Then, for searching more different regions in solution space, the algorithm uses each permutation generated in the upper layer as a heuristic to perform a series of neighbor operations on the corresponding individuals in the lower layer. Thirdly, in order to enhence its ability of obtaining the non-dominated individuals or solutions with low energy consumption, the algorithm utilizes an energy-saving strategy based on non-critical path to perform local search on better individuals of each generation. Finally, simulations and comparisons demonstrate that the HHCE algorithm can effectively solve the GDPFSPFPT.

关 键 词：分布式流水线 模糊加工时间 绿色调度 多目标优化 超启发式算法 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]