A comparison of waiting time approximations in series queueing systems

The determination of steady-state characteristics in systems of tandem queues has been left to computer simulation because of the lack of exact solutions in all but the simplest newtorks. In this paper, several methods developed for approximating the average waiting time in single-server queues are extended to systems of queues in series. Three methods, due to Fraker, Page, and Marchal, are compared along with results gathered through GPSS simulation. Various queueing networks with Erlangian service distributions are investigated.     

Discrete‐time analysis of MAP/PH/1 multiclass general preemptive priority queue

We use the matrix‐geometric method to study the MAP/PH/1 general preemptive priority queue with a multiple class of jobs. A procedure for obtaining the block matrices representing the transition matrix P is presented. We show that the special upper triangular structure of the matrix R obtained by Miller [Computation of steady‐state probabilities for M/M/1 priority queues, Oper Res 29(5) (1981), 945–958] can be extended to an upper triangular block structure. Moreover, the subblock matrices of matrix R also have such a structure. With this special structure, we develop a procedure to compute the matrix R. After obtaining the stationary distribution of the system, we study two primary performance indices, namely, the distributions of the number of jobs of each type in the system and their waiting times. Although most of our analysis is carried out for the case of K = 3, the developed approach is general enough to study the other cases (K ≥ 4). © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 662–682, 2003.     

On preservation of classes of life distributions under reliability operations: Some complementary results

A counterexample of general character is constructed showing that the NWUE class is not preserved under mixing. Some general classes of life distributions are introduced and their behavior under mixing and convolution is studied. These classes have a theoretical character but coincide in many cases with well-known classes. It is proved that the DMRL class is not preserved under convolution.     

On a large sample test for the traffic intensity in GI|G|s queue

A large sample test based on normal approximation for the traffic intensity parameter ρ in the cases of single and multiple-server queues has been proposed. The test procedure is developed without imposing steady-state assumptions and is applicable to queueing systems with general interarrival and service-time distributions.     

An approximation for the waiting time distribution in single server queues

Single server queues with general interarrival and service times are approximated by queues with two-point (Bernoulli) interarrival times and exponential service times. The parameters are chosen such that the first four moments of the difference of the service times and interarrival times in the approximating system equal those of the original system. The aptness of the approximation is discussed and some examples are presented comparing the exact and approximate waiting time distributions. A more complicated approximation is presented using the dual system (exponential arrivals, Bernoulli service) for those cases where the original approximation cannot be used.     

A robust queueing network analyzer based on indices of dispersion

We develop a robust queueing network analyzer algorithm to approximate the steady-state performance of a single-class open queueing network of single-server queues with Markovian routing. The algorithm allows nonrenewal external arrival processes, general service-time distributions and customer feedback. The algorithm is based on a decomposition approximation, where each flow is partially characterized by its rate and a continuous function that measures the stochastic variability over time. This function is a scaled version of the variance-time curve, called the index of dispersion for counts (IDC). The required IDC functions for the external arrival processes can be calculated from the model primitives or estimated from data. Approximations for the IDC functions of the internal flows are calculated by solving a set of linear equations. The theoretical basis is provided by heavy-traffic limits for the flows established in our previous papers. A robust queueing technique is used to generate approximations of the mean steady-state performance at each queue from the IDC of the total arrival flow and the service specification at that queue. The algorithm's effectiveness is supported by extensive simulation studies.     

On the behavior and shape of mixture failure rates from a family of IFR Weibull distributions

Populations of many types of component are heterogeneous and often consist of a small number of different subpopulations. This is called a mixture and it arises in a number of situations. For example, a majority of products in industrial populations are mixtures of defective items with shorter lifetimes and standard items with longer lifetimes. It is a well‐known result that distributions with decreasing failure rates are closed under mixture. However, mixtures of distributions with increasing failure rates are not easily classifiable. If the subpopulations involved in the mixture have increasing failure rates, there might be some upward movement in the mixture and later a general downward pull towards the strongest component. Little work has been done in describing the shape of mixture failure rates when all subpopulations do not have decreasing failure rate. In this paper, we present general results that describe the shape and behavior of a failure rate of a mixture obtained from two Weibull subpopulations with strictly increasing failure rates. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

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     

The single server queue in discrete time-numerical analysis I

This is the first of a sequence of papers dealing with the computational aspects of the transient behavior of queues in discrete time It is shown that for a substantial class of queues of practical interest, a wealth of numerical information may be obtained by relatively unsophisticated methods This approach should prove useful in the analysis of unstable queues which operate over a limited time interval, but is by no means limited to such queues Mathematically the service unit is modeled in terms of a multivariate Markov chain, whose particular structure is used in iterative computation. Many important queue features may then be derived from the n-step transition probabilities of this chain.     

Convolutions and generalization of logconcavity: Implications and applications

