A hybrid general lot-sizing and scheduling formulation for a production process with a two-stage product structure

Abstract

Tailored for a complex application in the process industry, this article examines a multi-product production planning and scheduling problem with sequence-dependent setup cost and times. The manufacturing process is characterised by a two-stage structure where the sequencing problem occurs on the first level and contribution margin, holding cost, penalty cost are accounted on the second level. We present a hybrid mixed-binary optimisation model based on the general lot-sizing and scheduling problem [Fleischmann, B. and Meyr, H. 1997. The general lotsizing and scheduling problem. OR Spectrum, 19 (1), 11–21], which combines discrete and continuous-time elements within a standard inventory and lot-size (I&L) formulation. Since the I&L formulation does not provide sharp linear programming-relaxation bounds, we present two alternative reformulations based on a transportation problem. In a numerical study inspired by real industry data, we show that on average, both reformulations yield significant improvements in computation time and integrality gap.

Keywords:

• lot-sizing
• scheduling
• mixed-integer programming
• reformulations
• process industry

Acknowledgements

We gratefully acknowledge the helpful comments of two anonymous referees.