A decomposition-based matheuristic for flexible job shops with processing alternatives

The flexible job shop scheduling problem with processing alternatives (FJSP-PA) extends the flexible job shop scheduling problem by allowing jobs to be completed in multiple technologically feasible ways. We model these alternatives using directed acyclic processing graphs that combine operation vertices, precedence relations, and XOR-decisions. Unlike existing approaches, we consider processing graphs that are not restricted to disjoint subgraphs and define processing alternatives through edge-based XOR-decisions, such that they contain only the operations and precedence relations implied by the selected edges. We present a compact mixed-integer linear programming formulation for the FJSP-PA and derive a Dantzig--Wolfe decomposition in which processing alternatives are represented as columns. Based on this decomposition, we develop a matheuristic combining the generation of processing alternatives with a fix-and-optimize neighborhood search. We evaluate the approach on benchmark instances from the literature and a newly generated benchmark set covering different levels of processing and machine flexibility. Finally, we investigate different strategies for generating processing alternatives and compare the matheuristic with the compact formulation to assess their performance on the FJSP-PA.