A branch-and-cut approach for the distributed no-wait flowshop scheduling problem. (December 2022)

• Record Type: Journal Article
• Authors: Avci, Mustafa; Avci, Mualla Gonca; Hamzadayı, Alper
• Is Part Of: Computers & operations research. Volume 148(2022)
• Publication Date: 2022-12
• Subjects: Scheduling -- Flowshop scheduling -- Distributed no-wait -- Branch-and-cut; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.106009
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: The distributed no-wait flowshop scheduling problem (DNWFSP) is an extension of the permutation flowshop scheduling problem with multiple factories and no-wait constraints. The DNWFSP consists of two decisions, namely, assigning jobs to the factories and sequencing the set of jobs assigned to the same factory. The no-wait constraints require that jobs have to be processed without any interruption between operations. Since the introduction of the DNWFSP, a number of metaheuristic approaches were developed to solve it. However, there exists no exact solution approach for the DNWFSP to the best of our knowledge. In this regard, a branch-and-cut (BC) algorithm is proposed to solve the DNWFSP. The proposed BC is integrated with a heuristic algorithm to obtain good upper bounds. Moreover, a set of symmetry breaking constraints are employed in the models to strengthen the formulations. The performance of BC is evaluated on a set of benchmark problem instances available in the related literature. The proposed BC is numerically compared with mixed-integer programming formulations of the DNWFSP which are solved by a commercial solver. The results obtained from the computational experiments reveal the effectiveness of the proposed approach. The proposed BC is able to solve all small-size instances, as well as, 206 out of 660 large-size instances to optimality. Besides, it is worth to mention that the average percentage gap for the large-size instances with two factories is only 0.43%. Highlights: The distributed no-wait flowshop scheduling problem is addressed. An exact solution algorithm is proposed for its solution. The performance of the proposed algorithm has been tested on a set of benchmark instances. The algorithm provides high quality solutions for the problem instances.