Operations Management and Econometrics

Finite Buffer Fluid Networks with Overflows

Dr Yoni Nazarathy, Swinburne University of Technology

29th Jul 2011  11:00 am - Room 498, Merewether Building

Consider an abstraction of a material processing network with N nodes. Each node is equipped with a finite buffer of capacity K_i and with a processor capable of working at rate mu_i. Material is modeled as a continuous (ideal fluid) flow and arrives to the nodes exogenously according to rates alpha_i. When material arrives to node i and finds less than K_i in the buffer then it either enters the buffer or is immediately processed if the buffer is empty. Material which is processed at node i can either leave the system or move to other nodes. This follows the proportions p_{i,j} (the proportion of material leaving i which goes to j) with have sum_j p_{i,j} <= 1; in case the inequality is strict, the remaining material leaves the system. When material arrives to find a full buffer it is diverted (overflows) according to propositions q_{i,j} similarly to the p_{i,j}.
 
The case of random discrete memoryless (Poisson/Exponential) flows and K_i = infinity is the well-known Jackson network and can be represented as a Markov chain having a product form solution in the stable case. As opposed to that, finite K_i  typically implies intractability of the Markov Chain. In this case it is first fruitful to analyze the behaviour of the system with deterministic continuous flows. In this respect we formulate traffic equations and show that they can be represented as a linear complementarity problem. We further find a polynomial time algorithm for the solution of the equations (note that the general LCP is in general an NP-complete problem). Finally, the solution of the traffic equations can be used to approximate the sojourn time distribution of customers through the network which can be represented as a discrete phase-type distribution.
Joint work with Erjen Lefeber from Eindhoven University of Technology.

103621