Time-partitioning heuristics: Application to one warehouse, multiitem, multiretailer lot-sizing problems

We describe effective time partitioning heuristics for dynamic lot-sizing p roblems 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, t o optimality, on each of these intervals, acid the resulting solution coale sced into a solution for the complete horizon. The intervals are selected t o be of a size which permits the use of exact and effective solution method s (e.g., branch-and-bound methods). Each interval's problem is specified to include options for starting conditions which adequately complement the so lutions obtained for prior intervals. The heuristics can usually be designe d to be of low polynomial complexity as well as to guarantee epsilon-optima lity for any desired precision epsilon > 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 d evelop such a heuristic in detail, for the one warehouse multiretailer mode l representing a two-echelon distribution network with m retailers, selling J distinct items. A comprehensive numerical study exhibits that the partit ioning heuristics are very efficient and close-re-optimal. Even problems wi th a planning horizon of up to 150 periods can be solved within 1.5% of opt imality, employing intervals of 5-10 periods only and in a matter of CPU se conds, or up to a few minutes, using longer intervals and when the number o f items and retailers is large. These CPU times refer to a SUN 4M (SPARC) w orkstation. (C) 1999 John Wiley & Sons, Inc.