Institute for Systems Research
Permanent URI for this communityhttp://hdl.handle.net/1903/4375
Browse
11 results
Search Results
Item On Stochastic Approximations Driven by Sample Averages: Convergence Results via the ODE Method(1994) Bartusek, John D.; Makowski, Armand M.; ISR; CSHCNWe consider a class of projected stochastic approximation algorithms drive by sample averages. These algorithms arise naturally in problems of on-line parametric optimization for discrete event dynamical systems., e.g., queueing systems and Petri net models. We develop a general framework for investigating the a.s. convergence of the iterate sequence, and show how such convergence results can be obtained by means of the ordinary differential equation (ODE) method under a condition of exponential convergence. We relate this condition of exponential convergence to certain Large Deviations upper bounds which are uniform in both the parameter q and the initial condition x. To demonstrate the applicability of the results, we specialize them to two specific classes of state processes, namely sequences of i.i.d. random variables and finite state time-homogeneous Markov chains. In both cases, we identify simple (and checkable) conditions that ensure the validity of a uniform Large Deviations upper bound.Item On an Elementary Characterization of the Increasing Covex Ordering, with an Application(1993) Makowski, Armand M.; ISRIn this short note, we present a simple characterization of the increasing convex ordering icx on the set of probability distributions on IR. We show its usefulness by providing a very short proof of a comparison result for M|GI|1 queues due to Delay and Rolski and obtained by completely different means.Item On The Convergence and ODE Limit of A Two-Dimensional Stochastic Approximation(1993) Ma, Dye-Jyun; Makowski, Armand M.; ISRWe consider a two-dimensional stochastic approximations scheme of the Robbins-Monro type which naturally arises in the study of steering policies for Markov decision processes [6,7]. Making use of a decoupling change of variable, we establish almost sure convergence by ad-hoc arguments that combine standard results on one-dimensional stochastic approximations with a version of the law of large number for martingale differences. Coming full circle, this direct analysis gives clues on how to select the test function which appears in standard convergence results for multi-dimensional schemes. Furthermore, a blind application of the ODE method is not possible here as solutions to the limiting ODE cannot be defined in an elementary way, but the aforementioned change of variasble paves the way for an interpretation of the behavior of solutions to the limiting ODE.Item Interpolation Approximations for Symmetric Fork-Join Queues(1992) Varma, S.; Makowski, Armand M.; ISRIn this paper we propose a family of heuristic approximations for the expected response time of K-dimensional symmetric Fork-Join systems in statistical equilibrium with general inter-arrival and service time distributions. To do this, we rely on the light traffic interpolation technique popularized by Reiman and Simon. The starting point for our approach is the formula for the heavy traffic limit for two dimensional Fork-Join queues that was obtained in [17,19]. By observing a fortuitous agreement between the light traffic derivative and the heavy traffic limit for this system under Markovian assumptions. we are able to obtain an approximation to the heavy traffic limit for -dimensional systems with general inter-arrival and service distributions. By combining this heavy traffic limit with light traffic limits, we are able to obtain interpolation approximations for the Fork-Join queue which agree extremely well with simulation results.Item On the Effects of the Initial Condition in State Estimation for Discrete-Time Linear Systems(1992) Sowers, R.B.; Makowski, Armand M.; ISRWe consider the one-step prediction problem for discrete-time linear systems in correlated Gaussian white plant and observation noises, and non-Gaussian initial conditions. Explicit representations are obtained for the MMSE and LLSE (or Kalman) estimates square of their difference. These formulae are obtained with the help of the Girsanov transformation for Gaussian white noise sequences, and explicitly display the effects of the distribution of the initial condition. With the help of these formulae, we investigate the large-time asymptotics of et , the expected squared difference between the MMSE and LLSE estimates at time t. We characterize the limit of the error sequence {et, t = 1,2,...} and obtain some related rates of convergence. A complete large-time analysis is provided for the scalar case.Item Distributed Parallelism Considered Harmful(1992) Makowski, Armand M.; Nelson, R.; ISRWe consider a model of a distributed parallel processing system that shows that parallel versus sequential processing is beneficial only under conditions of light load. Our results are valid under general assumptions on the number of processors, task service times and the information used to schedule jobs. Our model of a parallel processing system consists of a set of homogeneous processors each with private memory in which tasks queue before being served. Jobs arriving to the system consist of a random number of tasks which can be executed independently each other and we consider a job to be completed only after all of its component tasks have finished execution. a central dispatcher schedules the tasks on the processors at job arrival instants using information on the number of tasks currently scheduled on each processor. We model this system as a distributed fork/join queueing system and derive the structure of the individually optimal scheduling policy. Our results show that the individually optimal is a mixture of policies corresponding to sequential job execution (all tasks are scheduled on a single processor) and parallel scheduling (tasks are distributed among several processors in a manner that tends to equalize queue lengths). We show that, under conditions that include the case of moderate to heavy loads, the individually optimal scheduler schedules tasks according to the sequential policy which runs counter to the intuition that parallel processing is desirable. Because we do not include certain overheads associated with executing jobs in parallel in our model, our results are biased towards parallel rather than sequential processing. since we believe that systems are not typically underutilized, our results strongly suggest that it can be harmful to have parallel execution in distributed processing systems. Response time properties of the individually optimal scheduler are derived and compared to other scheduling policies.Item Optimal Scheduling for a Distributed Parallel Processing Model(1992) Makowski, Armand M.; Nelson, R.; ISRWe consider a model of a parallel processing system consisting of K distributed homogeneous processors each with private memory in which tasks queue before being served. Jobs arriving to the system consist of a set of tasks which can be executed independently of each other and we consider a job to be completed only after all of its component tasks have finished execution. A central dispatcher schedules the tasks on the processors at job arrival instants using information on the number of tasks currently scheduled on each processor. We model this system as a distributed fork/join queueing system and derive the structure of the individually optimal scheduling policy. Our results show that the individually optimal policy is a mixture of policies corresponding to sequential job execution (all tasks are scheduled on a single processor) and parallel scheduling (tasks are distributed among several processors in a manner that tends to equalize queue lengths). We show that, under conditions that include the case of moderate to heavy loads, the individually optimal scheduler schedules tasks according to the sequential policy which runs counter to the intuition that parallel processing is desirable. Because we do not include certain overheads associated with executing jobs in parallel in our model, our results are biased towards parallel rather than sequential processing. Thus our results strongly suggest that for actual distributed memory systems the benefits of parallel processing can be achieved only in conditions of light load. Response time properties of the individually optimal scheduler are derived and compared by simulation to other scheduling policies.Item Stochastic Orders Associated with the Forward Recurrence Time of a Renewal Process(1992) Baccelli, Francois; Makowski, Armand M.; ISRWAITING FOR JAYA TO CREATE SYMBOLS FOR THE ABSTRACT OF THIS REPORT.Item On Constrained Optimization of the Klimov Network and Related Markov Decision Processes(1991) Makowski, Armand M.; Shwartz, A.; ISRWe solve a constrained version of the server allocation problem for a Klimov network and establish that the optimal constrained schedule is obtained by randomizing between two fixed priority schemes. This generalizes work of Nain and Ross in the context of the competing queue problem, and also covers the discounted cost case.In order to establish these results we develop a general framework for optimization under a single constraint in the presence of index-like policies. This methodology is in principle of wider applicability.
Item Convexity Results for Parallel Queues with Bernoulli Routing(1990) Gun, Levent; Jean-Marie, Alain; Makowski, Armand M.; Tedijanto, T.; ISRIn this note, we derive various convexity and monotonicity properties of performance measures in parallel GI/GI/1 queues with Bernoulli routing. We then use these results to establish that the equilikely assignment is optimal among all Bernoulli routing. The main tools are notions of stochastic convexity recently introduced by Shaked and Shanthikumar. The optimality results are couched in terms of the stochastic orderings st and icx.