Algorithms for computing waiting time distributions under different queue disciplines for the D-BMAP/PH/1

A queueing system characterized by the discrete batch Markovian arrival process (D-BMAP) and a probability of phase type distribution for the service time is one that arises frequently in the area of telecommunications. Under this arrival process and service time distribution we derive the waiting time distribution for three queue disciplines: first in first out (FIFO), last in first out (LIFO), and service in random order (SIRO). We also outline efficient algorithmic procedures for computing the waiting time distributions under each discipline. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 559–576, 1997     

Bounds on parallel-processing of queues with multiple-phase jobs

Currently, both the hardware and software designs of many large computing systems aim at improved system performance through exploitation of parallelism in multiprocessor systems. In studying these systems, mathematical modelling and analysis constitute an important step towards providing design tools that can be used in building such systems. With this view the present paper describes a queueing model of a multiprocessor system operating in a job-shop environment in which arriving jobs consist of a random number of segments (sub-jobs). Two service disciplines are considered: one assumes that the sub-jobs of a given job are capable of parallel operation on different processors while the other assumes that the same sub-jobs must be operated in a strictly serial sequ'snce. The results (in particular, the mean number in the system and waiting time in queue) obtained for these two disciplines are shown to be bounds for more general job structures.     

Waiting time analysis for a queueing system with time‐limited service and exponential timer

We consider a single‐queue with exhaustive or gated time‐limited services and server vacations, in which the length of each service period at the queue is controlled by a timer, i.e., the server serves customers until the timer expires or the queue becomes empty, whichever occurs first, and then takes vacations. The customer whose service is interrupted due to the timer expiration may be attended according to nonpreemptive or preemptive service disciplines. For the M/G/1 exhaustive/gated time‐limited service queueing system with an exponential timer and four typical preemptive/nonpreemptive service disciplines, we derive the Laplace—Stieltjes transforms and the moment formulas for waiting times and sojourn times through a unified approach, and provide some new results for these time‐limited service disciplines. © John Wiley & Sons, Inc. Naval Research Logistics 48: 638–651, 2001.     

Stochastic analysis of a single server retrial queue with general retrial times

Retrial queueing systems are widely used in teletraffic theory and computer and communication networks. Although there has been a rapid growth in the literature on retrial queueing systems, the research on retrial queues with nonexponential retrial times is very limited. This paper is concerned with the analytical treatment of an M/G/1 retrial queue with general retrial times. Our queueing model is different from most single server retrial queueing models in several respectives. First, customers who find the server busy are queued in the orbit in accordance with an FCFS (first‐come‐first‐served) discipline and only the customer at the head of the queue is allowed for access to the server. Besides, a retrial time begins (if applicable) only when the server completes a service rather upon a service attempt failure. We carry out an extensive analysis of the queue, including a necessary and sufficient condition for the system to be stable, the steady state distribution of the server state and the orbit length, the waiting time distribution, the busy period, and other related quantities. Finally, we study the joint distribution of the server state and the orbit length in non‐stationary regime. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 561–581, 1999     

Level crossing analysis of priority queues and a conservation identity for vacation models

The two purposes of this article are to illustrate the power and simplicity of level crossing analysis and to present a conservation identity for M/G/1 priority queues with server vacations. To illustrate the use of level crossing analysis we apply it to preemptive (resume) priority M/G/1 queues with single- and multiple-server vacations considered by Kella and Yechiali (1986) and to non-preemptive priority M/M/c queues considered by Kella and Yechiali (1985). The conservation identity presented here states that the ratios of mean waiting times in an M/G/1 queue with and without server vacation policies are independent of the service discipline for first come first served, shortest processing time, shortest processing time within generations and non-preemptive priority service disciplines.     

Approximation for the departure process of a queue in a network

A simple renewal process is identified to approximate the complex departure process of a queue often found in queueing network models. The arrival process to the queue is the superposition or merging of several independent component-renewal processes that are approximations of departure processes from other queues and external arrival processes; there is a single server with exponential service times, and the waiting space is infinite. The departure process of this queue is of interest because it is the arrival process to other queues in the network. The approximation proposed is a hybrid; the mean and variance of the approximating departure intervals is a weighted average of those determined by basic methods in Whitt [41] with the weighting function empirically determined using simulation. Tandem queueing systems with superposition arrival processes and exponential service times are used to evaluate the approximation. The departure process of the first queue in the tandem is approximated by a renewal process, the tandem system is replaced by two independent queues, and the second queue is solved analytically. When compared to simulation estimates, the average absolute error in hybrid approximations of the expected number in the second queue is 6%, a significant improvement over 22–41% in the basic methods.     

