Stochastic analysis of a single server retrial queue with general retrial times

Retrial queueing systems are widely used in teletraffic theory and computer and communication networks. Although there has been a rapid growth in the literature on retrial queueing systems, the research on retrial queues with nonexponential retrial times is very limited. This paper is concerned with the analytical treatment of an M/G/1 retrial queue with general retrial times. Our queueing model is different from most single server retrial queueing models in several respectives. First, customers who find the server busy are queued in the orbit in accordance with an FCFS (first‐come‐first‐served) discipline and only the customer at the head of the queue is allowed for access to the server. Besides, a retrial time begins (if applicable) only when the server completes a service rather upon a service attempt failure. We carry out an extensive analysis of the queue, including a necessary and sufficient condition for the system to be stable, the steady state distribution of the server state and the orbit length, the waiting time distribution, the busy period, and other related quantities. Finally, we study the joint distribution of the server state and the orbit length in non‐stationary regime. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 561–581, 1999     

The queue G/M/m/N: Busy period and cycle,waiting time under reverse and random order service

The busy period, busy cycle, and the numbers of customers served and lost therein, of the G/M/m queue with balking is studied via the embedded Markov chain approach. It is shown that the expectations of the two discrete variables give the loss probability. For the special case G/M/1/N a closed expression in terms of contour integrals is obtained for the Laplace transform of these four variables. This yields as a byproduct the LIFO waiting time distribution for the G/M/m/N queue. The waiting time under random order service for this queue is also studied.     

A note on sojourn times in M/G/1 queues with instantaneous,bernoulli feedback

Queueing systems which include the possibility for a customer to return to the same server for additional service are called queueing systems with feedback. Such systems occur in computer networks for example. In these systems a chosen customer will wait in the queue, be serviced and then, with probability p, return to wait again, be serviced again and continue this process until, with probability (1 – p) = q, it departs the system never to return. The time of waiting plus service time, the nth time the customer goes through, we will call his nth sojourn time. The (random) sum of these sojourn times we will call the total sojourn time (abbreviated, sojourn time when there is no confusion which sojourn time we are talking about). In this paper we study the total sojourn time in a queueing system with feedback. We give the details for M/G/1 queues in which the decision to feedback or not is a Bernoulli process. While the details of the computations can be more difficult, the structure of the sojourn time process is unchanged for the M/G/1 queue with a more general decision process as will be shown. We assume the reader is familiar with Disney, McNickle and Simon [1].     

A queueing system with vacations after N services

This article is devoted to the study of an M/G/1 queue with a particular vacation discipline. The server is due to take a vacation as soon as it has served exactly N customers since the end of the previous vacation. N may be either a constant or a random variable. If the system becomes empty before the server has served N customers, then it stays idle until the next customer arrival. Such a vacation discipline arises, for example, in production systems and in order picking in warehouses. We determine the joint transform of the length of a visit period and the number of customers in the system at the end of that period. We also derive the generating function of the number of customers at a random instant, and the Laplace–Stieltjes transform of the delay of a customer. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 646–658, 2015     

Computational analysis of MMAP[K]/PH[K]/1 queues with a mixed FCFS and LCFS service discipline

This paper studies a queueing system with a Markov arrival process with marked arrivals and PH‐distribution service times for each type of customer. Customers (regardless of their types) are served on a mixed first‐come‐first‐served (FCFS) and last‐come‐first‐served (LCFS) nonpreemptive basis. That is, when the queue length is N (a positive integer) or less, customers are served on an FCFS basis; otherwise, customers are served on an LCFS basis. The focus is on the stationary distribution of queue strings, busy periods, and waiting times of individual types of customers. A computational approach is developed for computing the stationary distribution of queue strings, the mean of busy period, and the means and variances of waiting times. The relationship between these performance measures and the threshold number N is analyzed in depth numerically. It is found that the variance of the virtual (actual) waiting time of an arbitrary customer can be reduced by increasing N. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 399–421, 2000     

On queues with dependent interarrival and service times

AnM/G/1 queueing system is studied in which the service time required by a customer is dependent on the interarrival time between his arrival and that of his predecessor Assuming the two variables are “associated,” we prove that the expected delay in this system is less than or equal to than of a conventional M/G/1 queue This conclusion has been verified via simulation by Mitchell and Paulson [9] for a special class of dependent M/M/1 queue. Their model is a special case of the one we consider here. We also study another modified GI/G/1 queue. where the arrival process and/or the service process are individually “associated”.     

Optimal admission pricing policies for M/Ek/1 queues

