Exact solution of the two-machine flow shop problem with three operations. (February 2022)

• Record Type: Journal Article
• Authors: Della Croce, Federico; Salassa, Fabio; T'kindt, Vincent
• Is Part Of: Computers & operations research. Volume 138(2022)
• Publication Date: 2022-02
• Subjects: Two-machine flow shop with three operations -- IP modeling -- Exact approach; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105595
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: We consider the NP-hard two-machine flow shop problem with three operations with the objective of minimizing the makespan. We exploit the links between this problem and another two-machine flow shop problem with common due date and jobs selection. We show how to tailor to this problem the constraint generation approach already successfully applied in the literature to the latter problem. Computational testing indicates that the proposed approach solves to optimality, within 120 s all instances with up to 40000 jobs. Highlights: A 2-machine flow shop problem with three operations is considered. The link between this problem and a 2-machine problem with common due date and job selection is exploited. A tailored constraint generation approach available in the literature is applied. Problems with up to 40000 jobs are solved to optimality within 120 s.