Real time job flow control in non-concurrent queueing networks

Abstract

This research focuses upon the development of a real time, state variable feedback optimal control for the class of non-concurrent queueing networks. The objective of this control is to achieve higher network throughput while keeping the job sojourn times to within an acceptable range, with a pre-specified probability. An optimal control is formulated that maximizes throughput along any sample path subject to a probabilistic constraint on sojourn time. In this dissertation, non-concurrent queueing networks are modeled as Stochastic Timed Event Graphs or Decision Free Petri Nets which in the (max, +) algebra, are characterized by a set of linear stochastic equations. These difference equations capture network dynamic behavior and serve as the mathematical model underlying our control. It is shown that optimal control is equivalent to releasing new jobs into the network subject to a probabilistic constraint on job sojourn time; hence, control is exercised by assessing, in real time, the feasibility of the probabilistic constraint. The image of the event (through the stochastic dynamic equations) that the sojourn time is within an acceptable range, forms a convex polytope in Cartesian space of service times. The probability of this event is computed by integrating with respect to product measure induced by the joint service time distribution. A new approach (based upon a straightforward mathematical programming formulation and Monte Carlo simulation) for evaluating this sophisticated integral is developed.