A linearization approach to the stochastic dynamic capacitated lotsizing problem with sequence-dependent changeovers

Inspired by the production and planning process of coreboard of our industry partner, a Fortune 1000 player in packaging, we present a mixed-integer linear programming model that can jointly optimize lot sizes, production sequences and safety stocks in the presence of sequence-dependent changeovers. First, we formulate a nonlinear (MINLP) model that can handle both the stochasticity and the sequence-dependency of the stochastic dynamic capacitated lotsizing problem, based on the stochastic sequence-independent (Tempelmeier et al. 2018) and deterministic sequence-dependent (Guimaraes et al. 2014) version of the problem. Then, we develop a piecewise linearization approach for the non-linear inventory on hand and backorder curves that builds on and challenges earlier research published by van Pelt and Fransoo 2018 and Tempelmeier et al. 2018. We use the derivatives of the inventory on hand and backorder functions to develop a tailored breakpoint selection strategy that reduces the maximum approximation error between the linearized and non-linear objective function from 20.3% to 0.5% in comparison to the equidistant linearization strategy recommend by the aforementioned articles. As a third and last contribution, we develop a Relax-and-Fix with Fix-andOptimize heuristic and show in an extensive numerical study that it improved the objective value by 20% on average and realized an average run time reduction of 60% over a state-of-the-art solver.

Jaar van publicatie:2019

Toegankelijkheid:Closed