An efficient algorithm for the 2-level capacitated lot-sizing problem with identical capacities at both levels

We present a polynomial time algorithm for solving the 2-level production-in-series lot-sizing problem with capacities at both levels. At each level, we consider a fixed setup cost together with linear production and holding costs. We assume that capacities are stationary and identical at both levels. We introduce a new cost structure, called path non-speculative, generalizing the classical non-speculative cost structure. We show that under this cost structure the problem can be solved in time complexity O(T5), where T is the number of periods of the planning horizon. When the cost structure follows the classical non-speculative motives, the time complexity is reduced to O(T3).