A Decomposition Algorithm for Arborescence Inventory Systems

Basil A. Kalymon
Additional contact information
Basil A. Kalymon: IBM Scientific Center, Los Angeles, California, and University of Toronto, Toronto, Ontario, Canada

Operations Research, 1972, vol. 20, issue 4, 860-874

Abstract: This paper develops an algorithm for solving an arborescence-structured production and inventory system. Arborescence structures model multi-echelon production systems in which each facility requires input from a unique immediate predecessor. Assuming known demands, and no backlogging, the objective is to schedule production over a finite planning horizon to minimize production and holding costs. The algorithm is applicable to systems in which, at all facilities with followers in the system, the production costs consist of a set-up charge plus linear costs and holding costs are linear. General costs are permitted at the lowest-echelon facilities (those without followers) with special computational efficiency resulting when these costs are concave. The algorithm exploits the known results on the structure of optimal policies in arborescence systems to decompose the problem into single-stage problems at each lowest-echelon facility. This decomposition is achieved by enumerating implicitly the feasible production set-up patterns at facilities with followers. As a result, the computational effort might increase exponentially with the number of facilities with followers, but is increasing only linearly with the number of lowest-echelon facilities in the system.

Date: 1972
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.20.4.860 (application/pdf)

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:inm:oropre:v:20:y:1972:i:4:p:860-874

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().