Institute for Systems Research Technical Reports
Permanent URI for this collectionhttp://hdl.handle.net/1903/4376
This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.
Browse
23 results
Search Results
Item Analysis and Adaptive Control of a Discrete-Time Single-Senrer Network with Random Routing.(1989) Makowski, Armand M.; Shwartz, A.; ISRThis paper considers a discrete time system composed of K infinite capacity queues that compete for the use of a single server. Customers arrive in i.i.d batches and are served according to a server allocation policy. Upon completing service, customers either leave the system or are routed instantaneously to another queue according to some random mechanism. As an alternative to simply randomized strategies, a policy based on a Stochastic Approximation algorithm is proposed to drive a long- run average cost to a given value. The motivation can be traced to implementation imues associated with constrained optimal strategies. A version of the ODE method as given by Metivier and Priouret is developed for proving a.s. convergence of this algorithm. This is done by exploiting the recurrence structure of the system under non-idling policies. A probabilistic representation the solutions to an associated Poisson equation is found most useful for proving their requisite Lipschitz continuity. The conditions that guarantee convergence are given directly in terms of the model data. The approach is of independent interest, as it is not limited to this particular queueing application and suggests a way of attacking other similar problems.Item Stochastic Approximations for Finite-State Markov Chains.(1989) Ma, Dye-Jyun; Makowski, Armand M.; Shwartz, A.; ISRThis paper develops an a.s. convergence theory for a class of projected Stochastic Approximations driven by finite-state Markov chains. The conditions are mild and are given explicitly in terms of the model data, mainly the Lipschitz continuity of the one- step transition probabilities. The approach used here is a version of the ODE method as proposed by Metivier and Priouret. It combines the Kushner-Clark Lemma with properties of the Poisson equation associated with the underlying family of Markov chains. The class of algorithms studied here was motivated by implementation issues for constrained Markov decision problems, where the policies of interest often depend on quantities not readily available due either to insufflcient knowledge of the model parameters or to computational difficulties. This naturally leads to the on-line estimation (or computation) problem investigated here. Several examples from the area of queueing systems are discussed.Item Analysis and Adaptive Control of a Discrete-Time Single-Server Network with Random-Routing.(1989) Makowski, Armand M.; Shwartz, A.; ISRThis paper considers a discrete-time system composed of K infinite capacity queues that compete for the use of a single server. Customers arrive in i.i.d batches and are served according to a server allocation policy. Upon completing service, customers either leave the system or are routed instantaneously to another queue according to some random mechanism. As an alternative to simply randomized strategies, a policy based on a Stochastic Approximation algorithm is proposed to drive a long- run average cost to a given value. The motivation can be traced to implementation issues associated with constrained optimal strategies. A version of the ODE method as given by Metivier and Priouret is developed for proving a.s. convergence of this algorithm. This is done by exploiting the recurrence structure of the system under non-idling policies. A probabilistic representation the solutions to an associated Poisson equation is found most useful for proving their requisite Lipschitz continuity. The conditions which guarantee convergence are given directly in terms of the model data. The approach is of independent interest, as it is not limited to this particular queueing application and suggests a way of attacking other similar problems.Item Discrete-Time Filtering for Linear Systems in Correlated Noise with Non-Gaussian Initial Conditions.(1989) Sowers, R.B.; Makowski, Armand M.; ISRWe consider the one-step prediction problem for discrete-time linear systems in correlated plant and observation noises, and non-gaussian initial conditions. Explicit representations are obtained for the MMSE and LMSE ( or Kalman) estimates of the state given past observations. These formulae are obtained with the help of the Girsanov transformation for Gaussian white noise sequences, and display explicitly the dependence of the quantities of interest on the initial distribution. Applications of these results can be found in [5] and [6].Item Discrete-Time Filtering for Linear Syskms in Correlated Noise with Non-Gaussian Initial Conditions: Asymptotic Behavior of the Difference between the MMSE and LMSE Estimates.(1989) Sowers, R.B.; Makowski, Armand M.; ISRWe consider the one-step prediction problem for discrete-time linear systems in correlated plant and observation noises, and non-gaussian initial conditions. We investigate the asymptotic behavior of the expected square {GREEK LETTER SUB t} of the difference between the MMSE and LMSE (or Kalman) estimates of the state given past observations. We characterize the limit of the error sequence ( {GREEK LETTER SUB t}, t = 0,1, ...} and obtain some related rates of convergence, with complete analysis being provided for the scalar case. The discussion is based on the explicit representations which were obtained by the authors in [,] for the MMSE and LMSE estimates, and which explicitly display the dependence of these quantities on the initial distribution.Item Simple Proofs of Some Folk Theorems for Parallel Queues.(1989) Makowski, Armand M.; Philips, T.K.; ISRWe present simple proofs of some folk theorems for systems of identical single server queues operating in parallel. In particular we establish a monotonicity property in the number of servers, and show that round-robin customer assignment outperforms random customer assignment. The results are couched in terms of stochastic orderings and hold in great generality.Item Discrete-Time Filtering for Linear Systems in Correlated Noise with Non-Gaussian Initial Conditions.(1988) Sowers, R.B.; Makowski, Armand M.; ISRWe consider the one-step prediction problem for discrete-time linear systems in correlated plants and observation noises, and non-Gaussian initial conditions. Explicit representations are obtained for the MMSE and LMMSE (or Kalman) estimates of the state given past observations, as well as for the expected square of their difference. These formulae are obtained with the help of the Girsanov transformation for Gaussian white noise sequences, and display explicitly the dependency of the quantities of interest on the initial distribution. Applications of these results can be found in [5] and [6].Item Dynamic, Transient and Stationary Behavior of the M/GI/1 Queue.(1988) Baccelli, Francois; Makowski, Armand M.; ISRAn exponential martingale is associated with the Markov chain of the number of customers in the M/GI/1 queue. This together with renewal theory are shown to provide a unified probabilistic framework for deriving several well-known generating functions for the M/GI/1 queue, including the Pollaczek-Khinchine formula, the transient generating function of the number of customers at departure epochs and the generating function of the number of customers served in a busy period.Item Steering Policies for Markov Decision Processes Under a Recurrence Condition.(1988) Ma, Dye-Jyun; Makowski, Armand M.; ISRThis paper presents a class of adaptive policies in the context of Markov decision processes (MDP's) with long-run average performance measures. Under a recurrence condition, the proposed policy alternates between two stationary policies so as to adaptively track a sample average cost to a desired value. Direct sample path arguments are presented for investigating the convergence of sample average costs and the performance of the adaptive policy is discussed. The obtained results are particularly useful in discussing constrained MDP's with a single constraint. Applications include a wide class of constrained MDP's with finite state space (Beutler and Ross 1985), an optimal flow control problem (Ma and Makowski 1987) and an optimal resource allocation problem (Nain and Ross 1986).Item Matrix-Geometric Solution for Two Node Tandem Queueing Systems with Phase-Type Servers Subject to Blocking and Failures.(1987) Gun, Levent; Makowski, Armand M.; ISRA two node tandem queueing system with phase-type servers and Bernoulli arrivals is considered in discrete-time when servers are subject to bloclring and failuree. The invariant probability vector of the underlying finite state Quasi-Birth-and-Death process is shown to admit a matrix-geometric representation for all values of the arrival rate A. The corresponding rate matrix is given explicitly in terms of the model parameters and the resulting closed-form expression provides the basis for an efficient calculation of the invariant probability vector. The cases LAMBDA = 1 and LAMBDA < 1 are studied separately and the irreducibility of the underlying Markov chain is discussed for each case. The continuous-time formulation is briefly discussed and only major differences with the discrete-time results are pointed out. Some numerical examples are also provided.
- «
- 1 (current)
- 2
- 3
- »