Stability analysis of N-model systems under a static priority rule

We consider the stability of N-model systems that consist of two customer classes and two server pools. Servers in one of the pools can serve both classes, but those in the other pool can serve only one of the classes. The standard fluid models in general are not sufficient to establish the stability region of these systems under static priority policies. Therefore, we use a novel and a general approach to augment the fluid model equations based on induced Markov chains. Using this new approach, we establish the stability region of these systems under a static priority rule with thresholds when the service and interarrival times have phase-type distributions. We show that, in certain cases, the stability region depends on the distributions of the service and interarrival times (beyond their mean), on the number of servers in the system, and on the threshold value. We also show that it is possible to expand the stability region in these systems by increasing the variability of the service times (without changing their mean) while keeping the other parameters fixed. The extension of our results to parallel server systems and general service time distributions is also discussed.     

On the stability of queueing systems under precedence restrictions for the service of customers

We consider queueing systems under precedence-based queueing disciplines and derive conditions for the stability of the system. The precedence restrictions are posed on customers' service in a way that a service can start only if some previous customers are served completely and some later customers arrived already. The stability depends on the interarrival times only through their means and the stability condition splits into two terms: with respect to a typical customer, one is representing the influences of future arrivals and one is representing the influences of past arrivals.     

The discrete-time MAP/PH/1 queue with multiple working vacations

We consider a discrete-time single-server queueing model where arrivals are governed by a discrete Markovian arrival process (DMAP), which captures both burstiness and correlation in the interarrival times, and the service times and the vacation duration times are assumed to have a general phase-type distributions. The vacation policy is that of a working vacation policy where the server serves the customers at a lower rate during the vacation period as compared to the rate during the normal busy period. Various performance measures of this queueing system like the stationary queue length distribution, waiting time distribution and the distribution of regular busy period are derived. Through numerical experiments, certain insights are presented based on a comparison of the considered model with an equivalent model with independent arrivals, and the effect of the parameters on the performance measures of this model are analyzed.     

Optimal control of parallel server systems with many servers in heavy traffic

We consider a parallel server system that consists of several customer classes and server pools in parallel. We propose a simple robust control policy to minimize the total linear holding and reneging costs. We show that this policy is asymptotically optimal under the many-server heavy traffic regime for parallel server systems when the service times are only server pool dependent and exponentially distributed. J.G. Dai’s research supported in part by National Science Foundation grants CMMI-0727400 and CNS-0718701, and by an IBM Faculty Award.     

Analysis of the infinite server queues with semi-Markovian multivariate discounted inputs

We consider a general k-dimensional discounted infinite server queueing process (alternatively, an incurred but not reported claim process) where the multivariate inputs (claims) are given by a k-dimensional finite-state Markov chain and the arrivals follow a renewal process. After deriving a multidimensional integral equation for the moment-generating function jointly to the state of the input at time t given the initial state of the input at time 0, asymptotic results for the first and second (matrix) moments of the process are provided. In particular, when the interarrival or service times are exponentially distributed, transient expressions for the first two moments are obtained. Also, the moment-generating function for the process with deterministic interarrival times is considered to provide more explicit expressions. Finally, we demonstrate the potential of the present model by showing how it allows us to study semi-Markovian modulated infinite server queues where the customers (claims) arrival and service (reporting delay) times depend on the state of the process immediately before and at the switching times.

     

Large sample inference from single server queues

Problems of large sample estimation and tests for the parameters in a single server queue are discussed. The service time and the interarrivai time densities are assumed to belong to (positive) exponential families. The queueing system is observed over a continuous time interval (0,T] whereT is determined by a suitable stopping rule. The limit distributions of the estimates are obtained in a unified setting, and without imposing the ergodicity condition on the queue length process. Generalized linear models, in particular, log-linear models are considered when several independent queues are observed. The mean service times and the mean interarrival times after appropriate transformations are assumed to satisfy a linear model involving unknown parameters of interest, and known covariates. These models enhance the scope and the usefulness of the standard queueing systems.Partially supported by the U. S. Army Research Office through the Mathematical Sciences Institute of Cornell University.     

Single line queue with repeated demands

We analyze a model of a queueing system in which customers can only call in to request service: if the server is free, the customer enters service immediately, but if the service system is occupied, the unsatisfied customer must break contact and reinitiate his request later. Such a customer is said to be in “orbit”. In this paper we consider three models characterized by the discipline governing the order of re-request of service from orbit. First, all customers in orbit can reapply, but are discouraged and reduce their rate of demand as more customers join the orbit. Secondly, the FCFS discipline operates for the unsatisfied customers in orbit. Finally, the LCFS discipline governs the customers in orbit and the server takes an exponentially distributed vacation after each service is completed. We calculate several characteristics quantities of such systems, assuming a general service-time distribution and different exponential distributions for the times between arrivals of first and repeat requests.     

