Benders Decomposition to Integrate MILP and Discrete-Event Simulation for Flow Shop Scheduling

Optimization-based decision-making in the chemical industry is highly beneficial but also very difficult, because many decision variables must be considered, and their interrelation is complicated. Different modeling techniques exist each with individual strengths. We propose Benders decomposition to integrate mixed-integer linear programming (MILP) and discrete-event simulation (DES) to solve flow shop scheduling problems. The basic idea is to generate valid Benders cuts based on sensitivity information of DES models which can be found in the critical path of a DES solution. We apply our Benders-DES approach to a scaled literature flow shop with secondary resource constraints and find that near optimal solutions can be found quickly. From the optimality gap information during the solution process we can conclude that Benders-DES is a promising approach to combine rigorous optimization capabilities with high-fidelity modeling capabilities.