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.

Keywords:

• Hybrid flowshop scheduling
• decision support system
• integer programming
• conflict graph
• co-bipartite chain graph
• interval graph
• maximal clique

Acknowledgements

The authors would like to thank Anita Graumans (DDCgroup B.V.), Taner Sezgin, Mahir Yüksel, Seda Lafcı (ICRON Technologies) for their valuable contributions in the implementation project. The authors also thank Tınaz Ekim (Boğaziçi University) for helpful discussions.

Disclosure statement

No potential conflict of interest was reported by the authors.