This paper extends the Low-Lippman M/M/1 model to the case of Gamma service times. Specifically, we have a queue in which arrivals are Poisson, service time is Gamma-distributed, and the arrival rate to the system is subject to setting an admission fee p. The arrival rate λ(p) is non-increasing in p. We prove that the optimal admission fee p^* is a non-decreasing function of the customer work load on the server. The proof is for an infinite capacity queue and holds for the infinite horizon continuous time Markov decision process. In the special case of exponential service time, we extend the Low-Lippman model to include a state-dependent service rate and service cost structure (for finite or infinite time horizon and queue capacity). Relatively recent dynamic programming techniques are employed throughout the paper. Due to the large class of functions represented by the Gamma family, the extension is of interest and utility.     

Optimal policies for M/M/m queue with two different kinds of (N,T)‐policies

In this paper, two different kinds of (N, T)‐policies for an M/M/m queueing system are studied. The system operates only intermittently and is shut down when no customers are present any more. A fixed setup cost of K > 0 is incurred each time the system is reopened. Also, a holding cost of h > 0 per unit time is incurred for each customer present. The two (N, T)‐policies studied for this queueing system with cost structures are as follows: (1) The system is reactivated as soon as N customers are present or the waiting time of the leading customer reaches a predefined time T, and (2) the system is reactivated as soon as N customers are present or the time units after the end of the last busy period reaches a predefined time T. The equations satisfied by the optimal policy (N*, T*) for minimizing the long‐run average cost per unit time in both cases are obtained. Particularly, we obtain the explicit optimal joint policy (N*, T*) and optimal objective value for the case of a single server, the explicit optimal policy N* and optimal objective value for the case of multiple servers when only predefined customers number N is measured, and the explicit optimal policy T* and optimal objective value for the case of multiple servers when only predefined time units T is measured, respectively. These results partly extend (1) the classic N or T policy to a more practical (N, T)‐policy and (2) the conclusions obtained for single server system to a system consisting of m (m ≥ 1) servers. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 240–258, 2000     

An M/M/1 queue with delayed feedback

We present some results for M/M/1 queues with finite capacities with delayed feedback. The delay in the feedback to an M/M/1 queue is modelled as another M-server queue with a finite capacity. The steady state probabilities for the two dimensional Markov process {N(t), M(t)} are solved when N(t) = queue length at server 1 at t and M(t) = queue length at server 2 at t. It is shown that a matrix operation can be performed to obtain the steady state probabilities. The eigenvalues of the operator and its eigenvectors are found. The problem is solved by fitting boundary conditions to the general solution and by normalizing. A sample problem is run to show that the solution methods can be programmed and meaningful results obtained numerically.     

Waiting time analysis for a queueing system with time‐limited service and exponential timer

We consider a single‐queue with exhaustive or gated time‐limited services and server vacations, in which the length of each service period at the queue is controlled by a timer, i.e., the server serves customers until the timer expires or the queue becomes empty, whichever occurs first, and then takes vacations. The customer whose service is interrupted due to the timer expiration may be attended according to nonpreemptive or preemptive service disciplines. For the M/G/1 exhaustive/gated time‐limited service queueing system with an exponential timer and four typical preemptive/nonpreemptive service disciplines, we derive the Laplace—Stieltjes transforms and the moment formulas for waiting times and sojourn times through a unified approach, and provide some new results for these time‐limited service disciplines. © John Wiley & Sons, Inc. Naval Research Logistics 48: 638–651, 2001.     

Statistical tests for exponential service from m/g/1 waiting-time data

From an original motivation in quantitative inventory modeling, we develop methods for testing the hypothesis that the service times of an M/G/1 queue are exponentially distributed, given a sequence of observations of customer line and/or system waits. The approaches are mostly extensions of the well-known exponential goodness-of-fit test popularized by Gnedenko, which results from the observation that the sum of a random exponential sample is Erlang distributed and thus that the quotient of two independent exponential sample means is F distributed.     

Decentralized admission control of a queueing system: A game‐theoretic model

Consider a distributed system where many gatekeepers share a single server. Customers arrive at each gatekeeper according to independent Poisson processes with different rates. Upon arrival of a new customer, the gatekeeper has to decide whether to admit the customer by sending it to the server, or to block it. Blocking costs nothing. The gatekeeper receives a reward after a customer completes the service, and incurs a cost if an admitted customer finds a busy server and therefore has to leave the system. Assuming an exponential service distribution, we formulate the problem as an n‐person non‐zero‐sum game in which each gatekeeper is interested in maximizing its own long‐run average reward. The key result is that each gatekeeper's optimal policy is that of a threshold type regardless what other gatekeepers do. We then derive Nash equilibria and discuss interesting insights. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 702–718, 2003.     

