CDC2000 Recent Advances in Stochastic Networks

Recent Advances in Stochastic Networks
Home Full List of Titles 1: Proceedings of CDC2000 Discrete Event Systems Control in Communication Systems Optimal Control and Applications I Optimisation Approaches and Methods Model Predictive Control Advances in Linear Estimation Stochastic and Uncertain Systems Nonlinear Control and Applications Nonlinear Estimation and Filtering Formation Control and its Applications New Approaches to Fuzzy Control Manufacturing Systems Automotive Applications Stability Issues in Hybrid Control Recent Advances in Stochastic Networks Optimal Control and Applications II Robust Controller Design - mu, L1 and H2 Constrained and Receding Horizon Control Identification and Control around the World Markov Decision Processes Nonlinear Optimisation Observers for Nonlinear Systems Motion Planning Neural / Fuzzy Stability and Control Motor Control Control of Quantum Phenomena I Hybrid Systems Methods Control in Communication Networks Robustness and Optimisation Bumpless Transfer, Antiwindup and Saturation Adaptive Control: Linear Systems Estimation and Closed Loop Identification Control of Markov Processes Nonlinear Filtering and Control Modelling, Identification and Validation of Nonlinear Systems Differential Geometric Control Theory for Mechanical Systems Nonlinear Output Feedback Control Pneumatics and Compression Systems Control of Quantum Phenomena II Stability of Hybrid Systems Performance Analysis in Communication Networks Adaptive Control of Nonlinear Systems LMI Methods in Design Robust Control of Time Delay Systems Subspace Identification Methods Nonlinear Stochastic Filtering and Estimation Bifurcations, Chaos and Control I New Progress in Synthesis of Nonlinear Systems I Implementation Issues of Sliding Mode Control Theory Control of Mixing in Shear Flows Novel Neural Network Control Techniques for Industrial Motion Control Systems Physiological Control Systems Optimal Control of Hybrid Systems Stochastic Models for Communication Networks Control and Stabilisation of Nonlinear Systems New Directions in Robust Control Linear Systems Theory Advanced Topics in Systems Theory Estimation in Action Bifurcations, Chaos and Control II New Progress in Synthesis of Nonlinear Systems II Numerical Design and Analysis Techniques for Nonlinear Systems Analysis and Control of Underactuated Systems Sliding Mode Control I Challenges in the Application of Control to Computer Systems Estimation and Diagnosis of Discrete Event Systems Communications and Games Optimal Control Stochastic Systems Model Reduction Methodologies Identification and Subspace Methods Applications of Nonlinear Adaptive Control Advances in Nonlinear Output Feedback Design The Behavioural Approach to Systems and Control Vision Based Estimation and Control: Recent Advances and Open Problems Agile Control of Military Operations Sliding Mode Control II Model-based Fault Diagnosis of Industrial Processes Discrete Event Systems / Petri Nets System Identification and Confidence Estimation New Approaches to H-Infinity Control I Probabilistic Approaches to Robust Control Time Delay System Stabilisation Identification Methods Controlled Stochastic Processes Output Feedback of Nonlinear Systems Topics in Nonlinear Stabilisation Mobile Robots: Tracking Control Robust Control of Nonlinear Systems Power Systems Stabilisation and Control Disk Drive Control Hybrid Control Applications Discrete Time Systems New Approaches to H-Infinity Control II Linear Systems with Saturating Actuators New Theories in Distributed Parameter Systems Applications of Estimation and Identification Stochastic Control and Tuning Methodologies Control of Nonlinear Systems Iterative Learning and Control Coordinating Robot Systems Nonlinear Time Varying Systems Novel Applications of Neural Networks Aerospace Applications Switched Systems Implicit and Descriptor Systems LQG Periodic Systems and Disturbances New Horizons for Distributed Parameter Systems State Estimation Learning and Neuro-Control Nonlinear Control and Stabilisation I Tracking Vision Servoing Controllability of Nonlinear Systems Control of Flexible Systems Electro-Mechanical Systems Robust Control Methods and Applications Fault Detection and Diagnosis Optimisation and Applications Robust Stability Analysis Numerical Methods in Control Filtering in Continuous Time Stochastic Systems Interplay between Control and Signal Processing Fault Detection and Analysis Nonlinear Dynamical Systems Nonlinear Time Delay Systems Computational Issues in Nonlinear Control Disturbance Rejection Process Control Industry Applications Linear Parameter Varying Systems Linear Control Systems Dynamic and Nonlinear Programming Model Reduction Applications New Techniques for Control and Systems: Numerical Linear Algebra Estimation and Identification using Hidden Markov Models Applications of Stochastic Control Topics in Linear Design Nonlinear Control and Stabilisation II Ambulatory Robot Systems Chaotic and Oscillatory Systems Biomedical System Control Integrated Control and CPU Scheduling Linear Design Techniques Adaptive Disturbance / Noise Compensation Nonlinear Model Predictive Control Sensitivity Design, Analysis and Limitations Analysis of Linear Systems Linear Matrix Inequalities in Design Lyapunov's 2nd Method Robotics: Tracking Control Lagrangian and Hamiltonian Theory Variable Structure Control Machine Vision Signal Processing Methods in Control Applied Nonlinear Control Author Index A B C D E F G H I J K L M N O P Q R S T U V W X Y Z	On Dynamic Scheduling Of Stochastic Networks In Heavy Traffic And Some New Results For The Workload Process Authors: Maury Bramson, Ruth J. Williams, Volume: 1, Page 516 Paper number 4501 Abstract: Dynamic scheduling of stochastic networks has applications to the control of modern telecommunications, manufacturing and computer systems. Most models of such networks cannot be analyzed exactly, and one is naturally led to consider more viable approximations. As one approach, J. M. Harrison proposed Brownian control problems (BCPs) as formal heavy traffic approximations to dynamic scheduling problems for stochastic networks. Subsequently, various authors combined analysis of BCPs with interpretation of their optimal solutions to suggest original and attractive policies for certain specific stochastic network control problems. Despite these successes for specific problems, there is, as yet, no general rigorous approach to analyzing BCPs, inferring good policies from their solutions, and proving asymptotic optimality of such policies. We are interested in developing such an approach. This paper is a step in that direction. In particular, we (a) provide a detailed stochastic network model, (b) give a fluid model interpretation of the notion of heavy traffic, (c) derive a formula for the dimension of the workload process in terms of basic model parameters and show that the components of the workload process are non-negative under a mild assumption, and (d) interpret the solution of the BCP for parallel server systems, under a complete resource pooling condition. This interpretation is in terms of a "continuous review threshold policy", which is shown to be asymptotically optimal in a separate recent work of Bell and Williams. CD004501.PDF (From Author) TOP A Numerical Method for Solving Singular Brownian Control Problems Authors: Sunil Kumar, Muthukumar Muthuraman, Volume: 1, Page 522 Paper number 4502 Abstract: The Brownian approximation approach to developing dynamic control policies for multiclass queueing networks is useful when the limiting, usually singular, Brownian control problem can be solved. However, this problem can be rarely solved analytically. In this paper we present a method for numerically solving singular Brownian control problems. We adapt finite element methods to iteratively solve the Hamilton-Jacobi-Bellman equation associated with the Brownian control problem. A key feature of our method is that the presence of singular controls simplifies the procedure. The solution to the Hamilton-Jacobi-Bellman equation is then used to construct an optimal control for the Brownian system. We illustrate the method on two examples of singular Brownian control problems. CD004502.PDF (From Author) TOP Large Deviations-Based Asymptotics for Inventory Control in Supply Chains Authors: Ioannis Ch. Paschalidis, Yong Liu, Volume: 1, Page 528 Paper number 4504 Abstract: We consider a model of a capacitated single-class supply chain consisting of a tandem of production facilities and propose production policies in two cases:(a) when each facility has access to its local inventory only, and (b) when it has knowledge of the total downstream inventory. In case (a) the proposed policy guarantees stockout probabilities at each stage to stay bounded below given constants (service level constraints). In case (b) we minimize total expected inventory cost subject to service level constraints. In both cases we rely upon large deviations asymptotics to analytically obtain the policy parameters; this leads to huge computational savings compared to simulation. Our model can accommodate autocorrelated demand and service processes, both critical features of modern failure-prone manufacturing systems. We demonstrate that detailed distributional information on demand and service processes, which is incorporated into large deviations asymptotics, is critical in inventory control decisions. Some extensions to a multiclass setting are discussed. CD004504.PDF (From Author) TOP Performance of Multiclass Markovian Queueing Networks Authors: Dimitris Bertsimas, David Gamarnik, John Tsitsiklis, Volume: 1, Page 534 Paper number 4507 Abstract: We study the distribution of steady-state queue lengths in multiclass queueing networks under a stable policy. We propose a general methodology based on Lyapunov functions, for the performance analysis of infinite state Markov chains and apply it specifically to Markovian multiclass queueing networks. We establish a deeper connection between stability and performance of such networks by showing that if there exist linear and piecewise linear Lyapunov functions that show stability, then these Lyapunov functions can be used to establish geometric type lower and upper bounds on the tail probabilities, and thus bounds on the expectation of the queue lengths. As an example of our results, for a re-entrant line queueing network with two processing stations operating under a work-conserving policy we show that E[L] =O( (fraction)1(1-(rho)^)^2), where L is the total number of customers in the system, and ((rho)^) is the maximal actual or virtual traffic intensity in the network. This extends a recent result by Dai and Vande-Vate, which states that a re-entrant line queueing network with two stations is globally stable if ((rho)^*<1. ) We also present several results on the performance of multiclass queueing networks operating under general Markovian, and in particular, priority policies. The results in this paper are the first that establish explicit geometric type upper and lower bounds on tail probabilities of queue lengths, for networks of such generality. Previous results provide numerical bounds and only on the expectation, not the distribution, of queue lengths. CD004507.PDF (From Author) TOP Optimal Control for Steel Annealing Processes as Hybrid Systems Authors: Young C. Cho, Wook Hyun Kwon, Christos G. Cassandras, Volume: 1, Page 540 Paper number 4402 Abstract: This paper formulates and solves an optimal control problem for steel annealing manufacturing processes involving one or more furnaces integrated with plant-wide planning and scheduling operations. We use a hybrid system framework to capture the tradeoff between metallurgical quality requirements and timely product delivery. The resulting nonconvex and nondifferentiable problem is solved by decomposing it into several smaller and simpler constrained convex optimization subproblems. Although the number of such subproblems appears to be combinationally large in the number N of jobs to be completed, we use a recently developed approach for identifying at most 2N-1 such problems and provide some explicit numerical results. CD004402.PDF (From Author) TOP A Unified Approach to Linear Programming Bounds for Queueing Networks: Systems with Polyhedral Invariance of Transition Probabilities Authors: James R. Morrison, Panganamala R. Kumar, Volume: 1, Page 546 Paper number 4403 Abstract: We develop a framework for obtaining linear programming performance bounds in queueing networks. The structure allowing for the development of the bounds requires that the underlying Markov Chain model possess translational invariance of its transition probabilities on polyhedra. Such a structure is exhibited by many systems of interest. The bounds are then obtained via a performance-to- performance duality. CD004403.PDF (From Author) TOP Improving the Lagrangian Relaxation Approach for Large Job-Shop Scheduling Authors: Lei Fang, Peter B. Luh, Haoxun Chen, Volume: 1, Page 552 Paper number 4406 Abstract: Lagrangian Relaxation (LR) has recently emerged as a practical approach for job shop scheduling problems of realistic size. The efficiency of the approach, however, depends on how fast the dual problem is solved and how good the feasible solutions are constructed. The purpose of this paper is to address above two issues. First, a "variable target value" method is used to regulate the step size for surrogate subgradient optimization. The target values are updated iteratively whenever necessary, depending on the information obtained in the process of the algorithm. The convergence of the algorithm is proved using practically desirable step size rule. Then based on the insights of the old list scheduling algorithm, the SPT/CR priority index is selected in place of the incremental cost index. Testing results show that these modifications make the LR approach computationally more efficient and five to eight percent of duality gap improvement was obtained for large problems. CD004406.PDF (From Author) TOP