Optimal admission pricing and service rate control of an M[x]/M/s queue with reneging

In this article we consider the optimal control of an M^[X]/M/s queue, s ≧ 1. In addition to Poisson bulk arrivals we incorporate a reneging function. Subject to control are an admission price p and the service rate μ. Thus, through p, balking response is induced. When i customers are present a cost h(i,μ,p) per unit time is incurred, discounted continuously. Formulated as a continuous time Markov decision process, conditions are given under which the optimal admission price and optimal service rate are each nondecreasing functions of i. In Section 4 we indicate how the infinite state space may be truncated to a finite state space for computational purposes.     

The effect of prior assumptions on the expected cost of m/m/1 queueing systems with unknown arrival rate

In this study we deal with the determination of optimal service rate in an M/M/1 queue. The arrival rate is unknown and assumed to be a random variable with a known distribution function. Holding and operating costs are considered and service rate is determined to minimize total expected discounted costs for infinite horizon. The effects of the arrival rate's distribution properties on the characteristics of the system are examined.     

Some properties of optimal control policies for entry to an M/M/1 queue

Customers served by an M/M/1 queueing system each receive a reward R but pay a holding cost of C per unit time (including service time) spent in the system. The decision of whether or not a customer joins the queue can be made on an individual basis or a social basis. The effect of increasing the arrival rate on the optimal policy parameters is examined. Some limiting results are also derived.     

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”.     

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].     

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.     

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.     

Waiting time analysis of the M/G/1 queue with finite retrial group

We consider an M/G/1 retrial queue with finite capacity of the retrial group. First, we obtain equations governing the dynamic of the waiting time. Then, we focus on the numerical inversion of the density function and the computation of moments. These results are used to approximate the waiting time of the M/G/1 queue with infinite retrial group for which direct analysis seems intractable. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

A heterogeneous arrival and service queueing loss model

Consider a single-server exponential queueing loss system in which the arrival and service rates alternate between the paris (γ₁, γ₁), and (γ₂, μ₂), spending an exponential amount of time with rate cμ_i in (γ_i, μ_i), i = 1.2. It is shown that if all arrivals finding the server busy are lost, then the percentage of arrivals lost is a decreasing function of c. This is in line with a general conjecture of Ross to the effect that the “more nonstationary” a Poisson arrival process is, the greater the average customer delay (in infinite capacity models) or the greater the precentage of lost customers (in finite capacity models). We also study the limiting cases when c approaches 0 or infinity.     

The single server queue in discrete time-numerical analysis III

This paper deals with the stationary analysis of the finite, single server queue in discrete time. The following stntionary distributions and other quantities of practical interest are investigated: (1) the joint density of the queue length and the residual service time, (2) the queue length distribution and its mean, (3) the distribution of the residual service time and its mean, (4) the distribution and the expected value of the number of customers lost per unit of time due to saturation of the waiting capacity, (5) the distribution and the mean of the waiting time, (6) the asymptotic distribution of the queue length following departures The latter distribution is particularly noteworthy, in view of the substantial difference which exists, in general, between the distributions of the queue lengths at arbitrary points of time and those immediately following departures.     

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.     

On the busy period of the M/G/1 retrial queue

The M/G/1 queue with repeated attempts is considered. A customer who finds the server busy, leaves the service area and joins a pool of unsatisfied customers. Each customer in the pool repeats his demand after a random amount of time until he finds the server free. We focus on the busy period L of the M/G/1$ retrial queue. The structure of the busy period and its analysis in terms of Laplace transforms have been discussed by several authors. However, this solution has serious limitations in practice. For instance, we cannot compute the first moments of L by direct differentiation. This paper complements the existing work and provides a direct method of calculation for the second moment of L. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 115–127, 2000     

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.     

A finite capacity GI/PH/1 queue with group services

