Search

This paper studies the behaviour of a double channel queueing system wherein the arrivals are (i) uncorrelated and (ii) correlated at the two consecutive transition marks; and the intertransition time distribution is exponential.Laplace transforms of the probability generating functions for the queue length are obtained and the steady state results are derived therefrom.

The Laplace-Stieltjes transform of the variance function V ( y ) = var ( N (0, y ]) for the number N (0, y ] of departures in a time interval of length y is found for stationary M/G/1 and G1/M/1 queueing systems. It is shown that for G1/M/1 systems V ( y ) is linear only for M/M/1.

The question of replacing a single-density, two-channel, two-controller disk system with a cheaper, plug-compatible, dual-density, single-channel system having the same capacity is considered. An analytical model is explored to examine the effect of such a replacement on average response time, that is, the time between issuing an I/O request and completion of the request. Queueing theory is used to obtain curves of response time versus arrival rate, and the results are compared with corresponding curves obtained by a simulation model.

This note presents two fairly simple formulae for the approximate evaluation of the average queueing time in the processes M/D/r and D/M/r. The formulae were tested for up to 100 servers; the relative percentage errors incurred are below 1% for most practical purposes. In the case of the process D/M/r, an approximate formula for the queue size distribution is also given.

We derive an expression for the Laplace-Stieltjes transform of the steady-state distribution of the queueing time for the M/G/1 finite capacity queue. The derivation proceeds in terms of a related 2-stage closed cyclic queueing network. The resulting expression is a rational function of the steady-state probabilities of the imbedded Markov chain at departure epochs and of the Laplace-Stieltjes transform of the service time distribution. The expression can be differentiated readily in order to obtain moments of the steady-state queueing time and some numerical results for the mean and coefficient of variation are presented.

Although many queueing processes of various principles have extensively been investigated, little attention has been paid to the sampling aspect of the theory, by which the nature of sample sequences of finite or infinite length can be examined with respect to some given ensemble of queueing sequences. In this paper we wish to identify classes of sample sequences of an M/G/1 model and investigate several hitherto unknown properties of queueing phenomenon of a given particular service system over a finite or infinite length of time. The method to be used is an extension of both the method of imbedded Markow chains, cf. D. G. Kendall [4], and semi-Markovian processes, Smith [9], Levy [5], Pyke[7,8], Fabens [2], Neuts [6], etc.

This paper considers the steady state behaviour of a queueing system in which (i) the input following the Hypergeometric Distribution is in batches of variable size (ii) queue discipline is first come first served it being assumed that the batches are preordered for service purposes and (ii) the service at two consecutive time marks is correlated. Probability generating functions for the various cases have been obtained and the mean queue lengths derived.

For the single server queueing system, whose distributions of service and inter-arrival times have rational Laplace-Stieltjes transforms, limit theorems are derived for the supremum of the virtual waiting time during k successive busy cycles for k→∞. Similarly, for the supremum of the actual waiting times of all customers arriving in k successive busy cycles. Only the cases with the load of the system less than one and equal to one are considered. The limit distributions are extreme value distributions. The results are obtained by first deriving a number of asymptotic expressions for the quantities which govern the analytic description of the system Km/Kn/1. Using these asymptotic relations limit theorems for entrance times can also be obtained, a few examples are given.

This paper deals with the analysis of a queueing process involving two classes of customers where the arrival mechanism of each class is subject to a particular control doctrine based on the queue length. Expressions are obtained for the equilibrium distribution of the queue length, the expected queue length and other characteristics which measure the effectiveness of the control doctrine.

The model considered in this paper describes a queueing system in which the station is dismantled at the end of a busy period and re-established on arrival of a new customer, in such a way that the closing-down process consists of N1 phases of random duration and that a customer 𝒞n who arrives while the station is being closed down must wait a random time idn(i = 1, ···, N1) if the ith phase is going on at the arrival instant. (For each fixed index i, the random variables idn are identically distributed.) A customer 𝒞n arriving when the closing-down of the station is already accomplished has to wait a random time (N1 + 1)dn corresponding to the set up time of the station. Besides, a customer 𝒞n who arrives when the station is busy has to wait an additional random time 0dn. We thus have (N1 + 2) types of “delay” (additional waiting time). Similarly, we consider (N2 + 2) types of service time and (N3 + 2) probabilities of joining the queue. This may be formulated as a model with (N + 2) types of triplets (delay, service time, probability of joining the queue). We consider the general case where the random variables defining the model all have an arbitrary distribution.The process {wn}, where wn denotes the waiting time of customer 𝒞n if he joins the queue at all, is not necessarily Markovian, so that we first study (by algebraic considerations) the transient behaviour of a Markovian process {vn} related to {wn}, and then derive the distribution of the variables wn.

