An extension of the Economic Order Quantity (EOQ) model to multi-stage production-distribution systems and the isotonic regression problem are known to be equivalent and to be solvable in O(N4) time. The following specializations of the model are solvable in O(NlogN) time: joint replenishment systems, pure assembly systems, nested policies in pure distribution systems, nonnested policies in one-warehouse multi-retailer systems, nested policies in multi-item, one-warehouse, multi-retailer systems, and systems in which the underlying network is a series-parallel digraph. The authors show here that a generalization of this problem is solvable in O(NlogN) time whenever the undirected version of the underlying network is a tree. The algorithm they propose is used as a subroutine in an algorithm solving the EOQ problem on general circuitless directed graphs, the subject of a compansion paper.
