Discrete Event Systems, Manufacturing Systems, and Communication Networks

The COCOLOG (Conditional Observer and Controller Logic) system is a partially ordered family of first order logical theories expressed in the typed first order languages {L _k ;k ≥ 0z describing the controlled evolution of the state of a given partially observed finite machine M The initial theory of the system, denoted Th ₀, gives the theory of M. without data being given on the initial state. Later theories, \(\{ Th(o_1^k);k \ge 1\}\) , depend upon the (partially ordered lists of) observed input-output trajectories, where new data is accepted in the form of the new axioms AXM ^obs (L _k ),k ≥ 1. A feedback control input U(k) is determined via the solution of control problems posed in the form of a set of conditional control rules, denoted CCR(L_k), which is paired with the theory \(Th(o_1^k)\). The disadvantage of this formulation is that the accumulation of observation axioms may handicap the speed of reasoning. In this paper, by use of a restricted subset, \(L_k^m\), of each language L _k , k ≥ 1, we introduce a restricted version of COCOLOG; this is called a system of Markovian fragments of COCOLOG and it is designed so that a smaller amount of information than in the full COCOLOG system is communicated from one theory to the next. Systems of Markovian fragments are associated with a restricted set of candidate control problems, denoted \( CCR(L_k^m)\) k ≥ 1. It is shown that, under certain conditions, a Markovian fragment theory \(MTh(o_1^k)\) contains a large subset of \(Th(o_1^k)\) which includes, in particular, the state estimation theorems of the corresponding full COCOLOG system, and, for the set of control rules \(CCR(L_k^m)\), possesses what may be informally termed the same control reasoning power. In formal terms, this means that \(MTh(o_1^k)\) with respect to the well formed formulas in \(L_k^m\). Hence a theoretical basis is supplied for the increased theorem proving efficiency of the fragment systems versus the full COCOLOG systems. Finally some computer generated examples are given illustrating these results.

Infinitesimal perturbation analysis (IPA) is a method for estimating the gradient of a performance measure in a discrete event system by observing a single sample path of the system. The method lends itself naturally to recursive optimization using gradient-based algorithms. Such algorithms can be used in on-line optimization applications, or in single-run optimization of simulation models. We describe the use of such algorithms for optimization of single server queues. We give sufficient conditions that guarantee convergence of the algorithm to the optimizing point. The convergence proof is simple, and provides insight into how the algorithm behaves under different update times.

This paper advocates some mind-set changes concerning the problem of optimization of the performance of general discrete event dynamic systems under uncertainty via simulation. We present arguments and evidence that orders of magnitude improvement in computational efficiency are possible and summarize a set of works by the Harvard DEDS group in this area over the past decade.

Dynamic set-up scheduling is an important issue when a Flexible Manufacturing System (FMS) recovers from a failure or other disruption induced excursion from its economic-lot size steady state cycle. In fact, FMSs usually spend more time recovering from disruptions than being in steady state. We present recent results on the structure of optimal and near optimal policies for dynamic set-up scheduling that minimize backlog costs for a given vector of demands for each of many part types. When different part-types are nonhomogeneous or differ significantly in importance or value, non-Round Robin (general Round Robin) set-up change policies may be needed. Theoretical considerations and numerical solution results are used to deduce structural properties of the optimal policies (not necessarily Round Robin) and design near optimal policies that are tractable for high dimensional systems. The near optimal policies are based on primary and secondary set-up change hyper plane surfaces (thresholds). Primary switching surfaces (PSSs) are of dimension n — 1 (for n part-type systems) and when encountered indicate that the current set-up must be changed. Secondary switching surfaces (SSSs) are of lower dimension and indicate what set-up to change to. Stability issues as well as issues on convergence to a limit cycle are raised and analyzed, and sufficient conditions are obtained. A procedure for designing primary and secondary hyper plane set-up switching surfaces is proposed and implemented.

Automata-theoretic verification is based upon the language containment test where the Pi’s are automata which together model a system with its fairness constraints, ⊗ is a parallel composition for automata and T defines a specification. The complexity of that test typically grows exponentially with k. This growth, often called “state explosion”, has been a major impediment to computer-aided verification, and many heuristics which are successful in special cases, have been developed to combat it. We describe here a general reduction methodology which subsumes many of these heuristics. It is based upon two transformations: decomposition of T into “local” properties T₁ ,…, T_n such that ) ∩L(Tj) ⊂ L(Tj), and localization of each test L(⊗P_i) ⊂ L(Tj) to a small (tractible) test.

Recently, real-time system models have been proposed which fall into the general category of timed automata. A timed automaton consists of a discrete event component represented as a finite automaton, coupled with a temporal component represented as a finite collection of clocks marking time between event occurrences. For timed automata it is possible to reduce certain verification problems to those of checking language containment or language emptiness. We extend this model to allow the clocks to rim at rates other than one. The extension is well suited to the analysis of scheduling problems, find we demonstrate this by the modeling a simple scheduling policy. We give conditions for reduction of the rate automaton to a finite state automaton.

The event-scheduling view of the discrete-event simulation technique is widely used to model and simulate dynamic systems. This paper presents DMOD, a formalization of this technique. DMOD offers two major advantages. First, it retains the powerful intutions behind this technique, yet makes it easier to specify them. Second, it permits reasoning about its models. This is done by means of symbolic simulation, i.e. simulation in which input parameters can be constrained variables. DMOD can be used to model hybrid systems including those with non-linearities. It has been implemented in Prolog and applied to analysis of a variety of industrial systems.

A summary is given of computational complexity results for decentralized discrete-event control problems. These results generalize the earlier work of Tsitsiklis, who showed that for a special class of centralized supervisory control problems under partial observation, there is an algorithm for determining in polynomial-time whether or not a solution exists. The negative complexity results associated with Tsitsiklis’ work also carry over to the decentralized case, so that solution existence for the more general class is not decidable in polynomial time. Moreover, even when it can be shown that supervisor solutions exist for problems in either the special or general class, there is no polynomial-time algorithm for producing such solutions.

We review the stability condition of a class of guided distributed scheduling policies in queuing systems and show that the same stability condition also holds for fluid systems. This condition is interpreted as requiring a contraction of machine starvation delays in the cycles of material flow in the system. Machine starvation is the cause of instability and arises naturally in queuing systems due to the discrete nature of operations (it can also be caused by the scheduling policy). In fluid systems, however, machine starvation can only be caused by the scheduling policy. Although the cause of machine starvation can be different in queuing and fluid systems, our results show that this is inconsequential to the condition for stability.

Noting that instability is caused by machine starvation which leads to slow down (or stoppage) of machines, we show that the condition for stability of a system studied by Kumar and Seidman can be expressed as an ordinary capacity condition for the corresponding slowed down system.