Customers arriving randomly are served by a queueing system consisting of a sequence of two service stations with infinite queue allowable before the first station and no queue allowable between the stations. The moment generating functions of the steady-state queueing times as well as the generating functions of the steady-state numbers of customers in the various parts of the system are obtained under assumptions of Poisson process of arrivals and arbitrarily distributed service times at both stations. The cases of regular and exponential service times are investigated in some more detail, and the results obtained are extended to include the queueing system with a sequence of two stations with a finite intermediate queue allowable between them, infinite queue allowed before the first station, Poisson process of arrivals and regular service times at both stations.

The time dependent behaviour of the two server queueing system with recurrent input and negative exponential service times is studied here using certain recurrence relations for the underlying queuelength process. The service times have a varying mean depending on the number of busy servers.

This paper considers the behaviour of a queueing system wherein (i) the arrivals are correlated at the two consecutive transition marks, (ii) a certain service time distribution is given and (iii) the capacity of the service channel is a stochastic variable. The Laplace transform of the distribution function for the queue length is obtained. Finally, some particular cases are discussed.

This paper presents results for queueing systems that are characterized by poisson arrival epochs with x (a random variable) arrivals at each epoch, exponential service times and c servers. The steady state probabilities, the probability of blocking (not being served immediately) for both loss and delay systems are investigated. In addition, the average delay, the variance of the delay and the delay distribution for first-come-served by batches and arbitrary order of service within batches are presented.

(This article originally appeared in Management Science, November 1963, Volume 10, Number 1, pp. 131–142, published by The Institute of Management Sciences.) The equilibrium joint probability distribution of queue lengths is obtained for a broad class of jobshop-like “networks of waiting lines,” where the mean arrival rate of customers depends almost arbitrarily upon the number already present, and the mean service rate at each service center depends almost arbitrarily upon the queue length there. This extension of the author's earlier work is motivated by the observation that real production systems are usually subject to influences which make for increased stability by tending, as the amount of work-in-process grows, to reduce the rate at which new work is injected or to increase the rate at which processing takes place.

If we think of the input to a queueing system as arising from some process and depending on the history of that process, we might well expect the duration of inter-arrival intervals to depend mostly on the recent history and to a much smaller extent on that which is more remote.

We consider two models, the GI/M/s queue and the M/G/1 queue, in which waiting customers are served in random order. For each model we derive expressions for the calculation of the stationary waiting-time distribution function. Our methods differ from those of previous authors in that we do not use transforms, and consequently our results may be better suited for calculation. We illustrate our methods by deriving previously known results for the M/M/s and M/D/1 random-service queues, and by making sample calculations for the M/Ek/1 random-service queue for various values of the utilization factor and the index k.

Burke [Burke, P. J. 1956. The output of a queueing system. Oper. Res. 4 699–704.] showed that the departure process from an M/M/1 queue with infinite capacity was in fact a Poisson process. Using methods from semi-Markov process theory, this paper extends this result by determining that the departure process from an M/G/1 queue is a renewal process if and only if the queue is in steady state and one of the following four conditions holds: (1) the queue is the null queue—the service times are all 0; (2) the queue has capacity (excluding the server) 0; (3) the queue has capacity 1 and the service times are constant (deterministic); or (4) the queue has infinite capacity and the service times are negatively exponentially distributed (M/M/1/∞ queue).

A set of formulas relating two random variables is developed. With these results, the branch parameters of GERT network models for reliability and queueing problems can be calculated. Two examples illustrating the technique are presented. The basic results can be applied to a variety of queueing problems of the M/G/1 and G/M/1 type.

In this paper a renewal type equation for the probability that the counter is idle at a given time (when there is an arrival initially) is obtained and its solution is explicitly determined for the GI/M/1 queues. The solution for M/Ek/1 queues is studied in detail. Queues with zero initial load are also discussed.

The waiting-time distribution for an M/G/1 queue with last-come-first-served discipline has a simple structure that may be found from an argument based on the Takács server backlog process. This structure provides real-time information in a convenient form.

Consider a queueing system GI/G/∞ in which (i) the inter-arrival times are distributed with distribution function A(t) (A(O +) = 0) (ii) the service times have distribution function B(t) such that the expected value of the service time is β(>∞).

Consider a queueing system M/G/s with the arrival intensity λ, the service time distribution function B(t) (B(0) < 1) having a finite mean and the waiting room size N ≤ ∞. If s < ∞ and N = ∞, we shall also assume that its relative traffic intensity is less than 1. Since the arrival process of this system is Poisson, it is immediate that in this case the distribution of the number of arrivals during an interval is infinitely divisible.

The problem of controlling M/M/c queueing systems with c = or 1 is considered. By providing a new definition of the time of transition, we enlarge the standard set of decision epochs, and obtain a preferred version of the n- period problem in which the times between transitions are exponential random variables with constant parameter. Using this new technique, we are able to use the inductive approach in a manner characteristic of inventory theory. The efficacy of the approach is then demonstrated by successfully finding the form of an optimal policy for four quite distinct models that have appeared in the literature; namely, those of (i) McGill, (ii) Miller-Cramer, (iii) Crabill-Sabeti, and (iv) Low. Of particular note, one analysis establishes that an (s, S) or control-limit policy is optimal for an M/M/c queue with switching costs and removable servers.

