An effective hybrid meta-heuristic for flexible flow shop scheduling with limited buffers and step-deteriorating jobs

• Published in: Engineering applications of artificial intelligence 2021-11, Vol.106, p.104503, Article 104503
• Main Authors: Zheng, Qian-Qian, Zhang, Yu, Tian, Hong-Wei, He, Li-Jun
• Format: Article
• Language: English
• Subjects: Flexible flow shop; Genetic algorithm; Limited buffers; Simulated annealing; Step-deteriorating jobs; Variable neighborhood search
• ISSN: 0952-1976; 1873-6769
• DOI: 10.1016/j.engappai.2021.104503

This paper addresses a flexible flow shop scheduling problem considering limited buffers and step-deteriorating jobs, where there are multiple non-identical parallel machines. A mixed integer programming model is proposed, with the criterion of minimizing the makespan and total tardiness simultaneously. To handle this problem, an effective hybrid meta-heuristic algorithm, named GVNSA, is developed based on genetic algorithm (GA), variable neighborhood search (VNS) and simulated annealing (SA). In the algorithm, with a two-dimensional matrix encoding scheme, the NEH (Nawaz–Enscore–Ham) heuristic and bottleneck elimination method are implemented to determine the initial population. A three-level rolling translation approach is designed for decoding. To balance the exploration and exploitation abilities, three effective steps are executed: 1) partial matching crossover and mutation strategy based on multiple neighborhood search structures are imposed on the GA operators; 2) a VNS with SA is introduced to re-optimize some individuals from GA, where four neighborhood structures are constructed; 3) a modified CDS (Campbell–Dudek–Smith) heuristic is embedded to disturb population in the mid-iteration. Numerical experiments are carried out on test problems with different scales. Computational results demonstrate that the proposed GVNSA can obtain higher quality solutions in comparison with other heuristics and meta-heuristics existing in literature. •A bi-objective flexible flow shop scheduling problem is studied.•Limited buffers and step-deteriorating jobs are considered.•A new mathematical model is formulated for the problem.•An effective hybrid meta-heuristic is developed.•Results confirm the efficiency of the proposed hybrid meta-heuristic.