Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic

We address a rate control problem associated with a single server Markovian queueing system with customer abandonment in heavy traffic. The controller can choose a buffer size for the queueing system and also can dynamically control the service rate (equivalently the arrival rate) depending on the current state of the system. An infinite horizon cost minimization problem is considered here. The cost function includes a penalty for each rejected customer, a control cost related to the adjustment of the service rate and a penalty for each abandoning customer. We obtain an explicit optimal strategy for the limiting diffusion control problem (the Brownian control problem or BCP) which consists of a threshold-type optimal rejection process and a feedback-type optimal drift control. This solution is then used to construct an asymptotically optimal control policy, i.e. an optimal buffer size and an optimal service rate for the queueing system in heavy traffic. The properties of generalized regulator maps and weak convergence techniques are employed to prove the asymptotic optimality of this policy. In addition, we identify the parameter regimes where the infinite buffer size is optimal.     

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.     

An M/G/1 queue with two phases of service subject to the server breakdown and delayed repair

This paper deals with the steady-state behaviour of an M/G/1 queue with an additional second phase of optional service subject to breakdowns occurring randomly at any instant while serving the customers and delayed repair. This model generalizes both the classical M/G/1 queue subject to random breakdown and delayed repair as well as M/G/1 queue with second optional service and server breakdowns. For this model, we first derive the joint distributions of state of the server and queue size, which is one of chief objectives of the paper. Secondly, we derive the probability generating function of the stationary queue size distribution at a departure epoch as a classical generalization of Pollaczek–Khinchin formula. Next, we derive Laplace Stieltjes transform of busy period distribution and waiting time distribution. Finally, we obtain some important performance measures and reliability indices of this model.     

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

Notes of M/G/1 system under the {\langle p, T \rangle} policy with second optional service

We optimize the operating cost of the ${\langle p, T \rangle}We optimize the operating cost of the áp, T ?{\langle p, T \rangle} policy for an M/G/1 queueing system with second optional service, where the customer may depart from the system either after the first essential service with probability 1 − r or at the end of the first service may immediately go for a second service with probability r. Moreover, the server takes a vacation of fixed length T if the system becomes empty. If customers are found in the queue after T time units have elapsed since the end of the busy period, the server reactivates with probability p or leaves for a vacation of the same length T with probability 1 − p. Alternatively, if no customers present in the queue upon returning from the vacation, the server leaves for another a vacation of the same length. We call this áp, T ?{\langle p, T \rangle} policy. The total expected cost function per unit time is developed to determine the optimal thresholds of p and T at a minimum cost. Based on the optimal cost the explicit form for joint optimum values of p and T are obtained.     

Comparison of two randomized policy M/G/1 queues with second optional service, server breakdown and startup

The problem addressed in this paper is to compare the minimum cost of the two randomized control policies in the M/G/1 queueing system with an unreliable server, a second optional service, and general startup times. All arrived customers demand the first required service, and only some of the arrived customers demand a second optional service. The server needs a startup time before providing the first required service until the system becomes empty. After all customers are served in the queue, the server immediately takes a vacation and the system operates the (T, p)-policy or (p, N)-policy. For those two policies, the expected cost functions are established to determine the joint optimal threshold values of (T, p) and (p, N), respectively. In addition, we obtain the explicit closed form of the joint optimal solutions for those two policies. Based on the minimal cost, we show that the optimal (p, N)-policy indeed outperforms the optimal (T, p)-policy. Numerical examples are also presented for illustrative purposes.     

Convergence of a queueing system in heavy traffic with general patience-time distributions

We analyze a sequence of single-server queueing systems with impatient customers in heavy traffic. Our state process is the offered waiting time, and the customer arrival process has a state dependent intensity. Service times and customer patient-times are independent; i.i.d. with general distributions subject to mild constraints. We establish the heavy traffic approximation for the scaled offered waiting time process and obtain a diffusion process as the heavy traffic limit. The drift coefficient of this limiting diffusion is influenced by the sequence of patience-time distributions in a non-linear fashion. We also establish an asymptotic relationship between the scaled version of offered waiting time and queue-length. As a consequence, we obtain the heavy traffic limit of the scaled queue-length. We introduce an infinite-horizon discounted cost functional whose running cost depends on the offered waiting time and server idle time processes. Under mild assumptions, we show that the expected value of this cost functional for the n-th system converges to that of the limiting diffusion process as n tends to infinity.     

An M/G/1 queue under hysteretic vacation policy with an early startup and un-reliable server

This paper considers the bi-level control of an M/G/1 queueing system, in which an un-reliable server operates N policy with a single vacation and an early startup. The server takes a vacation of random length when he finishes serving all customers in the system (i.e., the system is empty). Upon completion of the vacation, the server inspects the number of customers waiting in the queue. If the number of customers is greater than or equal to a predetermined threshold m, the server immediately performs a startup time; otherwise, he remains dormant in the system and waits until m or more customers accumulate in the queue. After the startup, if there are N or more customers waiting for service, the server immediately begins serving the waiting customers. Otherwise the server is stand-by in the system and waits until the accumulated number of customers reaches or exceeds N. Further, it is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. We obtain the probability generating function in the system through the decomposition property and then derive the system characteristics     

Optimal control of the N policy M/G/1 queueing system with server breakdowns and general startup times

