Class clustering destroys delay differentiation in priority queues

This paper considers a discrete-time priority queueing model with one server and two types (classes) of customers. Class-1 customers have absolute (service) priority over class-2 customers. New customer batches enter the system at the rate of one batch per slot, according to a general independent arrival process, i.e., the batch sizes (total numbers of arrivals) during consecutive time slots are i.i.d. random variables with arbitrary distribution. All customers entering the system during the same time slot (i.e., belonging to the same arrival batch) are of the same type, but customer types may change from slot to slot, i.e., from batch to batch. Specifically, the types of consecutive customer batches are correlated in a Markovian way, i.e., the probability that any batch of customers has type 1 or 2, respectively, depends on the type of the previous customer batch that has entered the system. Such an arrival model allows to vary not only the relative loads of both customer types in the arrival stream, but also the amount of correlation between the types of consecutive arrival batches. The results reveal that the amount of delay differentiation between the two customer classes that can be achieved by the priority mechanism strongly depends on the amount of such interclass correlation (or, class clustering) in the arrival stream. We believe that this phenomenon has been largely overlooked in the priority-scheduling literature.     

Analysis of a two-class single-server discrete-time FCFS queue: the effect of interclass correlation

In this paper, we study a discrete-time queueing system with one server and two classes of customers. Customers enter the system according to a general independent arrival process. The classes of consecutive customers, however, are correlated in a Markovian way. The system uses a “global FCFS” service discipline, i.e., all arriving customers are accommodated in one single FCFS queue, regardless of their classes. The service-time distribution of the customers is general but class-dependent, and therefore, the exact order in which the customers of both classes succeed each other in the arrival stream is important, which is reflected by the complexity of the system content and waiting time analysis presented in this paper. In particular, a detailed waiting time analysis of this kind of multi-class system has not yet been published, and is considered to be one of the main novelties by the authors. In addition to that, a major aim of the paper is to estimate the impact of interclass correlation in the arrival stream on the total number of customers in the system, and the customer delay. The results reveal that the system can exhibit two different classes of stochastic equilibrium: a “strong” equilibrium where both customer classes give rise to stable behavior individually, and a “compensated” equilibrium where one customer type creates overload.     

Ergodicity properties of rerouting strategies in queueing networks

In this paper we study ergodicity properties for simple Markovian models describing different rerouting policies for queueing systems with two Poisson arrival streams and two exponential servers. On their arrival, customers are either routed to their normal server or are rerouted to the alternate server. We model the extra work for rerouted customers by assuming that each rerouted customer generates several tasks for the alternate server. This model can become non-ergodic even when the total arrival rate is smaller than the total service rate in the system. We compare different strategies for rerouting customers on the basis of necessary and sufficient conditions for ergodicity. For this purpose we make use of Lyapunov functions.Senior Research Associate N.F.W.O. (Belgian National Foundation for Scientific Research). Part of the research leading to this paper was carried out within the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Minister's Office of Science, Technology and Culture. The scientific responsibility rests with the authors.This author was partly supported by a Cátedra Patrimonial of the Mexican Council of Science and Technology.     

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 single-server discrete-time retrial <Emphasis Type="Italic">G</Emphasis>-queue with server breakdowns and repairs

This paper concerns a discrete-time Geo/Geo/1 retrial queue with both positive and negative customers where the server is subject to breakdowns and repairs due to negative arrivals. The arrival of a negative customer causes one positive customer to be killed if any is present, and simultaneously breaks the server down. The server is sent to repair immediately and after repair it is as good as new. The negative customer also causes the server breakdown if the server is found idle, but has no effect on the system if the server is under repair. We analyze the Markov chain underlying the queueing system and obtain its ergodicity condition. The generating function of the number of customers in the orbit and in the system are also obtained, along with the marginal distributions of the orbit size when the server is idle, busy or down. Finally, we present some numerical examples to illustrate the influence of the parameters on several performance characteristics of the system.     

Multiserver queue with addressed retrials

This paper presents a multiserver retrial queueing system with servers kept apart, thereby rendering it impossible for one to know the status (idle/busy) of the others. Customers proceeding to one channel will have to go to orbit if the server in it is busy and retry after some time to some channel, not necessarily the one already tried. Each orbital customer, independently of others, chooses the server randomly according to some specified probability distribution. Further this distribution is identical for all customers. We assume that the same ‘orbit’ is used by all retrial customers, between repeated attempts, to access the servers. We derive the system state probability distribution under Poisson arrival process of external customers, exponentially distributed service times and linear retrial rates to access the servers. Several system state characteristics are obtained and numerical illustrations provided. AMS subject classification: Primary 60K25 60K20     

Assembly-like queues with finite capacity: Bounds,asymptotics and approximations

