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

Awi Federgruen and Michal Tzur

Naval Research Logistics (NRL), 1999, vol. 46, issue 5, 463-486

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. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 463–486, 1999

Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1002/(SICI)1520-6750(199908)46:53.0.CO;2-S

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:46:y:1999:i:5:p:463-486

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().