Exact methods for the single-item multi-plant capacitated lot sizing problem coupled with transportation

In this paper we study the integration of production, transportation and storage decisions in a multi plant-distribution center supply structure. Multiple plants produce one type of item, each of them with different production capacity and costs, and send finished goods to the distribution center (DC) using capacitated vehicles. Customer demand is known at DC level and has to be satisfied without backlogging. This problem contains classical capacitated lot sizing problem as a subpart, which, in the general case, is NP-hard. We propose an exact pseudo-polynominal dynamic programming algorithm and show that the problem is NP-hard in the ordinary sense. We then compare the computational time of this dynamic program to that of a mixed integer linear program (MILP) which is selected among 4 different MILP formulations based on its lower computational time.