Book Excerpts:

The aim of this monograph is not to offer a complete theory of discrete event control of stochastic networks, but to derive a theory and applications based on multimodularity and regularity. The main objective is to show that for a large class of stochastic discrete event systems and under rather natural assumptions on the behavior of the system as well as on the stochastic processes driving its evolution, the smoother the input process, the better the performances of the system.

This book is focused on a wide class of control (or of optimization) problems over sequences of integer numbers. The theory of convex functions plays a key role in the theory of optimization over convex spaces. An important objective is to construct a counterpart for our setting in which the optimization is not done any more over a convex set.

This book develops mainly the tools for control problems with no state information. This is done both in a deterministic setting as well as in a very general stochastic framework. Two classes of problems are handled. In the first one, the control sequence is one dimensional; it covers admission control, service assignment and vacation control problems. Although the control is one dimensional, the systems to which it is applied to may be quite general and complex. This book focuses on general discrete event models which can be described as linear in the max-plus algebra. This type of problem is fully solved, and an optimal policy is identified. The second type of problems is the one in which the control is multi-dimensional. It covers routing as well as polling problems.

Although the main concern in the book is to handling control problems with no information, this book also investigates the problem of closed-loop control in which the control has full or partial state information. It develops a general framework for handling multimodular cost functions, and establishes the optimality of optimal monotone policies: these are of threshold type for the one dimensional case, and of a switching-curve type for the two-dimensional case.

Book Overview:

This book is structured in four parts.

Part I: Theoretical foundations, presents the theoretical foundations which consists of three notions: multimodularity, balanced words, bracket sequences and stochastic Petri nets. The material in Part I is used throughout the monograph. The other chapters can be studied independently.

Part II: Admission and routing control, covers the application of the optimisation theorems for optimal admission and routing control in discrete event stochastic systems.

Part III: Several extensions, shows how the previous results can be useful in other cases.

Part IV: Comparisons, derives the theory of routing to three queues or more. Since the structure of the optimal policy is unknown in this case, the analysis is focused on getting lower and upper bounds for the performance measures, and on the comparison of the systems for different admisssion sequences.