Analysis of a queueing system with a general service scheduling function,with applications to telecommunication network traffic control

In this paper we analyze a queueing system with a general service scheduling function. There are two types of customer with different service requirements. The service order for customers of each type is determined by the service scheduling function α_k(i, j) where α_k(i, j) is the probability for type-k customer to be selected when there are i type-1 and j type-2 customers. This model is motivated by traffic control to support traffic streams with different traffic characteristics in telecommunication networks (in particular, ATM networks). By using the embedded Markov chain and supplementary variable methods, we obtain the queue-length distribution as well as the loss probability and the mean waiting time for each type of customer. We also apply our model to traffic control to support diverse traffics in telecommunication networks. Finally, the performance measures of the existing diverse scheduling policies are compared. We expect to help the system designers select appropriate scheduling policy for their systems.     

Analysis of a time-limited service priority queueing system with exponential timer and server vacations

We consider a multi-class priority queueing system with a non-preemptive time-limited service controlled by an exponential timer and multiple (or single) vacations. By reducing the service discipline to the Bernoulli schedule, we obtain an expression for the Laplace-Stieltjes transform (LST) of the waiting time distribution via an iteration procedure, and a recursive scheme to calculate the first two moments. It is noted that we have to select embedded Markov points based on the service beginning epochs instead of the service completion epochs adopted for most of M/G/1 queueing analyses. Through the queue-length analysis, we obtain a decomposition form for the LST of the waiting time in each queue having the exhaustive service.      

Robustness of perturbation analysis estimators for queueing systems with unknown distributions

Sample-path-based stochastic gradient estimators for performance measures of queueing systems rely on the assumption that a probability distribution of the random vector of interest (e.g., a service or interarrival time sequence) is given. In this paper, we address the issue of dealing with unknown probability distributions and investigate the robustness of such estimators with respect to possibly erroneous distribution choices. We show that infinitesimal perturbation analysis (IPA) can be robust in this sense and, in some cases, provides distribution-independent estimates. Comparisons with other gradient estimators are provided, including experimental results. We also show that finite perturbation analysis (FPA), though only providing gradient approximations, possesses some attractive robustness properties with respect to unknown distribution parameters. An application of FPA estimation is included for a queueing system performance optimization problem involving customers with real-time constraints.This work was supported in part by the National Science Foundation Grant ECS-88-01912 and by the Office of Naval Research Contract N00014-87-K-0304.The authors wish to thank Dr. Jack Holtzman for several useful comments and suggestions.     

The achievable region method in the optimal control of queueing systems; formulations,bounds and policies

We survey a new approach that the author and his co-workers have developed to formulate stochastic control problems (predominantly queueing systems) asmathematical programming problems. The central idea is to characterize the region of achievable performance in a stochastic control problem, i.e., find linear or nonlinear constraints on the performance vectors that all policies satisfy. We present linear and nonlinear relaxations of the performance space for the following problems: Indexable systems (multiclass single station queues and multiarmed bandit problems), restless bandit problems, polling systems, multiclass queueing and loss networks. These relaxations lead to bounds on the performance of an optimal policy. Using information from the relaxations we construct heuristic nearly optimal policies. The theme in the paper is the thesis that better formulations lead to deeper understanding and better solution methods. Overall the proposed approach for stochastic control problems parallels efforts of the mathematical programming community in the last twenty years to develop sharper formulations (polyhedral combinatorics and more recently nonlinear relaxations) and leads to new insights ranging from a complete characterization and new algorithms for indexable systems to tight lower bounds and nearly optimal algorithms for restless bandit problems, polling systems, multiclass queueing and loss networks.     

Two‐tier healthcare service systems and cost of waiting for patients

Waiting has been a significant concern for healthcare services. We address this issue in the context of a two‐tier service system in this study. A two‐tier healthcare service system consists of two different service providers, typically one public service provider and one private service provider. In a baseline model, the two service providers are modeled by two queue servers, which charge each patient a common fixed fee for the service. Then, we study a queue model in which one service provider offers a subsidy or charges a premium while the other maintains the fixed service fee. This system provides a mechanism to segment patients along their waiting time cost through price discrimination. We analyze the problem from both the perspective of minimizing total waiting cost for all patients and the perspective of maximizing social gain for the public service provider or profit for the private service provider. We show that this model can significantly alleviate the burden of waiting for patients. The study addresses the design, the efficiency, and the implementation of two‐tier healthcare service systems. Copyright © 2017 John Wiley & Sons, Ltd.     

A sufficient condition and a necessary condition for the diffusion approximations of multiclass queueing networks under priority service disciplines

We establish a sufficient condition for the existence of the (conventional) diffusion approximation for multiclass queueing networks under priority service disciplines. The sufficient condition relates to a sufficient condition for the weak stability of the fluid networks that correspond to the queueing networks under consideration. In addition, we establish a necessary condition for the network to have a continuous diffusion limit; the necessary condition is to require a reflection matrix (of dimension equal to the number of stations) to be completely-S. When applied to some examples, including generalized Jackson networks, single station multiclass queues, first-buffer-first-served re-entrant lines, a two-station Dai–Wang network and a three-station Dumas network, the sufficient condition coincides with the necessary condition.     

Reduced gradient method combined with augmented Lagrangian and barrier for the optimal power flow problem

A new approach for solving the optimal power flow (OPF) problem is established by combining the reduced gradient method and the augmented Lagrangian method with barriers and exploring specific characteristics of the relations between the variables of the OPF problem. Computer simulations on IEEE 14-bus and IEEE 30-bus test systems illustrate the method.     

