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.     

A queueing model for crowdsourcing

Crowdsourcing is getting popular after a number of industries such as food, consumer products, hotels, electronics, and other large retailers bought into this idea of serving customers. In this paper, we introduce a multi-server queueing model in the context of crowdsourcing. We assume that two types, say, Type 1 and Type 2, of customers arrive to a c-server queueing system. A Type 1 customer has to receive service by one of c servers while a Type 2 customer may be served by a Type 1 customer who is available to act as a server soon after getting a service or by one of c servers. We assume that a Type 1 customer will be available for serving a Type 2 customer (provided there is at least one Type 2 customer waiting in the queue at the time of the service completion of that Type 1 customer) with probability \(p, 0 \le p \le 1\). With probability \(q = 1 - p\), a Type 1 customer will opt out of serving a Type 2 customer provided there is at least one Type 2 customer waiting in the system. Upon completion of a service a free server will offer service to a Type 1 customer on an FCFS basis; however, if there are no Type 1 customers waiting in the system, the server will serve a Type 2 customer if there is one present in the queue. If a Type 1 customer decides to serve a Type 2 customer, for our analysis purposes that Type 2 customer will be removed from the system as Type 1 customer will leave the system with that Type 2 customer. Under the assumption of exponential services for both types of customers we study the model in steady state using matrix analytic methods and establish some results including explicit ones for the waiting time distributions. Some illustrative numerical examples are presented.     

Analysis of multiserver retrial queueing system: A martingale approach and an algorithm of solution

The paper studies a multiserver retrial queueing system withm servers. Arrival process is a point process with strictly stationary and ergodic increments. A customer arriving to the system occupies one of the free servers. If upon arrival all servers are busy, then the customer goes to the secondary queue, orbit, and after some random time retries more and more to occupy a server. A service time of each customer is exponentially distributed random variable with parameter μ₁. A time between retrials is exponentially distributed with parameter μ₂ for each customer. Using a martingale approach the paper provides an analysis of this system. The paper establishes the stability condition and studies a behavior of the limiting queue-length distributions as μ₂ increases to infinity. As μ₂→∞, the paper also proves the convergence of appropriate queue-length distributions to those of the associated “usual” multiserver queueing system without retrials. An algorithm for numerical solution of the equations, associated with the limiting queue-length distribution of retrial systems, is provided. AMS 2000 Subject classifications: 60K25 60H30.     

A tollbooth tandem queue with heterogeneous servers

We study a tandem queueing system with K servers and no waiting space in between. A customer needs service from one server but can leave the system only if all down-stream servers are unoccupied. Such a system is often observed in toll collection during rush hours in transportation networks, and we call it a tollbooth tandem queue. We apply matrix-analytic methods to study this queueing system, and obtain explicit results for various performance measures. Using these results, we can efficiently compute the mean and variance of the queue lengths, waiting time, sojourn time, and departure delays. Numerical examples are presented to gain insights into the performance and design of the tollbooth tandem queue. In particular, it reveals that the intuitive result of arranging servers in decreasing order of service speed (i.e., arrange faster servers at downstream stations) is not always optimal for minimizing the mean queue length or mean waiting time.     

Truncated Erlangian queueing system with fuzzy arrival rate,balking and reneging

In this paper, we derive the performance measures of the truncated Erlangian service queueing system with state-dependent rate, balking and reneging with fuzzy arrival rate _n\tilde \lambda _n so for the (M/E _r /1/N(α, β)), we have obtained P _n,s the steady state probabilities in the system with the unit in the service being at stage s (s=1, 2, …, r); k is the boundary state for the number of customer more than the one that the rate of service increases. We treat this queueing system for general values of r, k and N and derive the Fuzzy effective measures for the operation of the system at any time.     

Analysis of the adaptive MMAP[K]/PH[K]/1 queue: A multi-type queue with adaptive arrivals and general impatience

In this paper we introduce the adaptive MMAP[K] arrival process and analyze the adaptive MMAP[K]/PH[K]/1 queue. In such a queueing system, customers of K different types with Markovian inter-arrival times and possibly correlated customer types, are fed to a single server queue that makes use of r thresholds. Service times are phase-type and depend on the type of customer in service. Type k customers are accepted with some probability a_i,k if the current workload is between threshold i − 1 and i. The manner in which the arrival process changes its state after generating a type k customer also depends on whether the customer is accepted or rejected.     

Optimal control of an M/M/2 queueing system with finite capacity operating under the triadic (0,Q,N,M) policy

