An effective hybrid meta-heuristic for flexible flow shop scheduling with limited buffers and step-deteriorating jobs. (November 2021)

• Record Type: Journal Article
• Authors: Zheng, Qian-Qian; Zhang, Yu; Tian, Hong-Wei; He, Li-Jun
• Is Part Of: Engineering applications of artificial intelligence. Volume 106(2021)
• Publication Date: 2021-11
• Subjects: Flexible flow shop -- Limited buffers -- Step-deteriorating jobs -- Genetic algorithm -- Variable neighborhood search -- Simulated annealing; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2021.104503
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: 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. Highlights: 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.