# Tree systems

Russian: Древовидная структура

Consider a tree system[1]. The overall approach of the last section for series systems works here too. Actually, the approach works even for fully general systems, but only under a severe restriction involving leadtimes, as explained below. Also, the notation and analysis become more complex in the general case. Focus on tree systems.

Let formalize the network expressing the system's structure: It is a directed graph, specified by the pair of sets $\,(N,A)$. The nodes $\,N$ represent the items; $\,J=|N|$ is the number of items. The arcs $\,A$ describe the supply-demand or input-output relations. An arc from $\,i$ to $\,j$ denoted $\,(i,j)\in A$, means that some of item $\,i$ is used to produce or supply item $\,j$ (If there are several $\,i$ with $\,(i,j)\in A$, then all the inputs $\,i$ are required for item $\,j$).

This graph is connected but acyclic; no group of items is independent of the others, and no item is used, directly or indirectly, to produce itself. One can number the items so that $\,i whenever $\,(i,j)\in A$. If $\,(i,j)\in A$, we say $\,i$ is an (immediate) predecessor of $\,j$ and $\,j$ is a successor of $\,i$.

Define

$\,Pre(j)$ -- set of predecessors of $\,j$

$\,Suc(i)$ -- set of successors of $\,j$

These sets list each item's immediate inputs and outputs. A start item is one with no predecessor, and an end item is one with no successor. Only start items receive supplies from outside the system; in a production setting they represent the raw materials. Only end items have exogenous demands.

In these terms an assembly system has one end item $\,J$, and each $\,i has only one successor. An item may have several predecessors, however (unlike a series system). A distribution system, conversely, has one start item 1, and each $\,j>1$ has only one predecessor. An item may have several successors. The official definition of a tree system is a bit more intricate: Ignoring the directions of the arcs for the moment, the undirected network has no circuits; in other words, there is a unique (undirected) path connecting any two nodes. Provided this condition holds, an item may have several predecessors and successors. In all these cases the number of arcs is precisely $\,|A|=|N|-1=J-1$.

The cost factors $\,k_{j}$ and $\,h'_{j}$ have the same meaning as in a series system, as do the local inventories $\,I'_{j} (t)$. Also, let $\,\lambda '_{j}$ -- demand rate for item $\,j$.

Only an end item may have $\,\lambda '_{j} >0$.

## Contents

Each arc $\,(i,j)$ has an associated leadtime $\,L'_{ij}$. Also, each start item $\,j$ has order leadtime $\,L'_{j}$. These are non-negative constants. The corresponding zero-leadtime system has the same data, except all $\,L'_{ij}$ and $\,L'_{j}$ are 0.

Consider some item $\,j$ with several predecessors. The $\,L'_{ij}$ may include item-specific transportation times as well as assembly time, so in general the $\,L'_{ij}$ need not be equal over $\,i$. Now, for a batch of $\,j$ to be finished and available at time $\,t$, a corresponding batch of item $\,i$ must be released at time $\,t-L'_{ij}$ from every $\,i\in Pre(j)$. It makes no sense to speak of placing an order for item $\,j$ at a certain time if these $\,L'_{ij}$ are different. Rather, the key events are now the departure and arrival times of batches on specific arcs. The inventory $\,I'_{j} (t)$ depends on all arrivals to and departures from $\,j$.

## Echelons and Echelon Inventories

Echelon $\,i$ comprises item $\,i$ itself, its successors, their successors, and so on. That is, echelon $\,i$ includes $\,i$ and all subsequent items which use $\,i$ as input, directly or indirectly.

The echelon inventory of item $\,i$ is all the inventory in echelon $\,i$, and its echelon demand rate is the total demand over items in echelon $\,i$. These quantities can be computed recursively, starting with the end items:

$\,I_{i} (t)=I'_{i} (t)+\sum _{j\in Suc(i)}I_{j} (t)$

$\,\lambda _{i} =\lambda _{i} ^{{'} } +\sum _{j\in Suc(i)}\lambda _{j}$

The echelon holding cost is

$\,h_{j} =h_{j} ^{{'} } -\sum _{i\in Pre(j)}h_{i} ^{{'} }$

In an assembly system, for example, echelon $\,i$ comprises the items along the path from $\,i$ to $\,J$, each $\,\lambda _{i}$ is just $\,\lambda _{J} =\lambda$, and, if $\,j$ is the (unique) element of $\,Suc(i)$,

$\,I_{i} (t)=I'_{i} (t)+I_{j} (t)$

As in systems with linear structure, the total holding-cost rate at time $\,t$ is again

$\,\sum _{j}h'_{j} I'_{j} (t) =\sum _{j}h_{j} I_{j} (t) .$

## Policy Characteristics

Stationary-interval policies are not necessarily dominant, as in systems with linear structure. Still, they are convenient, and, as shown below, they do perform well.

A nested policy is one where an order for item i triggers an order for each of its successors, and hence throughout echelon $\,i$. In an assembly system, nested policies dominate others, as in a series system. Otherwise, nested policies need not be dominant. For example, consider the simple distribution system shown in Figure 1, where a warehouse (item 1) supplies two retailers (items 2 and 3). Suppose $\,\lambda _{2} =\lambda _{3}$ the $\,h_{j}$ are equal, $\,k_{1} =k_{2}$, but $\,k_{3}$ is much larger than $\,k_{1}$ and $\,k_{2}$. It makes sense to order items 1 and 2 relatively often, but item 3 less frequently. (Since item 1 sometimes orders when 3 does not, such a policy is not nested.) Under a nested policy the system either incurs the cost $\,k_{3}$ too often or carries too much inventory (at 1 or 2) to supply stage 2.

Nevertheless, some situations require a nested policy, not because it is less costly as measured by the model, but rather because it is easier to implement. If so, we say the system is nested. This distinction is unnecessary, of course, for an assembly system. For now, we focus on nested tree systems only.

Consider a policy with all three properties. Redefine

$\,g_{j} =h_{j} \lambda _{j}$

$\,U=(u_{1} ,...,u_{n} )$

Then, the average cost of policy $\,U=(u_{1} ,...,u_{n} )$ is

$\,C(U)=\sum _{j}\left[\frac{k_{j} }{u_{j} } +\frac{1}{2} g_{j} u_{j} \right]$

Fig. 1. Simple distribution system.

The problem of choosing the best such policy, becomes:

$\,\min C(U)=\min \sum _{j}\left[\frac{k_{j} }{u_{j} } +\frac{1}{2} g_{j} u_{j} \right]$

$\,u_{i} =\xi _{ij} u_{j}$

$\,\xi _{ij} >0$, $\,\xi _{ij}$-- integer,

$\, (i,j)\in A .$

## References

1. Zipkin P. (2000) Foundations of inventory management; The McGraw-Hill Companies, Inc.