Sojourn times in a two‐stage queueing network with blocking

The model considered in this paper involves a tandem queue consisting of a sequence of two waiting lines. The main feature of our model is blocking, i.e., as soon as the second waiting line reaches a certain upper limit, the first line is blocked. The input of units to the tandem queue is the MAP (Markovian arrival process), and service requirements are of phase type. Our objective is to study the sojourn time distribution under the first‐come‐first‐serve discipline by analyzing the sojourn time through times until absorption in appropriately defined quasi‐birth‐and‐death processes and continuous‐time Markov chains. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Queues with stochastic service rates

The purpose of this paper is to explore an extension of the output discipline for the Poisson input, general output, single channel, first-come, first-served queueing system. The service time parameter, μ, is instead considered a random variable, M. In other words, the service time random variable, T, is to be conditioned by a parameter random variable, M. Therefore, if the distribution function of M is denoted by F_M(μ) and the known conditional service time distribution as B(t |_μ), then the unconditional service distribution is given by B(t) = Pr {T ≤ t}. = ∫_-∞^∞ B(t |_μ) dF_M(μ). Results are obtained that characterize queue size and waiting time using the imbedded Markov chain approach. Expressions are derived for the expected queue length and Laplace-Stieltjes transforms of the steady-state waiting time when conditional service times are exponential. More specific results are found for three special distributions of M: (1) uniform on [1.2]; (2) two-point; and (3) gamma.     

Estimation in single server queues