GI／PH／1休假排队系统队长的随机分解

对空竭服务、多重休假规则的GI/PH/1排队系统的稳态行为给出了详尽分析。在休假时间服从负指数分布情况下,讨论了到达点嵌入Markov链的结构、平衡条件和稳态队长。证明稳态队长可分解成两个独立随机变量之和。     

Randomly Interrupted GI-G-1 Queues: Service Strategies and Stability Issues

We consider a discrete-time queueing system subjected to random server interruptions. As customers arriving in the queue require generally distributed service times, the server can be interrupted during a customer's service. Therefore, nine different service strategies are proposed and analyzed using a probability generating functions approach. Performance measures under investigation include moments of steady-state buffer contents at random slot boundaries in equilibrium and moments of the customer delay. In particular we focus on the stability requirements for the strategies under consideration.     

Scheduling networks of queues: Heavy traffic analysis of a simple open network

We consider a queueing network with two single-server stations and two types of customers. Customers of type A require service only at station 1 and customers of type B require service first at station 1 and then at station 2. Each server has a different general service time distribution, and each customer type has a different general interarrival time distribution. The problem is to find a dynamic sequencing policy at station 1 that minimizes the long-run average expected number of customers in the system.The scheduling problem is approximated by a dynamic control problem involving Brownian motion. A reformulation of this control problem is solved, and the solution is interpreted in terms of the queueing system in order to obtain an effective sequencing policy. Also, a pathwise lower bound (for any sequencing policy) is obtained for the total number of customers in the network. We show via simulation that the relative difference between the performance of the proposed policy and the pathwise lower bound becomes small as the load on the network is increased toward the heavy traffic limit.     

Importance sampling algorithms for first passage time probabilities in the infinite server queue

This paper applies importance sampling simulation for estimating rare event probabilities of the first passage time in the infinite server queue with renewal arrivals and general service time distributions. We consider importance sampling algorithms which are based on large deviations results of the infinite server queue, and we consider an algorithm based on the cross-entropy method, where we allow light-tailed and heavy-tailed distributions for the interarrival times and the service times. Efficiency of the algorithms is discussed by simulation experiments.     

A server backup model with Markovian arrivals and phase type services

We consider a finite capacity queueing system with one main server who is supported by a backup server. We assume Markovian arrivals, phase type services, and a threshold-type server backup policy with two pre-determined lower and upper thresholds. A request for a backup server is made whenever the buffer size (number of customers in the queue) hits the upper threshold and the backup server is released from the system when the buffer size drops to the lower threshold or fewer at a service completion of the backup server. The request time for the backup server is assumed to be exponentially distributed. For this queuing model we perform the steady state analysis and derive a number of performance measures. We show that the busy periods of the main and backup servers, the waiting times in the queue and in the system, are of phase type. We develop a cost model to obtain the optimal threshold values and study the impact of fixed and variable costs for the backup server on the optimal server backup decisions. We show that the impact of standard deviations of the interarrival and service time distributions on the server backup decisions is quite different for small and large values of the arrival rates. In addition, the pattern of use of the backup server is very different when the arrivals are positively correlated compared to mutually independent arrivals.     

Higher order approximations for tandem queueing networks

In this paper a higher order approximation for single server queues and tandem queueing networks is proposed and studied. Different from the most popular two-moment based approximations in the literature, the higher order approximation uses the higher moments of the interarrival and service distributions in evaluating the performance measures for queueing networks. It is built upon the MacLaurin series analysis, a method that is recently developed to analyze single-node queues, along with the idea of decomposition using higher orders of the moments matched to a distribution. The approximation is computationally flexible in that it can use as many moments of the interarrival and service distributions as desired and produce the corresponding moments for the waiting and interdeparture times. Therefore it can also be used to study several interesting issues that arise in the study of queueing network approximations, such as the effects of higher moments and correlations. Numerical results for single server queues and tandem queueing networks show that this approximation is better than the two-moment based approximations in most cases.     

A quorum queueing system with an unreliable server

We analyze a bulk service queueing system with an unreliable server, Poisson input, and general service and repair times. A stability condition and steady state system size distributions are obtained. The optimal management policy is discussed and illustrative examples are provided.     

The cyclic queue and the tandem queue

