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.     

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

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.     

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

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     

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 basically poisson queue with nonpoisson output

The output of the queueing system M/M/1 is well known to be Poisson. This has also been shown to be true for other more general models inclusive of M/M_n/1; the system in which arrivals and epochs of service completion are elements of a birth and death process with parameters Λ and nμ, respectively, when the system contains n ≥ 1 customers. We shall here show that this result is not true in M_nM/1; a system where arrival parameter is state dependent quantity Λ/n+1. Expressions will be given for the steady state joint density of two consecutive output intervals as well as the coefficient of correlation between them.     

Individual headstart strategies for combating congestion

This paper examines the process by which a user of a queueing system selects his arrival time to the system to compensate for unpredictable delays in the system if he wishes to complete service at a particular time. Considering the case in which all the system users have already decided on their arrival times to the system and will not change these times, this paper investigates how a new user of this system develops his strategy for selecting his arrival time. The distribution of this customer's arrival time is then obtained for a special case.     

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.     

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.     

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     

On a single-server queue with state-dependent service

This paper discusses a class of queueing models in which the service time of a customer al a single server facility is dependent on the queue size at the onset of its service. The Laplace transform for the wait in queue distribution is derived and the utilization of the server is given when the arrival is a homogeneous Poisson process.     

Queues with stochastic service rates

The purpose of this paper is to explore an extension of the output discipline for the Poisson input, general output, single channel, first-come, first-served queueing system. The service time parameter, μ, is instead considered a random variable, M. In other words, the service time random variable, T, is to be conditioned by a parameter random variable, M. Therefore, if the distribution function of M is denoted by F_M(μ) and the known conditional service time distribution as B(t |_μ), then the unconditional service distribution is given by B(t) = Pr {T ≤ t}. = ∫_-∞^∞ B(t |_μ) dF_M(μ). Results are obtained that characterize queue size and waiting time using the imbedded Markov chain approach. Expressions are derived for the expected queue length and Laplace-Stieltjes transforms of the steady-state waiting time when conditional service times are exponential. More specific results are found for three special distributions of M: (1) uniform on [1.2]; (2) two-point; and (3) gamma.     

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.     

一个具有相互独立、不同分布服务时间序列的排队模型

讨论的排队模型 ,放宽了GI/G/1系统中“服务时间独立同分布”的限制 ,只要求各服务时间相互独立 ,因而较GI/G/1排队模型能更合理地拟合实际问题 .在此较宽的条件下 ,利用补充变量的方法 ,求得了该排队系统队长的瞬时分布     

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.     

Markov chain analyses of multiprogrammed computer systems

Most operating systems for large computing facilities involve service disciplines which base, to some extent, the sequencing of object program executions on the amount of running time they require. It is the object of this paper to study mathematical models of such service disciplines applicable to both batch and time-shared processing systems. In particular, Markov queueing models are defined and analyzed for round-robin and foreground-background service disciplines. With the round-robin discipline, the service facility processes each program or job for a maximum of q seconds; if the program's service is completed during this quantum, it leaves the system, otherwise it returns to the end of the waiting line to await another quantum of service. With the foreground-background discipline each new arrival joins the end of the foreground queue and awaits a single quantum of service. If it requires more it is subsequently placed at the end of the background queue which is allocated service only when the foreground queue is empty. The analysis focuses on the efficiency of the above systems by assuming a swap or set-up time (overhead cost) associated with the switching of programs on and off the processor. The analysis leads to generating functions for the equilibrium queue length probabilities, the moments of this latter distribution, and measures of mean waiting times. The paper concludes with a discussion of the results along with several examples.     

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.