A note on the hypercube model

We consider a variation of the hypercube model in which there are N distinguishable servers and R types of customers. Customers that find all servers busy (blocked customers) are lost. When service times are exponentially distributed and customers arrive according to independent Poisson streams, we show that the policy which always assigns customers to the fastest available server minimizes the long-run average number of lost customers. Furthermore, we derive an upper bound for the blocking probability and the long-run average number of customers lost.     

Equilibrium customers’ choice between FCFS and random servers

Consider two servers of equal service capacity, one serving in a first-come first-served order (FCFS), and the other serving its queue in random order. Customers arrive as a Poisson process and each arriving customer observes the length of the two queues and then chooses to join the queue that minimizes its expected queueing time. Assuming exponentially distributed service times, we numerically compute a Nash equilibrium in this system, and investigate the question of which server attracts the greater share of customers. If customers who arrive to find both queues empty independently choose to join each queue with probability 0.5, then we show that the server with FCFS discipline obtains a slightly greater share of the market. However, if such customers always join the same queue (say of the server with FCFS discipline) then that server attracts the greater share of customers. This research was supported by the Israel Science Foundation grant No. 526/08.     

Queueing systems on a circle

Consider a ring on which customers arrive according to a Poisson process. Arriving customers drop somewhere on the circle and wait there for a server who travels on the ring. Whenever this server encounters a customer, he stops and serves the customer according to an arbitrary service time distribution. After the service is completed, the server removes the client from the circle and resumes his journey.We are interested in the number and the locations of customers that are waiting for service. These locations are modeled as random counting measures on the circle. Two different types of servers are considered: The polling server and the Brownian (or drunken) server. It is shown that under both server motions the system is stable if the traffic intensity is less than 1. Furthermore, several earlier results on the configuration of waiting customers are extended, by combining results from random measure theory, stochastic integration and renewal theory.     

Optimal order for two servers in tandem

