A dynamic lot-sizing model with multi-mode replenishments: Polynomial algorithms for special cases with dual and multiple modes

Abstract

This paper generalizes the classical dynamic lot-sizing model to consider the case where replenishment orders may be delivered by multiple shipment modes. Each mode may have a different lead time and is characterized by a different cost function. The model represents those applications in which products can be purchased through various suppliers or delivered from a single source using various transportation modes with different lead times and costs. The problem is challenging due to the consideration of cargo capacity constraints, i.e., the multiple set-ups cost structure, associated with a replenishment mode. The paper presents several structural optimality properties of the problem and develops efficient algorithms, based on the dynamic programming approach, to find the optimal solution. The special, yet practical, cases of the two-mode replenishment problem analyzed in this paper are analytically tractable, and hence, the respective problems can be solved in polynomial time. © 2005 "IIE".