工业工程

工业工程 ›› 2021, Vol. 24 ›› Issue (4): 83-92.doi: 10.3969/j.issn.1007-7375.2021.04.010

• 专题论述 • 上一篇    下一篇

基于Lévy Flight的混合GA在柔性作业车间调度问题中的性能分析

张正敏1, 管在林1, 岳磊2   

  1. 1. 华中科技大学 机械科学与工程学院，湖北 武汉 430074;
    2. 广州大学 机械与电气工程学院，广东 广州 510006
  • 收稿日期:2020-03-12 发布日期:2021-09-02
  • 作者简介:张正敏(1995-)，女，湖北省人，博士研究生，主要研究方向为高级计划与排程、智能算法
  • 基金资助:
    国家科技攻关计划资助项目(2018YFB1702700)；国家自然科学基金资助项目(51561125002)；国家自然科学基金青年科学基金资助项目(51905196)

Performance Analysis of Hybrid GA Based on Lévy Flight in Flexible Job-shop Scheduling Problem

ZHANG Zhengmin1, GUAN Zailin1, YUE Lei2   

  1. 1. School of Mechanical Science and Engineering, Huazhong University of Science & Technology, Wuhan 430074, China;
    2. School of Mechanical and Electrical Engineering, Guangzhou University, Guangzhou 510006, China
  • Received:2020-03-12 Published:2021-09-02

RichHTML

23

PDF

5412

摘要： 近年来，柔性作业车间调度问题(FJSP)由于其NP难特性与在制造系统中的广泛应用被大量关注。为提高该类问题求解效率，本文在标准Lévy flight的基础上提出了一种新的离散Lévy flight搜索策略，并将该策略与遗传算法框架结合，形成一种离散Lévy flight策略的混合遗传算法。该混合算法通过使用离散Lévy flight搜索策略对每代精英种群进行变步长搜索，提高了算法的局部搜索能力，增强了种群多样性。本文通过将CS、GA和TLBO等经典算法作为对比算法，对不同规模的54个FJSP算例进行实验，证明了所提出的算法具备更好的收敛效果与稳定性，适合于求解大规模FJSP。

关键词: 柔性作业车间调度问题(FJSP), Lévy flight搜索策略, 混合遗传算法

Abstract: In the past few years, considerable attention has been paid to the flexible job-shop scheduling problem (FJSP) due to its NP-hard nature and extensive applications in manufacturing systems. To improve the efficiency of solving FJSPs, a new discrete Lévy flight search strategy is proposed based on the standard Lévy flight, and by combining this strategy with basic genetic algorithm framework, a hybrid genetic algorithm is established. The hybrid algorithm uses a discrete Lévy flight search strategy to perform a variable step-length search on elite population of each generation, which improves the local search capability of the algorithm and enhances the diversity of the population. For comparison, some other algorithms including CS, GA, TLBO are used to conduct experiments on 54 FJSP examples with different scales. The results indicate that the proposed Lévy-GA outperform its competitions in terms of the robustness and convergence effects. Moreover, the proposed hybrid genetic algorithm is also proved to be suitable for solving large-scale FJSPs.

Key words: flexible job-shop scheduling problem (FJSP), Lévy flight search strategy, hybrid genetic algorithm

中图分类号: