Abstract
We describe effective time partitioning heuristics for dynamic lot-sizing problems in multiitem and multilocation production/distribution systems. In a time-partitioning heuristic, the complete horizon of (say) N periods, is partitioned into smaller intervals. An instance of the problem is solved, to optimality, on each of these intervals, and the resulting solution coalesced into a solution for the complete horizon. The intervals are selected to be of a size which permits the use of exact and effective solution methods (e.g., branch-and-bound methods). Each interval's problem is specified to include options for starting conditions which adequately complement the solutions obtained for prior intervals. The heuristics can usually be designed to be of low polynomial complexity as well as to guarantee ϵ-optimality for any desired precision ϵ > 0, and asymptotic optimality as N goes to infinity. We first give a general description of the design of time-partitioning heuristics for dynamic lot-sizing problems. We subsequently develop such a heuristic in detail, for the one warehouse multiretailer model representing a two-echelon distribution network with m retailers, selling J distinct items. A comprehensive numerical study exhibits that the partitioning heuristics are very efficient and close-to-optimal. Even problems with a planning horizon of up to 150 periods can be solved within 1.5% of optimality, employing intervals of 5-10 periods only and in a matter of CPU seconds, or up to a few minutes, using longer intervals and when the number of items and retailers is large. These CPU times refer to a SUN 4M (SPARC) workstation.