Additive convolution of unimodal and α‐unimodal random variables are known as an old classic problem which has attracted the attention of many authors in theory and applied fields. Another type of convolution, called multiplicative convolution, is rather younger. In this article, we first focus on this newer concept and obtain several useful results in which the most important ones is that if is logconcave then so are and for some suitable increasing functions ?. This result contains and as two more important special cases. Furthermore, one table including more applied distributions comparing logconcavity of f(x) and and two comprehensive implications charts are provided. Then, these fundamental results are applied to aging properties, existence of moments and several kinds of ordered random variables. Multiplicative strong unimodality in the discrete case is also introduced and its properties are investigated. In the second part of the article, some refinements are made for additive convolutions. A remaining open problem is completed and a conjecture concerning convolution of discrete α‐unimodal distributions is settled. Then, we shall show that an existing result regarding convolution of symmetric discrete unimodal distributions is not correct and an easy alternative proof is presented. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 109–123, 2016     

On queues with state-dependent Erlang service

Some general results are derived for single-channel queues with Poisson input and state-dependent Erlang service times in view of the possible use of this model to approximate arbitrary M/G/1-like state-dependent queues in a manner similar to that suggested by Rosenshine, and by Kendall, and Kotiah, Thompson, and Waugh for the M/G/1. Numerical procedures are indicated for the evaluation of stationary state probabilities, expected system sizes and waiting times, and parameter estimation.     

Note: Minimizing the variability of the waiting times in a globally gated elevator polling system

A polling system comprising n queues and a single server is considered. Service is performed according to an elevator scheme under the globally gated regime. The problem of arranging the channels to minimize a measure of the variability of the waiting times is addressed. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 605–611, 1997     

Matrix-geometric solution of discrete time MAP/PH/1 priority queue

We use the matrix-geometric method to study the discrete time MAP/PH/1 priority queue with two types of jobs. Both preemptive and non-preemptive cases are considered. We show that the structure of the R matrix obtained by Miller for the Birth-Death system can be extended to our Quasi-Birth-Death case. For both preemptive and non-preemptive cases the distributions of the number of jobs of each type in the system are obtained and their waiting times are obtained for the non-preemptive. For the preemptive case we obtain the waiting time distribution for the high priority job and the distribution of the lower priority job's wait before it becomes the leading job of its priority class. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 23–50, 1998     

Renewal processes of phase type

This paper discusses a class of analytically and numerically tractable renewal processes, which generalize the Poisson process. When used to describe interarrival or service times in queues, these renewal processes lead to computationally explicit solutions which involve only real arithmetic. Previous modifications of the Poisson process, based on the Erlang or the hyperexponential distributions, appear as particular cases.     

The effect of correlated exponential service times on single server tandem queues

An investigation via simulation of system performance of two stage queues in series (single server, first-come, first-served) under the assumption of correlated exponential service times indicates that the system's behavior is quite sensitive to departures from the traditional assumption of mutually independent service times, especially at higher utilizations. That service times at the various stages of a tandem queueing system for a given customer should be correlated is intuitively appealing and apparently not at all atypical. Since tandem queues occur frequently, e.g. production lines and the logistics therewith associated, it is incumbent on both the practitioner and the theoretician that they be aware of the marked effects that may be induced by correlated service times. For the case of infinite interstage storage, system performance is improved by positive correlation and impaired by negative correlation. This change in system performance is reversed however for zero interstage storage and depends on the value of the utilization rate for the case where interstage storage equals unity. The effect due to correlation is shown to be statistically significant using spectral analytic techniques. For correlation equal unity and infinite interstage storage, results are provided for two through twenty-five stages in series to suggest how adding stages affects system performance for ρ>0. In this extreme case of correlation, adding stages has an effect on system performance which depends markedly on the utilization rate. Recursive formulae for the waiting time per customer for the cases of zero, one, and infinite interstage storage are derived.     

The effects of information on a queue with balking and phase‐type service times

This article generalizes the models in Guo and Zipkin, who focus on exponential service times, to systems with phase‐type service times. Each arriving customer decides whether to stay or balk based on his expected waiting cost, conditional on the information provided. We show how to compute the throughput and customers' average utility in each case. We then obtain some analytical and numerical results to assess the effect of more or less information. We also show that service‐time variability degrades the system's performance. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

运载器牵制释放结构动力响应数值模拟方法研究

将运载器牵制释放垂直发射的过程依次分为静态、牵制、释放三个阶段.利用MSC.Patran/Nastran的场功能和分组分析功能,将前一个阶段的计算结果场向后一个阶段的初始条件场传递,提出了一种分析运载器牵制释放全过程结构动力响应的分阶段计算新方法.解决了牵制释放过程中由于出现运载器-发射台分离面给结构动力响应计算带来的困难.采用该方法计算了几个运载器牵制释放的算例,分析了牵制阶段牵制力的变化、释放阶段运载器结构动力响应的特点、不同释放时间对结构动力响应的影响.算例表明:该方法实施简便、精度较高,还可拓展用于不同时刻释放、释放不同步、施加缓释力等条件下运载器结构动力响应的分析,为牵制释放系统的研制提供参考.     

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.     

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.     

Shock models with phase type survival and shock resistance

New closure theorems for shock models in reliability theory are presented. If the number of shocks to failure and the times between the arrivals of shocks have probability distributions of phase type, then so has the time to failure. PH-distributions are highly versatile and may be used to model many qualitative features of practical interest. They are also well-suited for algorithmic implementation. The computational aspects of our results are discussed in some detail.