Logic-based Benders decomposition for the preemptive flexible job-shop scheduling problem. (April 2023)

• Record Type: Journal Article
• Authors: Juvin, Carla; Houssin, Laurent; Lopez, Pierre
• Is Part Of: Computers & operations research. Volume 152(2023)
• Publication Date: 2023-04
• Subjects: Flexible job-shop scheduling -- Preemption -- Benders decomposition -- Mixed-integer programming -- Constraint programming; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2023.106156
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: In this paper, we focus on exact methods to solve the preemptive flexible job-shop scheduling problem with makespan minimisation objective function. Mathematical and constraint programming models enable the resolution of this problem for small instances. However, as an NP-hard problem, the cost of solving grows rapidly when considering larger instances. In this regard, we propose a logic-based Benders decomposition that relies on an efficient branch-and-bound procedure to solve the subproblem representing a pure (non-flexible) preemptive job-shop scheduling problem. Computational experiments are carried out and show the very good performance of our proposals. Highlights: The preemptive flexible job-shop scheduling problem is studied. We focus on exact methods to minimise the makespan. An original logic-based Benders decomposition scheme is proposed. Computational experiments show the very good performance of our method.