operating under the triadic (0,Q, N,M) policy, where L is the maximum number of customers in the system. The number of working servers can be adjusted one at a time at arrival epochs or at service completion epochs depending on the number of customers in the system. Analytic closed-form solutions of the controllable M/M/2 queueing system with finite capacity operating under the triadic (0,Q, N,M) policy are derived. This is a generalization of the ordinary M/M/2 and the controllable M/M/1 queueing systems in the literature. The total expected cost function per unit time is developed to obtain the optimal operating (0,Q, N,M) policy at minimum cost.     

The BMAP/PH/N retrial queue with Markovian flow of breakdowns

We consider a multi-server retrial queue with the Batch Markovian Arrival Process (BMAP). The servers are identical and independent of each other. The service time distribution of a customer by a server is of the phase (PH) type. If a group of primary calls meets idle servers the primary calls occupy the corresponding number of servers. If the number of idle servers is insufficient the rest of calls go to the orbit of unlimited size and repeat their attempts to get service after exponential amount of time independently of each other. Busy servers are subject to breakdowns and repairs. The common flow of breakdowns is the MAP. An event of this flow causes a failure of any busy server with equal probability. When a server fails the repair period starts immediately. This period has PH type distribution and does not depend on the repair time of other broken-down servers and the service time of customers occupying the working servers. A customer whose service was interrupted goes to the orbit with some probability and leaves the system with the supplementary probability. We derive the ergodicity condition and calculate the stationary distribution and the main performance characteristics of the system. Illustrative numerical examples are presented.     

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.     

Analysis of Queueing Systems with Synchronous Single Vacation for Some Servers

We study a multi-server M/M/c type queue with a single vacation policy for some idle servers. In this queueing system, if at a service completion instant, any d (d c) servers become idle, these d servers will take one and only one vacation together. During the vacation of d servers, the other c–d servers do not take vacation even if they are idle. Using a quasi-birth-and-death process and the matrix analytic method, we obtain the stationary distribution of the system. Conditional stochastic decomposition properties have been established for the waiting time and the queue length given that all servers are busy.     

Implementation of Markovian Queueing Network Model with Multiple Closed Chains

Mathematical strategy portrays the performance evaluation of computer and communication system and it deals with the stochastic properties of the multiclass Markovian queueing system with class-dependent and server-dependent service times. An algorithm is designed where the job transitions are characterized by more than one closed Markov chain. Generating functions are implemented to derive closed form of solutions and product form solution with the parameters such as stability, normalizations constant and marginal distributions. For such a system with N servers and L chains, the solutions are considerably more complicated than those for the systems with one sub-chain only. In Multi-class queueing network, a job moves from a queue to another queue with some probability after getting a service. A multiple class of customer could be open or closed where each class has its own set of queueing parameters. These parameters are obtained by analyzing each station in isolation under the assumption that the arrival process of each class is a state-dependent Markovian process along with different service time distributions. An algorithmic approach is implemented from the generating function representation for the general class of Networks. Based on the algorithmic approach it is proved that how open and closed sub-chain interact with each other in such system. Specifically, computation techniques are provided for the calculation of the Markovian model for multiple chains and it is shown that these algorithms converge exponentially fast.     

A batch arrival retrial queue with two phases of service and Bernoulli vacation schedule

We consider an M X /G/1 queueing system with two phases of heterogeneous service and Bernoulli vacation schedule which operate under a linear retrial policy. In addition, each individual customer is subject to a control admission policy upon the arrival. This model generalizes both the classical M/G/1 retrial queue with arrivals in batches and a two phase batch arrival queue with a single vacation under Bernoulli vacation schedule. We will carry out an extensive stationary analysis of the system , including existence of the stationary regime, embedded Markov chain, steady state distribution of the server state and number of customer in the retrial group, stochastic decomposition and calculation of the first moment.     

Discrete NT-policy single server queue with Markovian arrival process and phase type service

We consider a discrete time single server queueing system in which arrivals are governed by the Markovian arrival process. During a service period, all customers are served exhaustively. The server goes on vacation as soon as he/she completes service and the system is empty. Termination of the vacation period is controlled by two threshold parameters N and T, i.e. the server terminates his/her vacation as soon as the number waiting reaches N or the waiting time of the leading customer reaches T units. The steady state probability vector is shown to be of matrix-geometric type. The average queue length and the probability that the server is on vacation (or idle) are obtained. We also derive the steady state distribution of the waiting time at arrivals and show that the vacation period distribution is of phase type.     

A Discrete-Time Geo /G/1 Retrial Queue with General Retrial Times