We consider two servers (serveri, i=1, 2) in tandem for which the order of servers can be changed. Server 1 has a general service time distribution and server 2 has either its shifted or truncated distribution. This permits that the service times at the two servers are overlapping. An unlimited queue is allowed in front of the first server. For the systems having zero buffer capacity between the servers, we show that the sojourn time of every customer is stochastically minimized under any arrival process if server 2 is first. For the systems with infinite buffer capacity and a Poisson arrivals, we show that this order of servers minimizes mean customer delay when traffic is light. Several numerical examples are presented to demonstrate that this optimal order is invariant under any arrival process (the interarrival times are i.i.d. r.v.'s) and mild traffic condition.Research funded by NEC Corporation C & C Laboratory.     

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     

Partial Pooling in Tandem Lines with Cooperation and Blocking

For a tandem line of finite, single-server queues operating under the production blocking mechanism, we study the effects of pooling several adjacent stations and the associated servers into a single station with a single team of servers. We assume that the servers are cross-trained (so that they can work at several different stations) and that two or more servers can cooperate on the same job. For such a system, we provide sufficient conditions on the service times and sizes of the input and output buffers at the pooled station under which pooling will decrease the departure time of each job from the system (and hence increase the system throughput). We also show that pooling decreases the total number of jobs in the system at any given time and the sojourn time of each job in the system if the departure time of each job from the system is decreased by pooling and there is an arrival stream at the first station. Moreover, we provide sufficient conditions under which pooling will improve the holding cost of each job in the system incurred before any given time, and extend our results to closed tandem lines and to queueing networks with either a more general blocking mechanism or probabilistic routing. Finally, we present a numerical study aimed at quantifying the improvements in system performance obtained through pooling and at understanding which stations should be pooled to achieve the maximum benefit. Our results suggest that the improvements gained by pooling may be substantial and that the bottleneck station should be among the pooled stations in order to obtain the greatest benefit. AMS subject classification: 90B22     

Analysis of M/M/S queues with 1-limited service

In this paper, a multiple server queue, in which each server takes a vacation after serving one customer is studied. The arrival process is Poisson, service times are exponentially distributed and the duration of a vacation follows a phase distribution of order 2. Servers returning from vacation immediately take another vacation if no customers are waiting. A matrix geometric method is used to find the steady state joint probability of number of customers in the system and busy servers, and the mean and the second moment of number of customers and mean waiting time for this model. This queuing model can be used for the analysis of different kinds of communication networks, such as multi-slotted networks, multiple token rings, multiple server polling systems and mobile communication systems.     

Understanding the marginal impact of customer flexibility

We study the marginal impact of customer flexibility in service systems. We consider a queueing system with multiple parallel servers, in which a proportion of customers are flexible and can go to any server, while the remainder require service at a particular server. We show that the stationary expected waiting time is decreasing and convex in the proportion of flexible customers. We also show, for a related Inventory Model, in which servers are never idle and can build up inventory, that convexity holds in a strong sample-path sense. Our results reinforce the idea that a little flexibility goes a long way.     

Two Queues with Weighted One-Way Overflow

We consider an open queueing network consisting of two queues with Poisson arrivals and exponential service times and having some overflow capability from the first to the second queue. Each queue is equipped with a finite number of servers and a waiting room with finite or infinite capacity. Arriving customers may be blocked at one of the queues depending on whether all servers and/or waiting positions are occupied. Blocked customers from the first queue can overflow to the second queue according to specific overflow routines. Using a separation method for the balance equations of the two-dimensional server and waiting room demand process, we reduce the dimension of the problem of solving these balance equations substantially. We extend the existing results in the literature in three directions. Firstly, we allow different service rates at the two queues. Secondly, the overflow stream is weighted with a parameter p ∈ [0,1], i.e., an arriving customer who is blocked and overflows, joins the overflow queue with probability p and leaves the system with probability 1 − p. Thirdly, we consider several new blocking and overflow routines. An erratum to this article can be found at     

Single line queue with repeated demands

We analyze a model of a queueing system in which customers can only call in to request service: if the server is free, the customer enters service immediately, but if the service system is occupied, the unsatisfied customer must break contact and reinitiate his request later. Such a customer is said to be in “orbit”. In this paper we consider three models characterized by the discipline governing the order of re-request of service from orbit. First, all customers in orbit can reapply, but are discouraged and reduce their rate of demand as more customers join the orbit. Secondly, the FCFS discipline operates for the unsatisfied customers in orbit. Finally, the LCFS discipline governs the customers in orbit and the server takes an exponentially distributed vacation after each service is completed. We calculate several characteristics quantities of such systems, assuming a general service-time distribution and different exponential distributions for the times between arrivals of first and repeat requests.     

MAP/(PH/PH)/c Queue with Self-Generation of Priorities and Non-Preemptive Service

Abstract

Customers arriving according to a Markovian arrival process are served at a c server facility. Waiting customers generate into priority while waiting in the system (self-generation of priorities), at a constant rate γ; such a customer is immediately taken for service, if at least one of the servers is free. Else it waits at a waiting space of capacity c exclusively for priority generated customers, provided there is vacancy. A customer in service is not preempted to accommodate a priority generated customer. The service times of ordinary and priority generated customers follow distinct PH-distributions. It is proved that the system is always stable. We provide a numerical procedure to compute the optimal number of servers to be employed to minimize the loss to the system. Several performance measures are evaluated.     

Transient analysis of a two-heterogeneous servers queue with system disaster,server repair and customers’ impatience

A two-heterogeneous servers queue with system disaster, server failure and repair is considered. In addition, the customers become impatient when the system is down. The customers arrive according to a Poisson process and service time follows exponential distribution. Each customer requires exactly one server for its service and the customers select the servers on fastest server first basis. Explicit expressions are derived for the time-dependent system size probabilities in terms of the modified Bessel function, by employing the generating function along with continued fraction and the identity of the confluent hypergeometric function. Further, the steady-state probabilities of the number of customers in the system are deduced and finally some important performance measures are obtained.     

Bounding the performance of tandem queues with finite buffer spaces

We consider a queueing system with three single servers in tandem with two intermediate buffer storages of finite capacity. The processing times are exponentially distributed and the first server has unlimited number of customers in front of it. Using a negative dependence property between the number of customers at the first and second buffer storages we show that a popular form of decomposition approach applied to this model, indeed, provides a lower bound for its performance. The approach used here to establish the bound is new and could be extended to establish bounds for other types of tandem queues with finite buffer spaces.     

Analysis of a finite buffer model with two servers and two nonpreemptive priority classes

In this paper, we analyze a finite buffer queueing model with two servers and two nonpreemptive priority service classes. The arrival streams are independent Poisson processes, and the service times of the two classes are exponentially distributed with different means. One of the two servers is reserved exclusively for one class with high priority and the other server serves the two classes according to a nonpreemptive priority service schedule. For the model, we describe its dynamic behavior by a four-dimensional continuous-time Markov process. Applying recursive approaches we present the explicit representation for the steady-state distribution of this Markov process. Then, we calculate the Laplace–Stieltjes Transform and the steady-state distribution of the actual waiting times of two classes of customers. We also give some numerical comparison results with other queueing models.     

A Discrete-Time Single-Server Queueing System Under Multiple Vacations and Setup-Closedown Times

Abstract

This article concerns a Geo/G/1/∞ queueing system under multiple vacations and setup-closedown times. Specifically, the operation of the system is as follows. After each departure leaving an empty system, the server is deactivated during a closedown time. At the end of each closedown time, if at least a customer is present in the system, the server begins the service of the customers (is reactivated) without setup; however, if the system is completely empty, the server takes a vacation. At the end of each vacation, if there is at least a customer in the system, the server requires a startup time (is reactivated) before beginning the service of the customers; nevertheless, if there are not customers waiting in the system, the server takes another vacation. By applying the supplementary variable technique, the joint generating function of the server state and the system length together with the main performance measures are derived. We also study the length of the different busy periods of the server. The stationary distributions of the time spent waiting in the queue and in the system under the FCFS discipline are analysed too. Finally, a cost model with some numerical results is presented.     

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.     

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.     

A server backup model with Markovian arrivals and phase type services

We consider a finite capacity queueing system with one main server who is supported by a backup server. We assume Markovian arrivals, phase type services, and a threshold-type server backup policy with two pre-determined lower and upper thresholds. A request for a backup server is made whenever the buffer size (number of customers in the queue) hits the upper threshold and the backup server is released from the system when the buffer size drops to the lower threshold or fewer at a service completion of the backup server. The request time for the backup server is assumed to be exponentially distributed. For this queuing model we perform the steady state analysis and derive a number of performance measures. We show that the busy periods of the main and backup servers, the waiting times in the queue and in the system, are of phase type. We develop a cost model to obtain the optimal threshold values and study the impact of fixed and variable costs for the backup server on the optimal server backup decisions. We show that the impact of standard deviations of the interarrival and service time distributions on the server backup decisions is quite different for small and large values of the arrival rates. In addition, the pattern of use of the backup server is very different when the arrivals are positively correlated compared to mutually independent arrivals.