Approximating the Mean Waiting Time in the <Emphasis Type="Italic">GI/G/s</Emphasis> Queue

We provide two distribution-dependent approximations for the mean waiting time in a GI/G/s queue. Both approximations are weighted combinations of the exact mean waiting times for the GI/M/s and M/D/s queues each of which has the same mean service time and traffic intensity as in the approximating GI/G/s queue. The weights in the approximations are expressed by the service-time c.d.f. and the first two moments of interarrival and service times. To examine the performance of our approximations, they are numerically compared with exact solutions and previous two-moment approximations for various cases. Extensive numerical comparisons indicate that the relative percentage errors of the approximations are of the order of 5% in moderate traffic and 1% in heavy traffic, except for extreme cases.     

A single-server queue with batch arrivals and semi-Markov services

We investigate the transient and stationary queue length distributions of a class of service systems with correlated service times. The classical \(M^X/G/1\) queue with semi-Markov service times is the most prominent example in this class and serves as a vehicle to display our results. The sequence of service times is governed by a modulating process J(t). The state of \(J(\cdot )\) at a service initiation time determines the joint distribution of the subsequent service duration and the state of \(J(\cdot )\) at the next service initiation. Several earlier works have imposed technical conditions, on the zeros of a matrix determinant arising in the analysis, that are required in the computation of the stationary queue length probabilities. The imposed conditions in several of these articles are difficult or impossible to verify. Without such assumptions, we determine both the transient and the steady-state joint distribution of the number of customers immediately after a departure and the state of the process J(t) at the start of the next service. We numerically investigate how the mean queue length is affected by variability in the number of customers that arrive during a single service time. Our main observations here are that increasing variability may reduce the mean queue length, and that the Markovian dependence of service times can lead to large queue lengths, even if the system is not in heavy traffic.     

Log-Convexity of Counting Processes Evaluated at a Random end of Observation Time with Applications to Queueing Models

We consider a counting processes with independent inter-arrival times evaluated at a random end of observation time T, independent of the process. For instance, this situation can arise in a queueing model when we evaluate the number of arrivals after a random period which can depend on the process of service times. Provided that T has log-convex density, we give conditions for the inter-arrival times in the counting process so that the observed number of arrivals inherits this property. For exponential inter-arrival times (pure-birth processes) we provide necessary and sufficient conditions. As an application, we give conditions such that the stationary number of customers waiting in a queue is a log-convex random variable. We also study bounds in the approximation of log-convex discrete random variables by a geometric distribution.     

On the Relative Waiting Times in the GI/M/s and the GI/M/1 Queueing Systems

The expected steady-state waiting time, Wq(s), in a GI/M/s system with interarrival-time distribution H(·) is compared with the mean waiting time, Wq, in an "equivalent" system comprised of s separate GI/M/1 queues each fed by an interarrival-time distribution G(·) with mean arrival rate equal to 1/s times that of H(·). For H(·) assumed to be Exponential, Gamma or Deterministic three possible relationships between H(·) and G(·) are considered: G(·) can be of the "same type" as H(·); G(·) can be derived from H(·) by assigning new arrivals to the individual channels in a cyclic order; and G(·) may be obtained from H(·) by assigning customers probabilistically to the different queues. The limiting behaviour of the ratio R = Wq/Wq(s) is studied for the extreme values (1 and 0) of the common traffic intensity, ρ. Closed form results, which depend on the forms of H(·) and G(·) and on the relationships between them, are derived. It is shown that Wq is greater than Wq(s) by a factor of at least (s + 1)/2 when ρ approaches one, and that R is at least s(s!) when ρ tends to zero. In the latter case, however, R goes to infinity (!) in most cases treated. The results may be used to evaluate the effect on the waiting times when, for certain (non-queueing) reasons, it is needed to partition a group of s servers into several small groups.     

Refining Cosmetatos' Approximation for the Mean Waiting Time in the M/D/s Queue

This paper deals with refining Cosmetatos's approximation for the mean waiting time in an M/D/s queue. Although his approximation performs quite well in heavy traffic, it overestimates the true value when the number of servers is large or the traffic is light. We first focus on a normalized quantity that is a ratio of the mean waiting times for the M/D/s and M/M/s queues. Using some asymptotic properties of the quantity, we modify Cosmetatos's approximation to obtain better accuracy both for large s and in light traffic. To see the quality of our approximation, we compare it with the exact value and some previous approximations. Extensive numerical tests indicate that the relative percentage error is less than 1% for almost all cases with s ≤ 20 and at most 5% for other cases.     

Simulation of a random fuzzy queuing system with multiple servers

The paper considers a queuing system that has k servers and its interarrival times and service times are random fuzzy variables.We obtain a theorem concerning the average chance of the event “r servers (r ≤ k) are busy at time t”, provided that all the servers work independently. We simulate the average chance using fuzzy simulation method and obtain some results on the number of servers that are busy. Some examples to illustrate the simulation procedure are also presented.     

A discrete queue with double thresholds policy and its application to SVC systems

A discrete time Geo/Geo/1 queue with (m, N)-policy is considered in this paper. There are three operation periods being considered: high speed, low speed service periods and idle periods. With double thresholds policy, the server begins to take a working vacation when the number of customers is below m after a service and there is one customer in the system at least. What’s more, if the system becomes empty after a service, the server will take an ordinary vacation. Otherwise, high speed service continues if the number of customers still exceeds m after a service. At the vacation completion instant, servers resume their service if the quantity of customers exceeds N. Vacations can also be interrupted when the system accumulate customers more than the prefixed threshold. Using the quasi birth-death process and matrix-geometric solution methods, we derive the stationary queue length distribution and some system characteristics of interest. Based on these, we apply the queue to a virtual channel switching system and present various numerical experiments for the system. Finally, numerical results are offered to illustrate the optimal (m, N)-policy to minimize cost function and obtain practical consequence on the operation of double thresholds policy.     

Approximating the Distribution of Customers in <Emphasis Type="Italic">M/E</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript><Emphasis Type="Italic">/s</Emphasis> Queues

Approximation formulae are suggested for the mean and variance of customers in M/E _n /s queues. It is shown that the distributions can be approximated by using the mean and variance to fit Gamma functions. A brief comment on the more general E _m /E _n /s case is given.     

Analysis of queues in a random environment with impatient customers

We study M/M/c queues (c = 1, 1 < c < ∞ and c = ∞) in a Markovian environment with impatient customers. The arrivals and service rates are modulated by the underlying continuous-time Markov chain. When the external environment operates in phase 2, customers become impatient. We focus our attention on the explicit expressions of the performance measures. For each case of c, the corresponding probability generating function and mean queue size are obtained. Several special cases are studied and numerical experiments are presented.     

On the Diophantine Queueing System, <Emphasis Type="Italic">D/D</Emphasis><Superscript><Emphasis Type="Italic">a,b</Emphasis></Superscript><Emphasis Type="Italic">/</Emphasis>1

This paper considers the solution of a deterministic queueing system. In this system, the single server provides service in bulk with a threshold for the acceptance of customers into service. Analytic results are given for the steady-state probabilities of the number of customers in the system and in the queue for random and pre-arrival epochs. The solution of this system is a prerequisite to a four-point approximation to the model GI/G ^a,b /1. The paper demonstrates that the solution of such a system is not a trivial problem and can produce interesting results. The graphical solution discussed in the literature requires that the traffic intensity be a rational number. The results so generated may be misleading in practice when a control policy is imposed, even when the probability distributions for the interarrival and service times are both deterministic.     

Methods for Determining the Re-order Point of an (<Emphasis Type="Italic">s</Emphasis>, <Emphasis Type="Italic">S</Emphasis>) Ordering Policy when a Service Level is Specified

This paper deals with a periodic review inventory system. Methods are discussed for determining the re-order point s of an (s, S) order policy, when a certain service level is required. The results differ from those presented for a (Q, s) model which is usually considered in literature and implemented in practice. Methods are discussed for determining the re-order point of an (s, S) policy when demand is normal or gamma distributed. A numerical investigation demonstrates the applicability of the described methods. In particular, it is shown that these methods are superior to a formula that is implemented in many inventory control systems.     

Heavy traffic limit for a tandem queue with identical service times

We consider a two-node tandem queueing network in which the upstream queue is M/G/1 and each job reuses its upstream service requirement when moving to the downstream queue. Both servers employ the first-in-first-out policy. We investigate the amount of work in the second queue at certain embedded arrival time points, namely when the upstream queue has just emptied. We focus on the case of infinite-variance service times and obtain a heavy traffic process limit for the embedded Markov chain.     

Periodic review inventory systems with a service level criterion

Full-cost inventory models are mostly studied in the literature, whereas service level constraints are more common to be observed in practical settings. In this paper, we consider periodic review inventory systems with service level restrictions. The control of such inventory systems is limited to (s, S)-type policies in the literature. To the best of our knowledge, we are the first authors to compare such policies with optimal replenishment policies, and illustrate an average cost difference of 0.64%. This justifies the use of these popular (s, S) policies in practice. Furthermore, we propose a new one-dimensional search procedure that is bounded to set the reorder level s and order-up-to level S, whereas the solution space is unbounded and two dimensional. Our heuristic procedure is guaranteed to satisfy the service level constraint and numerical experiments illustrate that it results in an average cost deviation of 1–2% compared with the best (s, S) policy. Consequently, it significantly outperforms all existing procedures from literature, both in service and costs.     

Many-server Gaussian limits for overloaded non-Markovian queues with customer abandonment

Extending Ward Whitt’s pioneering work “Fluid Models for Multiserver Queues with Abandonments, Operations Research, 54(1) 37–54, 2006,” this paper establishes a many-server heavy-traffic functional central limit theorem for the overloaded \(G{/}GI{/}n+GI\) queue with stationary arrivals, nonexponential service times, n identical servers, and nonexponential patience times. Process-level convergence to non-Markovian Gaussian limits is established as the number of servers goes to infinity for key performance processes such as the waiting times, queue length, abandonment and departure processes. Analytic formulas are developed to characterize the distributions of these Gaussian limits.     

A discrete version of the Mishou theorem. II

In 2007, H. Mishou obtained a joint universality theorem for the Riemann zetafunction ζ(s) and the Hurwitz zeta-function ζ(s, α) with transcendental parameter α. The theorem states that a pair of analytic functions can be simultaneously approximated by the shifts ζ(s + iτ ) and ζ(s + iτ, α), τ ∈ R. In 2015, E. Buivydas and the author established a version of this theorem in which the approximation is performed by the discrete shifts ζ(s + ikh) and ζ(s + ikh, α), h > 0, k = 0, 1, 2.... In the present study, we prove joint universality for the functions ζ(s) and ζ(s, α) in the sense of approximation of a pair of analytic functions by the shifts ζ(s + ik ^β h) and ζ(s + ik ^β h, α) with fixed 0 < β < 1.     

The <Emphasis Type="Italic">M/G/k</Emphasis> Blocking System with Heterogeneous Servers

This paper considers the M/G/k blocking system under the assumption of servers whose service time distributions differ. Such a system has k servers each with a (possibly) different service time distribution, whose customers arrive in accordance with a Poisson process. They are served, unless all the servers are occupied. In this case they leave and do not return later (i.e. they are "blocked"). A generalization of the Erlang B-formula is given and it is shown that the latter is valid in the case of heterogeneous servers too, provided that all servers have equal mean service times. In the form of an appendix, the Engset formula also is generalized under the above assumption.     

A Priority Tandem Queue with No Intermediate Buffer

Priority queues are important in modelling and analysis of manufacturing systems, and computer and communication networks. In this paper, a priority tandem queueing system with two stations in series is studied. There is no intermediate buffer between the two stations, and the lack of buffers may cause blocking at the first station. K types of customers arrive at the system according to Poisson processes. The expected delay in the system for each type of customer is obtained when all the customers have the same service time distribution at the second station. Two cases are studied in detail when service times are either all exponentially distributed or all deterministic.     

Analysis of a Multivariate Claim Process

The first part of this paper introduces a class of discrete multivariate phase-type (MPH) distributions. Recursive formulas are found for joint probabilities. Explicit expressions are obtained for means, variances and co-variances. The discrete MPH-distributions are used in the second part of the paper to study multivariate insurance claim processes in risk analysis, where claims may arrive in batches, the arrivals of different types of batches may be correlated and the amounts of different types of claims in a batch may be dependent. Under certain conditions, it is shown that the total amounts of claims accumulated in some random time horizon are discrete MPH random vectors. Matrix-representations of the discrete MPH-distributions are constructed explicitly. Efficient computational methods are developed for computing risk measures of the total claims of different types of claim batches and individual types of claims (e.g., joint distribution, mean, variance, correlation and value at risk.)     

Graphic sequences and split graphs

The split graph K _rVK _s on r+s vertices is denoted by S _r,s. A graphic sequence π = (d ₁, d ₂, ···, d _n) is said to be potentially S _r,s-graphic if there is a realization of π containing S _r,s as a subgraph. In this paper, a simple sufficient condition for π to be potentially S _r,s-graphic is obtained, which extends an analogous condition for p to be potentially K _r+1-graphic due to Yin and Li (Discrete Math. 301 (2005) 218–227). As an application of this condition, we further determine the values of σ(S _r,s, n) for n ≥ 3r + 3s - 1.     

Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic

It was proved that the complexity of square root computation in the Galois field GF(3^s), s = 2^kr, is equal to O(M(2^k)M(r)k + M(r) log₂r) + 2^kkr^1+o(1), where M (n) is the complexity of multiplication of polynomials of degree n over fields of characteristics 3. The complexity of multiplication and division in the field GF(3^s) is equal to O(M(2^k)M(r)) and O(M(2^k)M(r)) + r^1+o(1), respectively. If the basis in the field GF(3^r) is determined by an irreducible binomial over GF(3) or is an optimal normal basis, then the summands 2^kkr^1+o(1) and r^1+o(1) can be omitted. For M(n) one may take n log₂nψ(n) where ψ(n) grows slower than any iteration of the logarithm. If k grow and r is fixed, than all the estimates presented here have the form O_r (M (s) log ₂s) = s (log ₂s)²ψ(s).