A Strong Integer Programming Formulation for Hybrid Flowshop Scheduling

Abstract

We consider a hybrid flowshop scheduling problem that includes parallel unrelated discrete machines or batch processing machines in different stages of a production system. The problem is motivated by a bottleneck process within the production system of a transformer producer located in the Netherlands. We develop an integer programming model that minimises the total tardiness of jobs over a finite planning horizon. Our model is applicable to a wide range of production systems organised as hybrid flowshops. We strengthen our integer program by exploiting the special properties of some constraints in our formulation. We develop a decision support system (DSS) based on our proposed optimisation model. We compare the results of our initial optimisation model with an improved formulation as well as with a heuristic that was in use at the company before the implementation of our DSS. Our results show that the improved optimisation model significantly outperforms the heuristic and the initial optimisation model in terms of both the solution time and the strength of its linear programming relaxation.