Arrival and departure state distributions in the general bulk‐service queue

In this paper, we give an explicit relation between steady‐state probability distributions of the buffer occupancy at customer entrance and departure epochs, for the classical single‐server system G/G^[N]/1 with batch services and for the finite capacity case. The method relies on level‐crossing arguments. For the particular case of Poisson input, we also express the loss probability in terms of state probabilities at departure epochs, yielding probabilities observed by arriving customers. This work provides the “bulk queue” version of a result established by Burke, who stated the equality between probabilities at arrival and departure epochs for systems with “unit jumps.” © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 107–118, 1999     

An M/M/1 queue with a general bulk service rule

A model of an M/M/1, bulk queue with service rates dependent on the batch size is developed. The operational policy is to commence service when at least L customers are available with a maximum batch size of K. Arriving customers are not allowed to join in-process service. The solution procedure utilizes the matrix geometric methodology and reduces to obtaining the inverse of a square matrix of dimension K + 1 - L. For the case where the service rates are not batch size dependent, the limiting probabilities can be written in closed form. A numerical example illustrates the variability of the system cost as a function of the minimum batch service size L.     

The single server queue in discrete time-numerical analysis IV

The nonlinear difference equation for the distribution of the busy period for an unbounded discrete time queue of M|G| 1 type is solved numerically by a monotone iterative procedure. A starting solution is found by computing a first passage time distribution in a truncated version of the queue.     

Customer delays in M/M/c repair systems with spares

A service center to which customers bring failed items for repair is considered. The items are exchangeable in the sense that a customer is ready to take in return for the failed item he brought to the center any good item of the same kind. This exchangeability feature makes it possible for the service center to possess spares. The focus of the article is on customer delay in the system—the time that elapses since the arrival of a customer with a failed item and his departure with a good one—when repaired items are given to waiting customers on a FIFO basis. An algorithm is developed for the computation of the delay distribution when the item repair system operates as an M/M/c queue.     

A sequential scheduling problem with impatient jobs

There are n customers that need to be served. Customer i will only wait in queue for an exponentially distributed time with rate λ_i before departing the system. The service time of customer i has distribution F_i, and on completion of service of customer i a positive reward r_i is earned. There is a single server and the problem is to choose, after each service completion, which currently in queue customer to serve next so as to maximize the expected total return. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 659–663, 2015     

A single server queue with arrival rate dependent on server breakdowns

This paper considers a single server queueing system that alternates stochastically between two states: operational and failed. When operational, the system functions as an M/E_k/1 queue. When the system is failed, no service takes place but customers continue to arrive according to a Poisson process; however, the arrival rate is different from that when the system is operational. The durations of the operating and failed periods are exponential with mean 1/cβ and Erlang with mean 1/cβ, respectively. Generating functions are used to derive the steady-state quantities L and W, both of which, when viewed as functions of c, decrease at a rate inversely proportional to c². The paper includes an analysis of several special and extreme cases and an application to a production-storage system.     

Estimation in single server queues

Moment and maximum likelihood estimates (m.l.e.'s) arc investigated for nonparametric and parametric models for a single server queue observed over a random time horizon, namely, up to the nth departure epoch. Also. m.l.e's of the mean interarrival time and mean service time in anM/M/1 queue observed over a fixed time-interval are studied Limit distributions of these estimates are obtained Without imposing steady state assumptions on the queue-size or waiting time processes.     

Equilibrium customer strategies and social–profit maximization in the single‐server constant retrial queue

We consider the single‐server constant retrial queue with a Poisson arrival process and exponential service and retrial times. This system has not waiting space, so the customers that find the server busy are forced to abandon the system, but they can leave their contact details. Hence, after a service completion, the server seeks for a customer among those that have unsuccessfully applied for service but left their contact details, at a constant retrial rate. We assume that the arriving customers that find the server busy decide whether to leave their contact details or to balk based on a natural reward‐cost structure, which incorporates their desire for service as well as their unwillingness to wait. We examine the customers' behavior, and we identify the Nash equilibrium joining strategies. We also study the corresponding social and profit maximization problems. We consider separately the observable case where the customers get informed about the number of customers waiting for service and the unobservable case where they do not receive this information. Several extensions of the model are also discussed. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011