In this paper we study a queueing model of assembly-like manufacturing operations. This study was motivated by an examination of a circuit pack testing procedure in an AT & T factory. However, the model may be representative of many manufacturing assembly operations. We assume that customers fromn classes arrive according to independent Poisson processes with the same arrival rate into a single-server queueing station where the service times are exponentially distributed. The service discipline requires that service be rendered simultaneously to a group of customers consisting of exactly one member from each class. The server is idle if there are not enough customers to form a group. There is a separate waiting area for customers belonging to the same class and the size of the waiting area is the same for all classes. Customers who arrive to find the waiting area for their class full, are lost. Performance measures of interest include blocking probability, throughput, mean queue length and mean sojourn time. Since the state space for this queueing system could be large, exact answers for even reasonable values of the parameters may not be easy to obtain. We have therefore focused on two approaches. First, we find upper and lower bounds for the mean sojourn time. From these bounds we obtain the asymptotic solutions as the arrival rate (waiting room, service rate) approaches zero (infinity). Second, for moderate values of these parameters we suggest an approximate solution method. We compare the results of our approximation against simulation results and report good correspondence.     

Equilibrium pricing in an M/G/1 retrial queue with reserved idle time and setup time

Power consumption is a ubiquitous and challenging problem in modern society. To save energy, one should turn off an idle device which still consumes about 60% of its peak consumption and switch it on again when some jobs arrive. However, it is not tolerate for delay sensitive applications. Therefore, there is a trade-off between power consumption and delay performance. In this paper we study an M/G/1 retrial queueing system with setup times in which the server keeps idle for a reserved idle time after completion of a service. If there are arrivals during this reserved idle time, these customers can be served immediately. Otherwise, the server will be turned off for saving energy until a new customer comes to activate the server. The setup time follows an exponential distribution. Based on the reward-cost function and the expected payoff, all customers will make decisions on whether to join or balk the system upon arrival. Given these strategic behaviors we study the optimal pricing strategies from the perspective of the server and social planner, respectively. The optimization of the reserved idle time for maximizing the server’s profit is also studied. Finally, numerical experiments are presented to illustrate the impact of system parameters on the customers’ equilibrium behavior and profit maximization solutions.     

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.     

Batch arrival queues with vacations and server setup

We study a single server queueing system whose arrival stream is compound Poisson and service times are generally distributed. Three types of idle period are considered: threshold, multiple vacations, and single vacation. For each model, we assume after the idle period, the server needs a random amount of setup time before serving. We obtain the steady-state distributions of system size and waiting time and expected values of the cycle for each model. We also show that the distributions of system size and waiting time of each model are decomposed into two parts, whose interpretations are provided. As for the threshold model, we propose a method to find the optimal value of threshold to minimize the total expected operating cost.     

An optimal service rate in a Poisson arrival queue with two-stage service policy*

We consider a two-stage service policy for a Poisson arrival queueing system. The idle server starts to work with ordinary service rate when a customer arrives. If the number of customers in the system reaches N, the service rate gets faster and continues until the system becomes empty. Otherwise, the server finishes the busy period with ordinary service rate. After assigning various operating costs to the system, we show that there exists a unique fast service rate minimizing the long-run average cost per unit time.This work was supported by Korea Research Foundation Grant(KRF-2002-070-C00021).     

Analysis of <Emphasis Type="Italic">N</Emphasis>-policy queues with disastrous breakdown

In the area of optimal design and control of queues, the N-policy has received great attention. A single server queueing system with system disaster is considered where the server waits till N customers accumulate in the queue and upon the arrival of Nth customer the server begins to serve the customers until the system becomes idle or the occurrence of disaster whichever happens earlier. The system size probabilities in transient state are obtained in closed form using generating functions and steady-state system size probabilities are derived in closed form using generating functions and continued fractions. Further, the mean and variance for the number of customers in the system are derived for both transient and steady states and these results are deduced for the specific models. Time-dependent busy period distribution is also obtained. Numerical illustrations are also shown to visualize the system effect.     

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.     

Fluid limits of many-server queues with abandonments,general service and continuous patience time distributions

This paper extends the works of Kang and Ramanan (2010) and Kaspi and Ramanan (2011), removing the hypothesis of absolute continuity of the service requirement and patience time distributions. We consider a many-server queueing system in which customers enter service in the order of arrival in a non-idling manner and where reneging is considerate. Similarly to Kang and Ramanan (2010), the dynamics of the system are represented in terms of a process that describes the total number of customers in the system as well as two measure-valued processes that record the age in service of each of the customers being served and the “potential” waiting times. When the number of servers goes to infinity, fluid limit is established for this triple of processes. The convergence is in the sense of probability and the limit is characterized by an integral equation.     

On optimal polling policies