The finite capacity of storage has a significant effect on the performance of a contemporary computer system. Yet it is difficult to formulate this problem and analyze it by existing queueing network models. We present an analysis of an open queueing model with two servers in series in which the second server has finite storage capacity. This network is an exponential service system; the arrival of requests into the system is modeled by a Poisson process (of rate λ) and service times in each stage are exponentially distributed (with rates α and β respectively). Requests are served in each stage according to the order of their arrival. The principal characteristic of the service in this network is blocking ; when M requests are queued or in service in the second stage, the server in the first stage is blocked and ceases to offer service. Service resumes in the first stage when the queue length in the second stage falls to M-1. Neuts [1] has studied two-stage blocking networks (without feedback) under more general statistical hypothesis than ours. Our goal is to provide an algorithmic solution which may be more accessible to engineers.

Mathematical models based on queueing theory are widely used in the analysis of computer system performance. As in the case of other engineering disciplines, these models never correspond exactly to the real systems they are intended to represent. However, if the associated error terms are sufficiently small the models can still serve as valuable tools for estimating performance levels in specific cases and for studying the factors which influence overall system behavior. In this paper we examine some error terms which arise when the familiar M/G/1 queueing model is used to predict expected response times and queue lengths in systems which contain only a finite number of sources.

A queueing system can be regarded as transforming one point process into another (as pointed out for example in Kendall (1964), Section 6), namely, the input or arrival process with inter-arrival intervals $\{T_n\}$ is acted on by a system comprised of a queue discipline and a service (or, delay) mechanism, producing the output or departure process with inter-departure intervals $\{D_n\}$. The object of this paper is to study the correlation structure of the sequence $\{D_n\}$ (and this sequence we shall for convenience call the output process of the system) when the input process is a renewal process and when the service times $\{S_n\}$ (assumed to be independently and identically distributed, and independent of the input process) are such that the system can and does exist in its stationary state. In particular, we shall be concerned with conditions under which the process $\{D_n\}$ is uncorrelated, by which we mean that $\operatorname{cov} (D_0, D_n) = E(D_0D_n) - (E(D_0))^2 = 0 (n = 1,2, \cdots)$. Schematically then, we study the mapping $\{T_n\} \overset{\{ S_n\}/1}{\longrightarrow} \{D_n\}$, and as consequences of the formal theorems of the paper the following statements can be justified $(T, S$, and $D$ denote typical members of $\{T_n\}, \{S_n\}$ and $\{D_n\})$. (i) $\operatorname{var} (D) \geqq \operatorname{var} (S)$, with equality only in the trivial case where both $\{T_n\}$ and $\{S_n\}$ are deterministic. (ii) Locally, the mapping can be made any of variance increasing, variance preserving, or variance decreasing (that is, all cases of $\operatorname{var} (D) >, =, < \operatorname{var} (T)$ are possible) by appropriate choice of $\{T_n\}$ and $\{S_n\}$. Globally however, the mapping is variance preserving, that is, $\operatorname{var} (D_1 + \cdots + D_n)/\operatorname{var} (T_1 + \cdots + T_n) \rightarrow 1\quad (n \rightarrow \infty)$. (iii) When $\{T_n\}$ is a Poisson process, the process $\{D_n\}$ is uncorrelated if and only if it is a Poisson process (and this occurs if and only if the $\{S_n\}$ are negative exponential). (iv) When the $\{S_n\}$ are negative exponential, $\{D_n\}$ is a renewal process if and only if it is a Poisson process (and this occurs if and only if $\{T_n\}$ is a Poisson process). However (cf. (iii)) $\{D_n\}$ can be uncorrelated without being a renewal process. If the $\{D_n\}$ are correlated then the terms $\operatorname{cov} (D_0, D_n)$ are of the same sign for all $n = 1,2, \cdots$ and converge to zero monotonically. (v) There exist $\{T_n\}$ and $\{S_n\}$ such that the serial covariances $\operatorname{cov} (D_0, D_n)$ are not of the same sign for all $n = 1,2, \cdots$ (see remark after Theorem 7).

The solution of separable closed queueing networks requires the evaluation of homogeneous multinomial expressions. The number of terms in those expressions grows combinatorially with the size of the network such that a direct summation may become impractical. An algorithm is given which does not show a combinatorial operation count. The algorithm is based on a generalization of Horner's rule for polynomials. It is also shown how mean queue size and throughput can be obtained at negligible extra cost once the normalization constant is evaluated.

The steady-state parameters of the bulk input queue Dc/M/1 and the Erlang service queue D/Ec/1 have been tabulated for C = 1(1)6(2)12(4)20 and 25, 50 and 100 and for ρ = 0·1(0·1)0·9. The tabulation includes the mean waiting time, idle time and queue size. In addition the queue D/Ec/1 has been compared with the queue M/Ec/1 to indicate the gains to be achieved by regularizing the arrival mechanism for a given Ec service facility.