Discrete-event Control of Stochastic Networks: Multimodularity and Regularity

This book is a counterpart of convex optimization in the setting of discrete optimization. The theory developed is applied to the control of stochastic discrete-event dynamic systems. Some applications are admission, routing, and service allocation.

**Tag(s):**
Operations Research

**Publication date**: 04 Aug 2003

**ISBN-10**:
3540203583

**ISBN-13**:
n/a

**Paperback**:
313 pages

**Views**: 17,857

Discrete-event Control of Stochastic Networks: Multimodularity and Regularity

This book is a counterpart of convex optimization in the setting of discrete optimization. The theory developed is applied to the control of stochastic discrete-event dynamic systems. Some applications are admission, routing, and service allocation.

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.

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.

Tweet

About The Author(s)

No information is available for this author.

No information is available for this author.

No information is available for this author.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Microsoft .NET
Rexx
Perl
PHP
Python
R
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors