Waiting Time Variability in some Single-Server Queueing Systems

This paper considers the range of values of the coefficient of variation of waiting time in some general single-server queueing systems. It is shown that in M/G/1 systems with given ρ, the square of this coefficient increases linearly with m₁m₃/m²₂, where m_i is the ith moment of the service distribution. This implies always a lower bound, and for some widely used distributions an upper bound as well. A few ranges are illustrated and compared to those implied in two GI/M/1 systems. The usefulness of knowing such ranges for modelling purposes is explained.     

The M/M/1 queue with inventory, lost sale, and general lead times

We consider an M/M/1 queueing system with inventory under the $(r,Q)$ policy and with lost sales, in which demands occur according to a Poisson process and service times are exponentially distributed. All arriving customers during stockout are lost. We derive the stationary distributions of the joint queue length (number of customers in the system) and on-hand inventory when lead times are random variables and can take various distributions. The derived stationary distributions are used to formulate long-run average performance measures and cost functions in some numerical examples.     

A two-class global FCFS discrete-time queueing model with arbitrary-length constant service times

We analyze a discrete-time queueing model where two types of customers, each having their own dedicated server, are accommodated in one single FCFS queue. Service times are deterministically equal to \(s \ge 1\) time slots each. New customers enter the system according to a general independent arrival process, but the types of consecutive customers may be nonindependent. As a result, arriving customers may (or may not) have the tendency to cluster according to their types, which may lead to more (or less) blocking of one type by the opposite type. The paper reveals the impact of this blocking phenomenon on the achievable throughput, the (average) system content, the (average) customer delay and the (average) unfinished work. The paper extends the results of earlier work where either the service times were assumed to be constant and equal to 1 slot each, or the customers all belonged to the same class. Our results show that, in case of Poisson arrivals, for given traffic intensity, the system-content distribution is insensitive to the length (s) of the service times, but the (mean) delay and the (mean) unfinished work in the system are not. In case of bursty arrivals, we find that all the performance measures are affected by the length (s) of the service times, for given traffic intensity.     

Delay of Social Search on Small-World Graphs

This article introduces an analytical framework for two small-world network models and studies the delay of targeted social search by considering messages traveling between source and target individuals in these networks. In particular, by considering graphs constructed on different network domains, such as rectangular, circular, and spherical network domains, analytical solutions for the average social search delay and the delay distribution are obtained as functions of source–target separation, distribution of the number of long-range connections and geometrical properties of network domains. Derived analytical formulas are first verified by agent-based simulations and then compared with empirical observations in small-world experiments. These formulas indicate that individuals tend to communicate with one another only through their short-range contacts and the average social search delay rises linearly, when the separation between the source and target is small. As this separation increases long-range connections are more commonly used, and the average social search delay rapidly saturates to a constant value and stays almost the same for all large values of the separation. These results do not require the dimensionality of the social space to be identical to the decay exponent of long-range social connections and are qualitatively consistent with experimental observations made by Travers and Milgram in 1969 Travers , J. , &; Milgram , S. ( 1969 ). An experimental study of the small world problem . Sociometry , 32 , 425 – 443 .[Crossref] , [Google Scholar] as well as by others. Moreover, analytical distributions for the delay of social search predicted by the models introduced in this article are also compared with corresponding empirical distributions, and good statistical matches between them are observed. Other somewhat surprising conclusions of the article are that hubs have limited effect in reducing the delay of social search and variation in node degree distribution adversely affects this delay.     

A product form solution to a system with multi-type jobs and multi-type servers

We consider a memoryless single station service system with servers \(\mathcal{S}=\{m_{1},\ldots,m_{K}\}\), and with job types \(\mathcal{C}=\{a,b,\ldots\}\). Service is skill-based, so that server m _i can serve a subset of job types \(\mathcal{C}(m_{i})\). Waiting jobs are served on a first-come-first-served basis, while arriving jobs that find several idle servers are assigned to a feasible server randomly. We show that there exist assignment probabilities under which the system has a product-form stationary distribution, and obtain explicit expressions for it. We also derive waiting time distributions in steady state.     

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.     

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

This paper studies the equilibrium behaviour of the generalized M/G/k blocking system with heterogeneous servers. Such a service 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 they do not return later (i.e. they are ‘blocked’). Whenever there are n (n = 0, 1, 2,..., k) servers occupied, each arriving customer balks with probability 1 - f _{n +1}(f _{k +1} = 0) and each server works at a rate g _n . Among other things, a generalization of the Erlang B-formula is given and also it is shown that the equilibrium departure process from the system is Poisson.     

A Delay Dependent Queue without Pre-emption with General Linearly Increasing Priority Function

This paper considers the delay dependent priority queueing discipline with P non-preemptive priority classes. The priority at time t of a customer from the pth priority class, who arrives at time T_p, is given by q_p(t) = a _p + b _p (t - T _p ). The result has been derived for the expected waiting time of a customer from the pth priority class.     

A Predictive Model for the Police Response Function

The expected response time to a call for service (CFS) for a given configuration of police beats is developed. The effect of downtime calls on the response time to a CFS is determined. Consideration is given to both travel time and waiting time. Travel time and service time distributions are isolated. The model is valid for Poisson arrivals and arbitrary service time distributions. A probabilistic assignment policy is determined for each beat. The fraction of incoming calls arriving in beat k answered by unit l is obtained. Pre-emptive priorities are allowed. Application to the Aurora, Illinois, Police Department is shown.     

Optimal Flow Control of a G/G/c Finite Capacity Queue

The optimal flow control of a G/G/c finite capacity queue is investigated by approximating the general (G-type) distributions by a maximum entropy model with known first two moments. The flow-control mechanism maximizing the throughput, under a bounded time-delay criterion, is shown to be of window type (bang-bang control). The optimal input rate and the maximum number of packets in the system (i.e. sliding window size) are derived in terms of the maximum input rate and the second moment of the interinput time, the maximum allowed average time delay, the first two moments of the service times and the number of servers. Moreover, the relationship between the maximum throughput and maximum time delay is determined. Numerical examples provide useful information on how critically the optimal throughput is affected by the distributional form of the input and service patterns and the finite capacity of the queue.     

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.     

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.     

Asymptotic independence of queues under randomized load balancing

Randomized load balancing greatly improves the sharing of resources while being simple to implement. In one such model, jobs arrive according to a rate-??N Poisson process, with ??<1, in a system of N rate-1 exponential server queues. In Vvedenskaya et al. (Probl. Inf. Transm. 32:15?C29, 1996), it was shown that when each arriving job is assigned to the shortest of D, D??2, randomly chosen queues, the equilibrium queue sizes decay doubly exponentially in the limit as N????. This is a substantial improvement over the case D=1, where queue sizes decay exponentially. The reasoning in Vvedenskaya et al. (Probl. Inf. Transm. 32:15?C29, 1996) does not easily generalize to jobs with nonexponential service time distributions. A?modularized program for treating randomized load balancing problems with general service time distributions was introduced in Bramson et al. (Proc. ACM SIGMETRICS, pp.?275?C286, 2010). The program relies on an ansatz that asserts that, for a randomized load balancing scheme in equilibrium, any fixed number of queues become independent of one another as N????. This allows computation of queue size distributions and other performance measures of interest. In this article, we demonstrate the ansatz in several settings. We consider the least loaded balancing problem, where an arriving job is assigned to the queue with the smallest workload. We also consider the more difficult problem, where an arriving job is assigned to the queue with the fewest jobs, and demonstrate the ansatz when the service discipline is FIFO and the service time distribution has a decreasing hazard rate. Last, we show the ansatz always holds for a sufficiently small arrival rate, as long as the service distribution has 2 moments.     

Epidemic spreading with time delay on complex networks

In this paper, we propose a susceptible-infected-susceptible (SIS) model on complex networks, small-world (WS) networks and scale-free (SF) networks, to study the epidemic spreading behavior with time delay which is added into the infected phase. Considering the uniform delay, the basic reproduction number R ₀ on WS networks and \(\bar R_0\) on SF networks are obtained respectively. On WS networks, if R ₀ ≤ 1, there is a disease-free equilibrium and it is locally asymptotically stable; if R ₀ > 1, there is an epidemic equilibrium and it is locally asymptotically stable. On SF networks, if \(\bar R_0 \leqslant 1\), there is a disease-free equilibrium; if \(\bar R_0 > 1\), there is an epidemic equilibrium. Finally, we carry out simulations to verify the conclusions and analyze the effect of the time delay τ, the effective rate λ, average connectivity 〈k〉 and the minimum connectivity m on the epidemic spreading.     

Geo/Geo/1 retrial queue with non-persistent customers and working vacations

In this paper, we consider a Geo/Geo/1 retrial queue with non-persistent customers and working vacations. The server works at a lower service rate in a working vacation period. Assume that the customers waiting in the orbit request for service with a constant retrial rate, if the arriving retrial customer finds the server busy, the customer will go back to the orbit with probability q (0≤q≤1), or depart from the system immediately with probability $\bar{q}=1-q$ . Based on the necessary and sufficient condition for the system to be stable, we develop the recursive formulae for the stationary distribution by using matrix-geometric solution method. Furthermore, some performance measures of the system are calculated and an average cost function is also given. We finally illustrate the effect of the parameters on the performance measures by some numerical examples.     

Parameter Estimation of Discrete Multivariate Phase-Type Distributions

This paper considers parameter estimation of a class of discrete multi-variate phase-type distributions (DMPH). Such discrete phase-type distributions are based on discrete Markov chains with marked transitions introduced by He and Neuts (Stoch Process Appl 74(1):37–52, 1998) and is a generalization of the discrete univariate phase–type distributions. Properties of the DMPHs are presented. An EM-algorithm is developed for estimating the parameters for DMPHs. A number of numerical examples are provided to address some interesting parameter selection issues and to show possible applications of DMPHs.     

Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers

The model is a service system, consisting of several large server pools. A server’s processing speed and buffer size (which may be finite or infinite) depend on the pool. The input flow of customers is split equally among a fixed number of routers, which must assign customers to the servers immediately upon arrival. We consider an asymptotic regime in which the total customer arrival rate and pool sizes scale to infinity simultaneously, in proportion to a scaling parameter n, while the number of routers remains fixed. We define and study a multi-router generalization of the pull-based customer assignment (routing) algorithm PULL, introduced in Stolyar (Queueing Syst 80(4): 341–361, 2015) for the single-router model. Under the PULL algorithm, when a server becomes idle it sends a “pull-message” to a randomly uniformly selected router; each router operates independently—it assigns an arriving customer to a server according to a randomly uniformly chosen available (at this router) pull-message, if there is any, or to a randomly uniformly selected server in the entire system otherwise. Under Markov assumptions (Poisson arrival process and independent exponentially distributed service requirements), and under subcritical system load, we prove asymptotic optimality of PULL: as \(n\rightarrow \infty \), the steady-state probability of an arriving customer experiencing blocking or waiting vanishes. Furthermore, PULL has an extremely low router–server message exchange rate of one message per customer. These results generalize some of the single-router results in Stolyar (2015).     

Screen Pseudo-Slant Lightlike Submanifolds of Indefinite Sasakian Manifolds

In this paper, we introduce the notion of screen pseudo-slant lightlike submanifolds of indefinite Sasakian manifolds giving characterization theorem with some non-trivial examples of such submanifolds. Integrability conditions of distributions D ₁, D ₂ and RadTM on screen pseudo-slant lightlike submanifolds of indefinite Sasakian manifolds have been obtained. Further, we obtain necessary and sufficient conditions for foliations determined by above distributions to be totally geodesic. We also study mixed geodesic screen pseudo-slant lightlike submanifolds of indefinite Sasakian manifolds.     

Dual affine connections on a quadratic hyperband distribution in a projective-metric space and their applications

In this paper, we develop fundamentals of the dual theory of quadratic hyperband distributions H of m-dimensional line elements in a projective-metric space K _n (m < n ? 1). In particular, we show that, on a dual normalized distribution H, there are induced two dual affine connections and indicate some applications of these connections to the geometry of m-webs on H.     

Pure Gaussian limit distributions of trigonometric series with bounded gaps

This paper is mainly concerned with the limit distribution of \((\cos 2\pi n_{1}x+\cdots +\cos 2\pi n_{N}x)/\sqrt{N}\) on the unit interval when the increasing sequence {n _k } has bounded gaps, i.e., 1≤n _k+1?n _k =O(1). By Bobkov–Götze [4], it was proved that the limiting variance must be less than 1/2 in this case. They proved that the centered Gaussian distribution with variance 1/4 together with mixtures of Gaussian distributions belonging to a huge class can be limit distributions. In this paper it is proved that any Gaussian distribution with variance less than 1/2 can be a limit distribution.