Synchronous working vacation policy for finite-buffer multiserver queueing system

This paper presents modeling and analysis of unreliable Markovian multiserver finite-buffer queue with discouragement and synchronous working vacation policy. According to this policy, c servers keep serving the customers until the number of idle servers reaches the threshold level d; then d idle servers take vacation altogether. Out of these d vacationing servers, d_W servers may opt for working vacation i.e. they serve the secondary customers with different rates during the vacation period. On the other hand, the remaining d − d_W = d_V servers continue to be on vacation. During the vacation of d servers, the other e = c − d servers must be present in the system even if they are idle. On returning from vacation, if the queue size does not exceed e, then these d servers take another vacation together; otherwise start serving the customers. The servers may undergo breakdown simultaneously both in regular busy period and working vacation period due to the failure of a main control unit. This main unit is then repaired by the repairman in at most two phases. We obtain the stationary performance measures such as expected queue length, average balking and reneging rate, throughput, etc. The steady state and transient behaviours of the arriving customers and the servers are examined by using matrix analytical method and numerical approach based on Runge-Kutta method of fourth order, respectively. The sensitivity analysis is facilitated for the transient model to demonstrate the validity of the analytical results and to examine the effect of different parameters on various performance indices.     

Exact analysis for multiserver queueing systems with cross selling

Annals of Operations Research - Exact analysis of a multi-server Markovian queueing system with cross selling in steady-state is presented. Cross selling attempt is initiated at the end of a...     

A two threshold vacation policy in multiserver queueing systems

We consider a queueing system with c servers and a threshold type vacation policy. In this system, when a certain number d < c of servers become idle at a service completion instant, these d servers will take a synchronous vacation of random length together. After each vacation, the number of customers in the system is checked. If that number is N or more, these d servers will resume serving the queue; otherwise, they will take another vacation together. Using the matrix analytical method, we obtain the stationary distribution of queue length and prove the conditional stochastic decomposition properties. Through numerical examples, we discuss the performance evaluation and optimization issues in such a vacation system with this (d, N) threshold policy.     

On the law of the iterated logarithm in multiserver open queueing networks

The paper is devoted to the analysis of queueing systems in the context of the network and communication theory. We investigate a theorem on the law of the iterated logarithm for a queue of jobs in a multiserver open queueing network under heavy traffic conditions.     

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.     

On stationary tandem queueing networks with job feedback

The class of tandem queueing networks with job feedback is studied under stationarity conditions on the arrival and service times sequences. Each job, after completing service in the last queue, is fed back (rerouted) to the first one, a random number of times, before leaving the system. The average execution time per job is exactly computed, as the number of jobs becomes large, and is minimized under mild conditions. The degree of parallelism achieved in the processing is also computed. The issue of rate-stability of the system is then considered. The network is defined to be rate-stable iff the job departure rate is equal to the job arrival rate; that depends heavily on the dynamic feedback policy we employ to place rerouted jobs in specific places of the front queue buffer of the network. The condition under which the network is rate-stable is specified, and a dynamic feedback policy is constructed, which rate-stabilizes the system under the maximum possible job arrival rate; thus, it maximizes the dynamic throughput of the network. Other related results concerning the performance of tandem networks with feedback are obtained.Research supported in part by grants NSF-DDM-RIA-9010778, NSF-NCR-9116268, NSF-NCR-NYI-9258 507, by an AT&T Foundation grant and a GTE Fellowship.     

An efficient computation algorithm for a multiserver feedback retrial queue with a large queueing capacity

Kumar et al. consider the M/M/c/N+c feedback queue with constant retrial rate [1]. They provide a solution for the steady state probabilities based on the matrix-geometric method. We show that there exists a more efficient computation method to calculate the steady state probabilities when N+c$N+c$ is large. We prove that the number of zero-eigenvalues of the characteristic matrix polynomial associated with the balance equation is ⌊(N+c+2)/2⌋$\lfloor (N+c+2)/2\rfloor$. As consequence, the remaining eigenvalues inside the unit circle can be computed in a quick manner based on the Sturm sequences. Therefore, the steady state probabilities can be determined in an efficient way.     

Numerical investigation of a multiserver retrial model

We consider a queueing model in which customers arrive in a Poisson stream to be served by one ofc servers. Each arriving customer enters a pool of active customers and starts generating requests for service at exponentially distributed time intervals at rate until he finds a free server and begins service. An analytical solution of this model is difficult and does not lend itself to numerical implementation. In this paper, we make a simplifying approximation, based on understanding of the physical behavior of the system, which yields an infinitesimal generator with a modified matrix-geometric equilibrium probability vector. That vector can be very efficiently computed even for high congestion levels. Illustrative numerical examples demonstrate the effectiveness of the approximation as well as the effect of the retrial rate on the system behavior for various levels of congestion. This study shows how numerical results for analytically intractable systems can be obtained by combining intuition with efficient algorithmic methods.This author's research was supported in part by Grants Nos. ECS-88-03061 from the National Science Foundation and AFOSR-88-0076 from the Air Force Office of Scientific Research.     

Towards minimum loss job routing to parallel heterogeneous multiserver queues via index policies