We consider a closed queueing network, consisting of two FCFS single server queues in series: a queue with general service times and a queue with exponential service times. A fixed number \(N\) of customers cycle through this network. We determine the joint sojourn time distribution of a tagged customer in, first, the general queue and, then, the exponential queue. Subsequently, we indicate how the approach toward this closed system also allows us to study the joint sojourn time distribution of a tagged customer in the equivalent open two-queue system, consisting of FCFS single server queues with general and exponential service times, respectively, in the case that the input process to the first queue is a Poisson process.     

具有位相型修理的离散时间可修排队系统

本文研究了具有一般独立输入，位相型修理的离散时间可修排队系统，假定服务台对顾客的服务时间和服务台寿命服从几何分布，运用矩阵解析方法我们给出系统嵌入在到达时刻的稳态队长分布和等待时间分布，并证明这些分布均为离散位相型分布．我们也得到在广义服务时间内服务台发生故障次数的分布，证明它服从一个修正的几何分布．我们对离散时间可修排队与连续时间可修排队进行了比较，说明这两种排队系统在一些性能指标方面的区别之处．最后我们通过一些数值例子说明在这类系统中顾客的到达过程、服务时间和服务台的故障率之间的关系．     

Measurement and optimization of robust stability of multiclass queueing networks: Applications in dynamic supply chains

Multiclass queueing networks are an essential tool for modeling and analyzing complex supply chains. Roughly speaking, stability of these networks implies that the total number of customers/jobs in the network remains bounded over time. In this context robustness characterizes the ability of a multiclass queueing network to remain stable, if the expected values of the interarrival and service times distributions are subject to uncertain shifts. A powerful starting point for the stability analysis of multiclass queueing networks is the associated fluid network. Based on the fluid network analysis we present a measure to quantify the robustness, which is indicated by a single number. This number will be called the stability radius. It represents the magnitude of the smallest shift of the expected value of the interarrival and/or service times distributions so that the associated fluid network looses the property of stability. The stability radius is a worst case measure and is a conceptual adaptation from the dynamical systems literature. Moreover, we provide a characterization of the shifts that destabilize the network. Based on these results, we formulate a mathematical program that minimizes the required network capacity, while ensuring a desired level of robustness towards shifts of the expected values of the interarrival times distributions. This approach provides a new view on long-term robust production capacity allocation in supply chains. The capabilities of our method are demonstrated using a real world supply chain.     

On balking from an empty queue

The intuition while observing the economy of queueing systems, is that one’s motivation to join the system, decreases with its level of congestion. Here we present a queueing model where sometimes the opposite is the case. The point of departure is the standard first-come first-served single server queue with Poisson arrivals. Customers commence service immediately if upon their arrival the server is idle. Otherwise, they are informed if the queue is empty or not. Then, they have to decide whether to join or not. We assume that the customers are homogeneous and when they consider whether to join or not, they assess their queueing costs against their reward due to service completion. As the whereabouts of customers interact, we look for the (possibly mixed) join/do not join Nash equilibrium strategy, a strategy that if adopted by all, then under the resulting steady-state conditions, no one has any incentive not to follow it oneself. We show that when the queue is empty then depending on the service distribution, both ‘avoid the crowd’ (ATC) and ‘follow the crowd’ (FTC) scenarios (as well as none-of-the-above) are possible. When the queue is not empty, the situation is always that of ATC. Also, we show that under Nash equilibrium it is possible (depending on the service distribution) that the joining probability when the queue is empty is smaller than it is when the queue is not empty. This research was supported by The Israel Science Foundation Grant No. 237/02.     

Analysis of the M [X]/G/1 queues with second multi-optional service and unreliable server

A bulk-arrival single server queueing system with second multi-optional service and unreliable server is studied in this paper. Customers arrive in batches according to a homogeneous Poisson process, all customers demand the first ＂essential＂ service, whereas only some of them demand the second ＂multi-optional＂ service. The first service time and the second service all have general distribution and they are independent. We assume that the server has a service-phase dependent, exponentially distributed life time as well as a servicephase dependent, generally distributed repair time. Using a supplementary variable method, we obtain the transient and the steady-state solutions for both queueing and reliability measures of interest.     

Queues with Workload-Dependent Arrival and Service Rates

We consider two types of queues with workload-dependent arrival rate and service speed. Our study is motivated by queueing scenarios where the arrival rate and/or speed of the server depends on the amount of work present, like production systems and the Internet. First, in the M/G/1 case, we compare the steady-state distribution of the workload (both at arbitrary epochs and at arrival instants) in two models, in which the ratio of arrival rate and service speed is equal. Applying level crossing arguments, we show that the steady-state distributions are proportional. Second, we consider a G/G/1-type queue with workload-dependent interarrival times and service speed. Using a stochastic mean-value approach, several well-known relations for the workload at various epochs in the ordinary G/G/1 queue are generalized.