This paper deals with an N policy M/G/1 queueing system with a single removable and unreliable server whose arrivals form a Poisson process. Service times, repair times, and startup times are assumed to be generally distributed. When the queue length reaches N(N ? 1), the server is immediately turned on but is temporarily unavailable to serve the waiting customers. The server needs a startup time before providing service until there are no customers in the system. We analyze various system performance measures and investigate some designated known expected cost function per unit time to determine the optimal threshold N at a minimum cost. Sensitivity analysis is also studied.     

Cost optimization of a repairable M/G/1 queue with a randomized policy and single vacation

This paper deals with the (p, N)-policy M/G/1 queue with an unreliable server and single vacation. Immediately after all of the customers in the system are served, the server takes single vacation. As soon as N customers are accumulated in the queue, the server is activated for services with probability p or deactivated with probability (1 − p). When the server returns from vacation and the system size exceeds N, the server begins serving the waiting customers. If the number of customers waiting in the queue is less than N when the server returns from vacation, he waits in the system until the system size reaches or exceeds N. It is assumed that the server is subject to break down according to a Poisson process and the repair time obeys a general distribution. This paper derived the system size distribution for the system described above at a stationary point of time. Various system characteristics were also developed. We then constructed a total expected cost function per unit time and applied the Tabu search method to find the minimum cost. Some numerical results are also given for illustrative purposes.     

Optimal strategy policy in batch arrival queue with server breakdowns and multiple vacations

This paper considers a like-queue production system in which server vacations and breakdowns are possible. The decision-maker can turn a single server on at any arrival epoch or off at any service completion. We model the system by an M^[x]/M/1 queueing system with N policy. The server can be turned off and takes a vacation with exponential random length whenever the system is empty. If the number of units waiting in the system at any vacation completion is less than N, the server will take another vacation. If the server returns from a vacation and finds at least N units in the system, he immediately starts to serve the waiting units. It is assumed that the server breaks down according to a Poisson process and the repair time has an exponential distribution. We derive the distribution of the system size through the probability generating function. We further study the steady-state behavior of the system size distribution at random (stationary) point of time as well as the queue size distribution at departure point of time. Other system characteristics are obtained by means of the grand process and the renewal process. Finally, the expected cost per unit time is considered to determine the optimal operating policy at a minimum cost. The sensitivity analysis is also presented through numerical experiments.     

An MAP/G/1 G-queues with preemptive resume and multiple vacations

In this paper, we consider an MAP/G/1 G-queues with possible preemptive resume service discipline and multiple vacations wherein the arrival process of negative customers is Markovian arrival process (MAP). The arrival of a negative customer may remove the customer being in service. The server leaves for a vacation as soon as the system empties and is allowed to take repeated (multiple) vacations. The service and vacation times are arbitrarily distributed. We obtain the queue length distributions with the method of supplementary variables, combined with the matrix-analytic method and censoring technique. We also obtain the mean of the busy period based on the renewal theory. Finally we provide expressions for a special case.     

Optimization and sensitivity analysis of controlling arrivals in the queueing system with single working vacation

This paper analyzes the F-policy M/M/1/K queueing system with working vacation and an exponential startup time. The F-policy deals with the issue of controlling arrivals to a queueing system, and the server requires a startup time before allowing customers to enter the system. For the queueing systems with working vacation, the server can still provide service to customers rather than completely stop the service during a vacation period. The matrix-analytic method is applied to develop the steady-state probabilities, and then obtain several system characteristics. We construct the expected cost function and formulate an optimization problem to find the minimum cost. The direct search method and Quasi-Newton method are implemented to determine the optimal system capacity K, the optimal threshold F and the optimal service rates (μ_B,μ_V) at the minimum cost. A sensitivity analysis is conducted to investigate the effect of changes in the system parameters on the expected cost function. Finally, numerical examples are provided for illustration purpose.     

Steady state analysis of an M/G/1 queue with two phase service and Bernoulli vacation schedule under multiple vacation policy

This paper examines the steady state behaviour of a batch arrival queue with two phases of heterogeneous service along and Bernoulli schedule vacation under multiple vacation policy, where after two successive phases service or first vacation the server may go for further vacations until it finds a new batch of customer in the system. We carry out an extensive stationary analysis of the system, including existence of stationary regime, queue size distribution of idle period process, embedded Markov chain steady state distribution of stationary queue size, busy period distribution along with some system characteristics.     

Dynamic Routing and Admission Control in High-Volume Service Systems: Asymptotic Analysis via Multi-Scale Fluid Limits

Motivated by applications in telephone call centers, we consider a service system model with m customer classes and r server pools. The model is one with doubly stochastic arrivals, which means that the m-vector λ of instantaneous arrival rates is allowed to vary both temporally and stochastically. Two levels of dynamic control are considered: customers may be either blocked or accepted at the time of their arrival, and then accepted customers of each class must be routed, either immediately upon acceptance or after some period of waiting, to a server pool that is qualified to handle that class. Customers who are made to wait before commencement of their service are liable to defect. The objective is to minimize the expected sum of blocking costs, waiting costs and defection costs over a fixed and finite planning horizon. We consider an asymptotic parameter regime in which (i) the arrival rates, service rates and defection rates are uniformly accelerated by a large factor κ, then (ii) arrival rates are increased by an additional factor g(κ), and the number of servers in each pool is increased by g(κ) as well. This produces a separation of time scales, justifying a pointwise stationary stochastic fluid approximation for our original system model. In the stochastic fluid approximation, optimal admission control and routing decisions are determined by a simple linear program that uses the current arrival rate vector λ as data. We explain how to implement the fluid model's optimal control policy in our original service system context, and prove that the proposed implementation is asymptotically optimal in the first-order sense. AMS subject classification: 60K30, 90B15, 90B36