This paper considers a Markovian model for the optimal dynamic routing of homogeneous traffic to parallel heterogeneous queues, each having its own finite input buffer and server pool, where buffer and server-pool sizes, as well as service rates, may differ across queues. The main goal is to identify a heuristic index-based routing policy with low complexity that consistently attains a nearly minimum average loss rate (or, equivalently, maximum throughput rate). A second goal is to compare alternative policies, with respect to computational demands and empirical performance. A novel routing policy that can be efficiently computed is developed based on a second-order extension to Whittle’s restless bandit (RB) index, since the latter is constant for this model. New results are also given for the more computationally demanding index policy obtained via policy improvement (PI), including that it reduces to shortest queue routing under symmetric buffer and server-pool sizes. A numerical study shows that the proposed RB index policy is nearly optimal across the instances considered, and substantially outperforms several previously proposed index policies.     

The “least flexible job first” rule in scheduling and in queueing

We consider an environment with m$m$ machines in parallel operating at different speeds. The processing requirements of all jobs are independent and have the same exponential distribution. Job j$j$ may only be processed on a specific subset of the m$m$ machines, referred to as its restricted set. The restricted sets are nested and preemptions are allowed. We show that the Least Flexible Job to the Fastest Machine (LFJ-FM) minimizes the expected makespan and the total expected completion time.     

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.     

Exact analysis of queueing networks with multiple job classes and blocking-after-service

Two models of closed queueing networks with blocking-after-service and multiple job classes are analyzed. The first model is a network withN stations and each station has either type II or type III. The second model is a star-like queueing network, also called a central server model, in which the stations may have either type I or type IV, with the condition that the neighbors of these stations must be of type II or type III such that blocking will be caused only by this set of station types. Exact product form solutions are obtained for the equilibrium state probabilities in both models. Formulae for performance measures such as throughput and the mean number of jobs are also derived.This work was supported by the National Science Foundation (NSF) under Grant No. CCR-90-11981.     

A tandem queueing model with coupled processors

We consider a tandem queue with coupled processors and analyze the two-dimensional Markov process representing the numbers of jobs in the two stations. A functional equation for the generating function of the stationary distribution of this two-dimensional process is derived and solved through the theory of Riemann-Hilbert boundary value problems.     

A queueing model of delayed product differentiation

We consider a production system in which a supplier produces semi-finished items on a make-to-stock basis for a manufacturer that will customize the items on a make-to-order basis. The proportion of total processing time undertaken by the supplier determines how suitable the semi-finished items will be to meet customer demand. The manufacturer wishes to determine the optimal point of differentiation (the proportion of processing completed by the supplier) and its optimal semi-finished goods buffer size. We use matrix geometric methods to evaluate various performance measures for this system, and then, with enumeration techniques, obtain optimal solutions. We find that delayed product differentiation is attractive when the manufacturer can balance the costs of customer order fulfillment delay with the costs associated with unsuitable items.     

A multi-server queueing model with server consultations

We consider a multi-server queueing model in which the arrivals occur according to a Markovian arrival process. One of the servers, henceforth referred to as the main server, offers consultation to fellow servers (referred to as regular servers) apart from serving the customers. A regular server may request a consultation only when serving a customer and is offered consultation on a first-come-first-served basis by the main server. The main server gives a preemptive priority to regular servers (for consulting) over customers. Thus, the main server can undergo interruptions during his/her servicing the customers. Under the assumptions of exponential services and consultations, the model is analyzed in steady-state using the well-known matrix-analytic methods. Illustrative numerical examples to bring out the qualitative nature of the model under study are presented.     

A catastrophic queueing model with delayed action

A queueing model with catastrophes and delayed action is studied in this paper. This delayed action could be in the form of protecting or removing all the customers that are in the system based on the outcome of two random clocks which are simultaneously activated upon the occurrence of a catastrophic event. Assuming the customers to arrive according to a versatile Markovian point process to a single server system, the service times to be of phase type, and all other underlying random variables to be exponentially distributed, we use matrix-analytic methods to study the delayed catastrophic model in steady-state. Needed expressions for the number in the system as well as the waiting time distributions are derived along with a discussion on some special cases of this model. Detailed illustrative examples are presented.     

Generalized sub-Gaussian fractional Brownian motion queueing model

It is well known that often the one-dimensional distribution of a queue content is not Gaussian but its tails behave like a Gaussian. We propose to consider a general class of processes, namely the class of $\varphi $ -sub-Gaussian random processes, which is more general than the Gaussian one and includes non-Gaussian processes. The class of sub-Gaussian random processes contains Gaussian processes also and therefore is of special interest. In this paper we provide an estimate for the queue content distribution of a fluid queue fed by $N$ independent strictly $\varphi $ -sub-Gaussian generalized fractional Brownian motion input processes. We obtain an upper estimate of buffer overflow probability in a finite buffer system defined on any finite time interval $[a,b]$ or infinite interval $[0,\infty )$ . The derived estimate captures more accurately the performance of the queueing system for a wider-range of input processes.     

A discrete-time retrial queueing model with one server

This paper presents a one-server queueing model with retrials in discrete-time. The number of primary jobs arriving in a time slot follows a general probability distribution and the different numbers of primary arrivals in consecutive time slots are mutually independent. Each job requires from the server a generally distributed number of slots for its service, and the service times of the different jobs are independent. Jobs arriving in a slot can start their service only at the beginning of the next slot. When upon arrival jobs find the server busy all incoming jobs are sent into orbit. When upon arrival in a slot jobs find the server idle, then one of the incoming jobs (randomly chosen) in that slot starts its service at the beginning of the next slot, whereas the other incoming jobs in that slot, if any, are sent into orbit. During each slot jobs in the orbit try to re-enter the system individually, independent of each other, with a given retrial probability.