Exact methods for single-item capacitated lot sizing problem with alternative machines and piece-wise linear production costs

In this paper, we study a special case of the capacitated lot sizing problem (CLSP), where alternative machines are used for the production of a single-item. The production cost on each machine is assumed to be piece-wise linear with discontinuous steps (step-wise costs). The over-produced finished products can be stored in an unlimited storage space to satisfy future demand. The aim is to achieve optimal production planning without backlogging. This problem can be seen as an integration of production and transportation activities in a multi-plant supply chain structure, where finished goods are sent directly from the plants to the distribution center using capacitated vehicles. For this problem, which we show to be NP-hard, we propose an exact pseudo-polynomial dynamic programming algorithm which makes it NP-hard in the ordinary sense. We also give three mixed integer linear programming (MILP) formulations that we have found in the literature for the simplest case of the CLSP. These formulations are adapted to the multi-machine case with a step-wise cost structure, to which some valid inequalities have been added to improve their efficiency. We then compare the computational time of the dynamic program to that of one MILP which we selected among MILP formulations based on its lower computational time and its lower and upper bound quality.