The distributed flowshop scheduling problem with delivery dates and cumulative payoffs. (March 2022)

• Record Type: Journal Article
• Authors: Li, Yuan-Zhen; Pan, Quan-Ke; He, Xuan; Sang, Hong-Yan; Gao, Kai-Zhou; Jing, Xue-Lei
• Is Part Of: Computers & industrial engineering. Volume 165(2022)
• Publication Date: 2022-03
• Subjects: Distributed permutation flowshop scheduling -- Release time -- Delivery dates -- Cumulative payoffs -- Heuristics -- Iterated greedy algorithm; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.107961
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: The DPFSP with delivery dates and cumulative payoffs is addressed. A mathematical model is built to formulate the new problem. The upper and lower bounds of the problem are given. The Insert-Pruning and nine heuristic algorithms are proposed. An improved IG algorithm is proposed. Abstract: In the classic distributed permutation flowshop scheduling problem (DPFSP), there are more studies on the minimization of makespan, total flow time, total tardiness, etc. This paper studies a new problem with a new optimization goal, the DPFSP with delivery dates and cumulative payoffs. It is a variation of the DPFSP with job release dates that maximizes the total payoff with a stepwise job objective function. The main contributions are summarized as follows. (1) A mathematical model is built to formulate the new problem. (2) The characteristics of the problem are explored, and the upper and lower bounds of the problem are given. Based on the problem-specific knowledge, an algorithm named Insert-Pruning is proposed to improve the efficiency of search. (3) Nine heuristic algorithms are proposed, including DRI, DRA, DEI, DEA, DNI, DNA, DII, DIA and DFF . (4) Combined with the characteristics of the problem, some modifications and improvements have been made to the IG algorithm to solve it, including the destruction method, the local search method and the acceptance criterion. (5) The experimental results show that the presented algorithm significantly outperforms the existing algorithms in the literature. In comparison with other competing algorithms in different dimensions, our algorithm has shown better performance, which verifies the effectiveness of this algorithm.