In a single-server polling system, the server visits the queues according to a routing policy and while at a queue, serves some or all of the customers there according to a service policy. A polling (or scheduling) policy is a sequence of decisions on whether to serve a customer, idle the server, or switch the server to another queue. The goal of this paper is to find polling policies that stochastically minimize the unfinished work and the number of customers in the system at all times. This optimization problem is decomposed into three subproblems: determine the optimal action (i.e., serve, switch, idle) when the server is at a nonempty queue; determine the optimal action (i.e., switch, idle) when the server empties a queue; determine the optimal routing (i.e., choice of the queue) when the server decides to switch. Under fairly general assumptions, we show for the first subproblem that optimal policies are greedy and exhaustive, i.e., the server should neither idle nor switch when it is at a nonempty queue. For the second subproblem, we prove that in symmetric polling systems patient policies are optimal, i.e., the server should stay idling at the last visited queue whenever the system is empty. When the system is slotted, we further prove that non-idling and impatient policies are optimal. For the third subproblem, we establish that in symmetric polling systems optimal policies belong to the class of Stochastically Largest Queue (SLQ) policies. An SLQ policy is one that never routes the server to a queue known to have a queue length that is stochastically smaller than that of another queue. This result implies, in particular, that the policy that routes the server to the queue with the largest queue length is optimal when all queue lengths are known and that the cyclic routing policy is optimal in the case that the only information available is the previous decisions.This work was supported in part by NSF under Contract ASC-8802764.     

Single server retrial queues with two way communication

The main aim of this paper is to study the steady state behavior of an M/G/1-type retrial queue in which there are two flows of arrivals namely ingoing calls made by regular customers and outgoing calls made by the server when it is idle. We carry out an extensive stationary analysis of the system, including stability condition, embedded Markov chain, steady state joint distribution of the server state and the number of customers in the orbit (i.e., the retrial group) and calculation of the first moments. We also obtain light-tailed asymptotic results for the number of customers in the orbit. We further formulate a more complicate but realistic model where the arrivals and the service time distributions are modeled in terms of the Markovian arrival process (MAP) and the phase (PH) type distribution.     

A multi-class discrete-time queueing system under the FCFS service discipline

The problem with the FCFS server discipline in discrete-time queueing systems is that it doesn’t actually determine what happens if multiple customers enter the system at the same time, which in the discrete-time paradigm translates into ‘during the same time-slot’. In other words, it doesn’t specify in which order such customers are served. When we consider multiple types of customers, each requiring different service time distributions, the precise order of service even starts to affect quantities such as queue content and delays of arbitrary customers, so specifying this order will be prime. In this paper we study a multi-class discrete-time queueing system with a general independent arrival process and generally distributed service times. The service discipline is FCFS and customers entering during the same time-slot are served in random order. It will be our goal to search for the steady-state distribution of queue content and delays of certain types of customers. If one thinks of the time-slot as a continuous but bounded time period, the random order of service is equivalent to FCFS if different customers have different arrival epochs within this time-slot and if the arrival epochs are independent of customer class. For this reason we propose two distinct ways of analysing; one utilizing permutations, the other considering a slot as a bounded continuous time frame.     

The Versatility of MMAP[K] and the MMAP[K]/G[K]/1 Queue

This paper studies a single server queueing system with multiple types of customers. The first part of the paper discusses some modeling issues associated with the Markov arrival processes with marked arrivals (MMAP[K], where K is an integer representing the number of types of customers). The usefulness of MMAP[K] in modeling point processes is shown by a number of interesting examples. The second part of the paper studies a single server queueing system with an MMAP[K] as its input process. The busy period, virtual waiting time, and actual waiting times are studied. The focus is on the actual waiting times of individual types of customers. Explicit formulas are obtained for the Laplace–Stieltjes transforms of these actual waiting times.     

Insensitivity in discrete time queues with a moving server

Queues in which customers request service consisting of an integral number of segments and in which the server moves from service station to service station are of considerable interest to practitioners working on digital communications networks. In this paper, we present insensitivity theorems and thereby equilibrium distributions for two discrete time queueing models in which the server may change from one customer to another after completion of each segment of service. In the first model, exactly one segment of service is provided at each time point whether or not an arrival occurs, while in the second model, at most one arrival or service occurs at each time point. In each model, customers of typet request a service time which consists ofl segments in succession with probabilityb _t(l). Examples are given which illustrate the application of the theorems to round robin queues, to queues with a persistent server, and to queues in which server transition probabilities do not depend on the server's previous position. In addition, for models in which the probability that the server moves from one position to another depends only on the distance between the positions, an amalgamation procedure is proposed which gives an insensitive model on a coarse state space even though a queue may not be insensitive on the original state space. A model of Daduna and Schassberger is discussed in this context.This work was supported by the Australian Research Council.