Capacity acquisition for the single-item lot sizing problem under energy constraints

We study a single-item lot sizing problem integrated with some energy constraints, called energy-LSP in the rest of the paper. We consider a production system composed of identical and capacitated machines in parallel. One has to decide how many machines to start and how much to produce to serve the demand and/or to replenish the inventory. In addition to the production capacity limit in each period, induced by the machines on, we have a limit on the energy that can be consumed by the start-ups of the machines and the production of units. We first provide a mixed integer programming formulation for the problem in the general case. We then develop efficient polynomial time algorithms running in O(Tlog T), with T the length of the planning horizon, for several subproblems: (i) energy-LSP where all energy parameters are set to 0, (ii) energy-LSP where only the machine start-ups consume energy, (iii) energy-LSP where only the production of units consumes energy. We show that, in all these special cases, energy-LSP can be seen as an extension of the integrated capacity acquisition and lot sizing problem. This allows us, as by-product of our approach, to significantly improve the existing result proposed for the capacity acquisition problem without energy constraint nor subcontracting.