A population-based iterated greedy algorithm to minimize total flowtime for the distributed blocking flowshop scheduling problem. (September 2021)

• Record Type: Journal Article
• Authors: Chen, Shuai; Pan, Quan-Ke; Gao, Liang; Sang, Hong-yan
• Is Part Of: Engineering applications of artificial intelligence. Volume 104(2021)
• Publication Date: 2021-09
• Subjects: Flowshop -- Total flowtime -- Distributed -- Iterated greedy algorithm -- Blocking; 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.104375
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: We consider the distributed blocking flowshop scheduling problem (DBFSP) which is a meaningful generalization of the blocking flowshop scheduling problem in the distributed production environment. The objective of minimizing the total flowtime is relevant and important in the current dynamic manufacturing environment, but, as far as we know, it has not been investigated in the DBFSP previously. In this paper, a population-based iterated greedy (PBIG) algorithm is proposed to solve the DBFSP with the total flowtime criterion, which takes the advantage of both the population-based search approach and the iterated greedy algorithm. First, an effective constructive heuristic is proposed by integrating two existing constructive approaches to initialize the population with a high level of quality and diversity. Second, three different procedures to generate the offspring solutions are tested for the effective exploration capability, each of which rationally combines the destruction, reconstruction and selection operator. Third, the insertion neighborhood and swap neighborhood are investigated to enhance the local exploitation ability and a hybrid local search procedure that utilizes simultaneously both the two neighborhoods are proposed. The comprehensive experimental evaluation based on a total of 720 well-known instances shows that the proposed algorithms outperform the existing effective algorithms at a significant margin. Highlights: We study the distributed blocking flowshop scheduling problem for total flowtime. We propose a novel population-based iterated greedy algorithm. We propose a constructive heuristic to obtain good initial solutions. We propose three local search methods and three selection operators. We compare the proposed algorithms with effective algorithms in the literature.