Abstract
The material presented in this book originated from research on discrete-event systems when the outputs are monotone functions of the inputs. A discrete-event system is defined as a collection of elementary processes evolving asynchronously and interacting at irregular instants called event epochs. Similar results have often been established for different systems by using inductive sample-path arguments. The authors have identified the underlying structure and formulated general conditions for monotonicity. The material is organized in nine chapters.
The first chapter discusses discrete-event systems and introduces generalized semi-Markov processes (GSMP). The authors explain these processes with a production-line example using the kanban method. This chapter also introduces the concept of a hierarchy of structural and monotonic conditions on the dynamics of a discrete-event system. The second chapter provides a detailed exposition and examples of generalized semi-Markov processes and schemes. It also introduces some terminology for formal languages. Chapter 3 introduces monotonicity conditions (M) and their consequences. The authors give various formulations of this condition, establish its equivalence to the antimatroid property, and develop the connection between this condition and monotonicity.
Chapter 4 extends the conditions developed in the previous chapter. The objective of this chapter is to explain the condition (CX), under which the event epochs admit (max, +) recursions, and to show that this condition is increasing and convex. The next chapter illustrates implications of the results of earlier chapters through connections with other models. This chapter analyzes production lines under a general control mechanism that includes the kanban system as a special case.
Chapter 6 deals with the optimal control of Markovian GSMPs when costs are assigned to states and the rates of events are subject to control. The authors show that the structure developed in chapters 3 and 4 implies the existence of monotone optimal controls. The next chapter is devoted to the long-run behavior of GSMPs satisfying (CX). The (max, +) recursions implied by this condition permit an analysis of the average time between occurrences through subadditive ergodic theory. This topic is pursued by formulating the evolution of event epochs in maxplus algebra along with the results on the random max-plus matrix.
Chapter 8 discusses the problem of optimal coupling of random objects. The authors show that, in comparing GSMPs that satisfy (M), using the same stream of random numbers to simulate the system reduces variance compared to independent simulation. The last chapter provides the perturbation analysis of GSMPs satisfying the structural conditions. This is a technique for computing derivatives of event epochs and performance criteria, with respect to parameters of event lifetimes.
This interesting book gives readers an opportunity to evaluate various discrete-event systems and their possible applications in solving problems of production lines, linear programming, and so on.