We consider a discrete-time Geo/G/1 retrial queue in which the retrial time has a general distribution and the server, after each service completion, begins a process of search in order to find the following customer to be served. We study the Markov chain underlying the considered queueing system and its ergodicity condition. We find the generating function of the number of customers in the orbit and in the system. We derive the stochastic decomposition law and as an application we give bounds for the proximity between the steady-state distributions for our queueing system and its corresponding standard system. Also, we develop recursive formulae for calculating the steady-state distribution of the orbit and system sizes. Besides, we prove that the M/G/1 retrial queue with general retrial times can be approximated by our corresponding discrete-time system. Finally, we give numerical examples to illustrate the effect of the parameters on several performance characteristics.     

Multi-server queueing systems with cooperation of the servers

In this paper, we consider an N-server queueing model with homogeneous servers in which customers arrive according to a stationary Poisson arrival process. The service times are exponentially distributed. Two new customer’s service disciplines assuming simultaneous service of arriving customer by all currently idle servers are discussed. The steady state analysis of the queue length and sojourn time distribution is performed by means of the matrix analytic methods. Numerical examples, which illustrate advantage of introduced disciplines comparing to the classical one, are presented.     

Effect of global FCFS and relative load distribution in two-class queues with dedicated servers

In this paper, we investigate multi-class multi-server queueing systems with global FCFS policy, i.e., where customers requiring different types of service—provided by distinct servers—are accommodated in one common FCFS queue. In such scenarios, customers of one class (i.e., requiring a given type of service) may be hindered by customers of other classes. The purpose of this paper is twofold: to gain (qualitative and quantitative) insight into the impact of (i) the global FCFS policy and (ii) the relative distribution of the load amongst the customer classes, on the system performance. We therefore develop and analyze an appropriate discrete-time queueing model with general independent arrivals, two (independent) customer classes and two class-specific servers. We study the stability of the system and derive the system-content distribution at random slot boundaries; we also obtain mean values of the system content and the customer delay, both globally and for each class individually. We then extensively compare these results with those obtained for an analogous system without global FCFS policy (i.e., with individual queues for the two servers). We demonstrate that global FCFS, as well as the relative distribution of the load over the two customer classes, may have a major impact on the system performance.     

Locating and staffing service centers under service level constraints

Many firms experience demand from geographically dispersed customers. This demand is satisfied by mobile servers that travel to the site of the customer. To achieve this in a cost-effective manner, the firm needs to decide where to locate its service centers, which customer regions to assign to the centers and the staffing level   at each center so that customers experience a defined level of service at minimum cost. To determine adequate staffing levels, we approximate a service center and the customer regions assigned to it as an M/G/s$M/G/s$ queueing system. Based on this queueing model, we explore properties of two different staffing level functions. The queueing model is embedded in a large-scale integer program. Using the concept of column generation, we develop an algorithm that can efficiently solve moderate-sized problems.     

Diffusion Approximation in Overloaded Switching Queueing Models

The asymptotic behavior of a queueing process in overloaded state-dependent queueing models (systems and networks) of a switching structure is investigated. A new approach to study fluid and diffusion approximation type theorems (without reflection) in transient and quasi-stationary regimes is suggested. The approach is based on functional limit theorems of averaging principle and diffusion approximation types for so-called Switching processes. Some classes of state-dependent Markov and non-Markov overloaded queueing systems and networks with different types of calls, batch arrival and service, unreliable servers, networks (M _SM,Q /M _SM,Q /1/) ^r switched by a semi-Markov environment and state-dependent polling systems are considered.     

Containment of socially optimal policies in multiple-facility Markovian queueing systems

We consider a Markovian queueing system with N heterogeneous service facilities, each of which has multiple servers available, linear holding costs, a fixed value of service and a first-come-first-serve queue discipline. Customers arriving in the system can be either rejected or sent to one of the N facilities. Two different types of control policies are considered, which we refer to as ‘selfishly optimal’ and ‘socially optimal’. We prove the equivalence of two different Markov Decision Process formulations, and then show that classical M/M/1 queue results from the early literature on behavioural queueing theory can be generalized to multiple dimensions in an elegant way. In particular, the state space of the continuous-time Markov process induced by a socially optimal policy is contained within that of the selfishly optimal policy. We also show that this result holds when customers are divided into an arbitrary number of heterogeneous classes, provided that the service rates remain non-discriminatory.     

On the service system MX/G/∞

In the present paper we consider the service system M^X/G/∞ characterized by an infinite number of servers anda general service time distribution. The customers arrive at the system in groups of size X, which is a random variable, the time between group arrivals being exponentially distributed. Using simple probability arguments, we obtain probability generating functions (p.g.f.'s) of the number of busy servers at time t and the number that depart by time t. Several other properties of these random variables are also discussed.