On the convergence of inexact augmented Lagrangian methods for problems with convex constraints

We consider the augmented Lagrangian method (ALM) for constrained optimization problems in the presence of convex inequality and convex abstract constraints. We focus on the case where the Lagrangian sub-problems are solved up to approximate stationary points, with increasing accuracy. We analyze two different criteria of approximate stationarity for the sub-problems and we prove the global convergence to stationary points of ALM in both cases.     

An outer approximation method for minimizing the product of several convex functions on a convex set

This paper addresses the minimization of the product ofp convex functions on a convex set. It is shown that this nonconvex problem can be converted to a concave minimization problem withp variables, whose objective function value is determined by solving a convex minimization problem. An outer approximation method is proposed for obtaining a global minimum of the resulting problem. Computational experiments indicate that this algorithm is reasonable efficient whenp is less than 4.This research was partly supported by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. (C)03832018 and (C)04832010.     

Optimal Threshold for the k-Out-Of-n Monitor with Dual Failure Modes

A monitor consists of n identical sensors working independently. Each sensor measures a variate of output or environment of a system, and is activated if a variate is over a threshold specified in advance for each sensor. The monitor alarms if at least k out of n sensors are activated. The performance of the monitor, the probabilities of failure to alarm and false alarming, depends on the number k, the threshold values and the probability distributions of the variate at normal and abnormal states of the system. In this paper, a sufficient condition on the pair of the distributions is given under which the same threshold values for all the sensors are optimal. The condition motivates new orders between probability distributions. Solving an optimization problem an explicit condition is obtained for maximizing or minimizing a symmetric function with the constraint of another symmetric function.     

Optimal convergence rates to nonlinear diffusion waves for the compressible Euler-Poisson system with damping

In this work, we study the 1-D isentropic bipolar hydrodynamic model. This model takes the form of compressible Euler-Poisson system with nonlinear damping added to the momentum equations. Under some smallness conditions, the solutions to the Cauchy problem of the system globally exist and convergence to the nonlinear diffusion waves, which are the corresponding solutions of nonlinear parabolic equations given by the Darcy's law with a specified initial data. The optimal convergence rates are obtained by Green function method when the initial perturbation is in L¹-space.     

非线性优化修正Frisch函数方法的乘子映射

对于同时含有等式与不等式约束的非线性优化问题的修正Frisch函数方法,给出其乘子映射和解映射的导数的估计.将得到的估计用于建立修正Frisch函数方法的线性收敛速率.在线性无关的约束规范,严格互补条件和二阶充分性条件成立的前提下,证得该收敛率与1/c成正比.本文的收敛性分析依赖于矩阵的奇异值分解,其方法可以用来分析其他的修正Lagrange方法.     

变质量非线性非完整系统相对运动动力学方程的积分方法

本文给出积分变质量非线性非完整系统相对于非惯性系动力学方程的梯度法,单分量法和场方法。首先,将这类问题的动力学方程表示为正则形式和场方程形式;然后,分别用梯度法,单分量法和场方法积分相应常质量完整系统相对于惯性系的动力学方程,并加上非完整约束对初始条件的限制而得到变质量非线性非完整系统相对于非惯性系动力学方程的解。     

Maintaining the positive definiteness of the matrices in reduced secant methods for equality constrained optimization

We propose an algorithm for minimizing a functionf on ⁿ in the presence ofm equality constraintsc that locally is a reduced secant method. The local method is globalized using a nondifferentiable augmented Lagrangian whose decrease is obtained by both a longitudinal search that decreases mainlyf and a transversal search that decreases mainly c. Our main objective is to show that the longitudinal path can be designed to maintain the positive definiteness of the reduced matrices by means of the positivity of _k ^T _k , where _k is the change in the reduced gradient and _k is the reduced longitudinal displacement.Work supported by the FNRS (Fonds National de la Recherche Scientifique) of Belgium.     

Necessary conditions of optimality for a class of second-order hyperbolic systems with spatially dependent controls in the coefficients

In the paper, we consider the problem of parameter optimization for a class of second-order hyperbolic systems with distributional forcing terms. After necessary preparations in Sections 1 and 3, we develop in Section 4 the necessary conditions of optimality for the system with quadratic cost function. In Section 5, we extend these results to cover a wider class of controls; we also prove the existence of suboptimal policies. An example is presented indicating possible application to power system regulation problems.This work was supported in part by the National Science and Engineering Council of Canada under Grant No. 7109.The author would like to thank Professor L. Cesari for pointing out in a private communication that there are situations like the Lavrentiev phenomenon in which an approximation analogous to that given in Theorem 5.3 is not possible.     

Uniform decay rates for the energy of weakly damped defocusing semilinear Schrödinger equations with inhomogeneous Dirichlet boundary control

In this paper, we study the open loop stabilization as well as the existence and regularity of solutions of the weakly damped defocusing semilinear Schrödinger equation with an inhomogeneous Dirichlet boundary control. First of all, we prove the global existence of weak solutions at the H¹-energy level together with the stabilization in the same sense. It is then deduced that the decay rate of the boundary data controls the decay rate of the solutions up to an exponential rate. Secondly, we prove some regularity and stabilization results for the strong solutions in H²-sense. The proof uses the direct multiplier method combined with monotonicity and compactness techniques. The result for weak solutions is strong in the sense that it is independent of the dimension of the domain, the power of the nonlinearity, and the smallness of the initial data. However, the regularity and stabilization of strong solutions are obtained only in low dimensions with small initial and boundary data.