Moment and maximum likelihood estimates (m.l.e.'s) arc investigated for nonparametric and parametric models for a single server queue observed over a random time horizon, namely, up to the nth departure epoch. Also. m.l.e's of the mean interarrival time and mean service time in anM/M/1 queue observed over a fixed time-interval are studied Limit distributions of these estimates are obtained Without imposing steady state assumptions on the queue-size or waiting time processes.     

The single server queue in discrete time-numerical analysis III

This paper deals with the stationary analysis of the finite, single server queue in discrete time. The following stntionary distributions and other quantities of practical interest are investigated: (1) the joint density of the queue length and the residual service time, (2) the queue length distribution and its mean, (3) the distribution of the residual service time and its mean, (4) the distribution and the expected value of the number of customers lost per unit of time due to saturation of the waiting capacity, (5) the distribution and the mean of the waiting time, (6) the asymptotic distribution of the queue length following departures The latter distribution is particularly noteworthy, in view of the substantial difference which exists, in general, between the distributions of the queue lengths at arbitrary points of time and those immediately following departures.     

The queue G/M/m/N: Busy period and cycle,waiting time under reverse and random order service

The busy period, busy cycle, and the numbers of customers served and lost therein, of the G/M/m queue with balking is studied via the embedded Markov chain approach. It is shown that the expectations of the two discrete variables give the loss probability. For the special case G/M/1/N a closed expression in terms of contour integrals is obtained for the Laplace transform of these four variables. This yields as a byproduct the LIFO waiting time distribution for the G/M/m/N queue. The waiting time under random order service for this queue is also studied.     

A note on sojourn times in M/G/1 queues with instantaneous,bernoulli feedback

Queueing systems which include the possibility for a customer to return to the same server for additional service are called queueing systems with feedback. Such systems occur in computer networks for example. In these systems a chosen customer will wait in the queue, be serviced and then, with probability p, return to wait again, be serviced again and continue this process until, with probability (1 – p) = q, it departs the system never to return. The time of waiting plus service time, the nth time the customer goes through, we will call his nth sojourn time. The (random) sum of these sojourn times we will call the total sojourn time (abbreviated, sojourn time when there is no confusion which sojourn time we are talking about). In this paper we study the total sojourn time in a queueing system with feedback. We give the details for M/G/1 queues in which the decision to feedback or not is a Bernoulli process. While the details of the computations can be more difficult, the structure of the sojourn time process is unchanged for the M/G/1 queue with a more general decision process as will be shown. We assume the reader is familiar with Disney, McNickle and Simon [1].     

A queueing system with vacations after N services

This article is devoted to the study of an M/G/1 queue with a particular vacation discipline. The server is due to take a vacation as soon as it has served exactly N customers since the end of the previous vacation. N may be either a constant or a random variable. If the system becomes empty before the server has served N customers, then it stays idle until the next customer arrival. Such a vacation discipline arises, for example, in production systems and in order picking in warehouses. We determine the joint transform of the length of a visit period and the number of customers in the system at the end of that period. We also derive the generating function of the number of customers at a random instant, and the Laplace–Stieltjes transform of the delay of a customer. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 646–658, 2015     

随机环境中的M/MY/1排队系统

文献［４］讨论了随机环境中的Ｍ／Ｍ／１排队模型，本文提出和讨论随机环境中的Ｍ／Ｍｙ／１排队模型，在统计平衡条件下给出了队长和等待队长的平稳分布以及平均队长和平均等待队长，得到了等待时间和逗留时间分布以及平均等待时间和平均逗留时间。     

Transient solution of a finite-capacity M/Ga,b/1 queueing system

In this article we consider a single-server, bulk-service queueing system in which the waiting room is of finite capacity. Arrival process is Poisson and all the arrivals taking place when the waiting room is full are lost. The service times are generally distributed independent random variables and the distribution is depending on the batch size being served. Using renewal theory, we derive the time-dependent solution for the system-size probabilities at arbitrary time points. Also we give expressions for the distribution of virtual waiting time in the queue at any time t.     

A queue with waiting time dependent service times

Sufficient conditions are developed for the ergodicity of a single server, first-come-first-serve queue with waiting time dependent service times.     

Waiting time distributions for transient bulk queues with general vehicle dispatching strategies

A numerical approach is presented for determining the waiting time distribution in a transient bulk-arrival, bulk-service queue. Vehicle departures from the queue are governed by a general dispatch strategy that includes holding with a variable release function and vehicle cancellations. The waiting time distribution of a customer (in a group) arriving at a given point in time is calculated by simulating the process in discrete time and determining at each step the probability the customer has left the system. The dispatch strategies require knowing the total length of the queue as well as the position a customer holds in the queue. An exact approach is compared to an accurate approximation which is 50 to 100 times faster. Comparisons are made with other approaches in the context of steady-state systems.     

Computational analysis of MMAP[K]/PH[K]/1 queues with a mixed FCFS and LCFS service discipline

This paper studies a queueing system with a Markov arrival process with marked arrivals and PH‐distribution service times for each type of customer. Customers (regardless of their types) are served on a mixed first‐come‐first‐served (FCFS) and last‐come‐first‐served (LCFS) nonpreemptive basis. That is, when the queue length is N (a positive integer) or less, customers are served on an FCFS basis; otherwise, customers are served on an LCFS basis. The focus is on the stationary distribution of queue strings, busy periods, and waiting times of individual types of customers. A computational approach is developed for computing the stationary distribution of queue strings, the mean of busy period, and the means and variances of waiting times. The relationship between these performance measures and the threshold number N is analyzed in depth numerically. It is found that the variance of the virtual (actual) waiting time of an arbitrary customer can be reduced by increasing N. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 399–421, 2000     

Customer delays in M/M/c repair systems with spares

A service center to which customers bring failed items for repair is considered. The items are exchangeable in the sense that a customer is ready to take in return for the failed item he brought to the center any good item of the same kind. This exchangeability feature makes it possible for the service center to possess spares. The focus of the article is on customer delay in the system—the time that elapses since the arrival of a customer with a failed item and his departure with a good one—when repaired items are given to waiting customers on a FIFO basis. An algorithm is developed for the computation of the delay distribution when the item repair system operates as an M/M/c queue.     

Allocating capacity in parallel queues to improve their resilience to deliberate attack

We develop models that lend insight into how to design systems that enjoy economies of scale in their operating costs, when those systems will subsequently face disruptions from accidents, acts of nature, or an intentional attack from a well‐informed attacker. The systems are modeled as parallel M/M/1 queues, and the key question is how to allocate service capacity among the queues to make the system resilient to worst‐case disruptions. We formulate this problem as a three‐level sequential game of perfect information between a defender and a hypothetical attacker. The optimal allocation of service capacity to queues depends on the type of attack one is facing. We distinguish between deterministic incremental attacks, where some, but not all, of the capacity of each attacked queue is knocked out, and zero‐one random‐outcome (ZORO) attacks, where the outcome is random and either all capacity at an attacked queue is knocked out or none is. There are differences in the way one should design systems in the face of incremental or ZORO attacks. For incremental attacks it is best to concentrate capacity. For ZORO attacks the optimal allocation is more complex, typically, but not always, involving spreading the service capacity out somewhat among the servers. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011