A Decomposition Algorithm for Arborescence Inventory Systems

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.