We consider a finite-capacity single-server queue in which arrivals occur one at a time, according to a renewal process. The successive service times are mutually independent and have a common phase-type distribution. The customers are served in groups of size at least L, a preassigned threshold value. Explicit analytic expressions for the steady-state queue-length densities at arrivals and at arbitrary time points, and the throughput of the system are obtained. The Laplace-Stieltjes transform of the stationary waiting-time distribution of an admitted customer at points of arrivals is computed. It is shown to be of phase type when the arrival process is also of phase type. Efficient algorithmic procedures for the steady-state analysis of the model are presented. These procedures are used in arriving at an optimal value for L that minimizes the mean waiting time of an admitted customer. A conjecture on the nature of the mean waiting time is proposed.     

On the behavior of the batch arrival queue Mx/M/1 during a busy period

The queue size process (^t)⁰≤^t≤^t0 of the batch arrival queue M^X/M/1 is studied under the condition that the duration of its busy period is larger than t⁰. Explicit formulas for the transition probabilities are given and the limiting Markov process for t⁰ → ∞ is investigated. Several properties of this process are considered. Its transition probabilities and moments and the distribution of its minimum are derived and a functional limit theorem for the rescaled process is proved. © 1994 John Wiley & Sons, Inc.     

Optimal control of entry to an M/Ek/1 queue serving several classes of customers

The individual and social optimum control policies for entry to an M/M//1 queue serving several classes of customers have been shown to be control-limit policies. The technique of policy iteration provides the social optimum policy for such a queue in a straightforward manner. In this article, the problem of finding the optimal control policy for the M/E_k/1 system is solved, thereby expanding the potential applicability of the solutions developed. The Markovian nature of the queueing system is preserved by considering the service as having k sequential phases, each with independent, identically distributed, exponential service times, through which a customer must pass to be serviced. The optimal policy derived by policy iteration for such a system is likely to be difficult to use because it requires knowledge of the number of phases rather than customers in the system when an arrival occurs. To circumvent this difficulty, a heuristic is used to find a good usable (implementable) solution. In addition, a mixed-integer program is developed which yields the optimal implementable solution when solved.     

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.     

Approximation for the departure process of a queue in a network

A simple renewal process is identified to approximate the complex departure process of a queue often found in queueing network models. The arrival process to the queue is the superposition or merging of several independent component-renewal processes that are approximations of departure processes from other queues and external arrival processes; there is a single server with exponential service times, and the waiting space is infinite. The departure process of this queue is of interest because it is the arrival process to other queues in the network. The approximation proposed is a hybrid; the mean and variance of the approximating departure intervals is a weighted average of those determined by basic methods in Whitt [41] with the weighting function empirically determined using simulation. Tandem queueing systems with superposition arrival processes and exponential service times are used to evaluate the approximation. The departure process of the first queue in the tandem is approximated by a renewal process, the tandem system is replaced by two independent queues, and the second queue is solved analytically. When compared to simulation estimates, the average absolute error in hybrid approximations of the expected number in the second queue is 6%, a significant improvement over 22–41% in the basic methods.     

Waiting times for M/G/1 queues with service-time or delay-dependent server vacations

This article shows how to determine the stationary distribution of the virtual wait in M/G/1 queues with either one-at-a-time or exhaustive server vacations, depending on either service times or accrued workload. For the first type of dependence, each vacation time is a function of the immediately preceding service time or of whether the server finds the system empty after returning from vacation. In this way, it is possible to model situations such as long service times followed by short vacations, and vice versa. For the second type of dependence, the vacation time assigned to an arrival to follow its service is a function of the level of virtual wait reached. By this device, we can model situations in which vacations may be shortened whenever virtual delays have gotten excessive. The method of analysis employs level-crossing theory, and examples are given for various cases of service and vacation-time distributions. A closing discussion relates the new model class to standard M/G/1 queues where the service time is a sum of variables having complex dependencies. © 1992 John Wiley & Sons, Inc.