A queueing system with random server capacity and multiple control

The authors study queueing, input and output processes in a queueing system with bulk service and state dependent service delay. The input flow of customers, modulated by a semi-Markov process, is served by a single server that takes batches of a certain fixed size if available or waits until the queue accumulates enough customers for service. In the latter case, the batch taken for service is of random size dependent on the state of the system, while service duration depends both on the state of the system and on the batch size taken. The authors establish a necessary and sufficient condition for equilibrium of the system and obtain the following results: Explicit formulas for steady state distribution of the queueing process, intensity of the input and output processes, and mean values of idle and busy periods. They employ theory of semi-regenerative processes and illustrate the results by a number of examples. In one of them an optimization problem is discussed.     

On the optimal control problem of a single-server queueing system

For a single-server queueing system (with a finite waiting room) with phase type arrivals and exponential service times, an optimal control for the service rate is derived. This generalizes the result of Scott and Jefferson for theM/M/1/1 queueing model.     

A semidefinite programming approach to the optimal control of a single server queueing system with imposed second moment constraints

Classical analyses of the dynamic control of multi-class queueing systems frequently yield simple priority policies as optimal. However, such policies can often result in excessive queue lengths for the low priority jobs/customers. We propose a stochastic optimisation problem in the context of a two class M/M/1 system which seeks to mitigate this through the imposition of constraints on the second moments of queue lengths. We analyse the performance of two families of parametrised heuristic policies for this problem. To evaluate these policies we develop lower bounds on the optimum cost through the achievable region approach. A numerical study points to the strength of performance of threshold policies and to directions for future research.     

On stochastic processes in a multilevel control bulk queueing system

This article analyzes some stochastic processes that arise in a bulk single server queue with continuously operating server, state dependent compound Poisson input flow and general state dependent service process. The authors treat the queueing process as a semi–regenerative process and obtain the invariant probability measure and the transient distribution for the embedded Markov chain. The stationary probability measure for the queueing process with continuous time parameter is found by using semi-regenerative techniques. The authors also study the input and output processes and establish ergodic theorems for some functionals of these processes. The results are obtained in terms of the invariant probability measure for the embedded process and the stationary measure for the queueing process with continuous time parameter     

On the optimal control of a single-server queueing system: Reply

This comment replies to a criticism due to Klein and Gruver (Ref. 1) of our earlier paper (Ref. 2) on the application of control theory to a queueing system. The criticism concerns the state-space diagram and the table which we inadvertently gave for the terminal-reward problem, albeit incorrectly labeled, rather than for the free-endpoint problem considered in our paper. We show that the solution given by Klein and Gruver is itself incorrect and nonoptimal.     

On the optimal control of a single-server queueing system: Comment

In a recent paper by Scott and Jefferson, the optimal control of the service rate for a single-server queue with limited waiting space is treated by the maximum principle. We show that their control policies are necessarily suboptimal. Characterizations for optimal control are derived and used to obtain corresponding optimal trajectories in both nonsingular and singular regions.     

Analysis of a time-limited service priority queueing system with exponential timer and server vacations

We consider a multi-class priority queueing system with a non-preemptive time-limited service controlled by an exponential timer and multiple (or single) vacations. By reducing the service discipline to the Bernoulli schedule, we obtain an expression for the Laplace-Stieltjes transform (LST) of the waiting time distribution via an iteration procedure, and a recursive scheme to calculate the first two moments. It is noted that we have to select embedded Markov points based on the service beginning epochs instead of the service completion epochs adopted for most of M/G/1 queueing analyses. Through the queue-length analysis, we obtain a decomposition form for the LST of the waiting time in each queue having the exhaustive service.      

On the optimal control of a single-server queueing system: Further remarks

This comment is in response to a reply by Scott and Jefferson (Ref. 3) concerning the application of control theory to a queueing problem.     

A single server queueing system with two phases of service subject to server breakdown and Bernoulli vacation

This paper deals with a single server M/G/1 queue with two phases of heterogeneous service and unreliable server. We assume that customers arrive to the system according to a Poisson process with rate λ. After completion of two successive phases of service the server either goes for a vacation with probability p(0 ? p ? 1) or may continue to serve the next unit, if any, with probability q(=1 ? p). Otherwise it remains in the system until a customer arrives. While the server is working with any phase of service, it may breakdown at any instant and the service channel will fail for a short interval of time. For this model, we first derive the joint distribution of state of the server and queue size, which is one of the chief objectives of the paper. Secondly, we derive the probability generating function of the stationary queue size distribution at a departure epoch. 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.     

Optimal server assignment in a two-stage tandem queueing system

We study Markovian queueing systems consisting of two stations in tandem. There is a dedicated server in each station and an additional server that can be assigned to any station. Assuming that linear holding costs are incurred by jobs in the system and two servers can collaborate to work on the same job, we determine structural properties of optimal server assignment policies under the discounted and the average cost criteria.     

Optimal control of a single server in a finite-population queueing network

We study the optimal dynamic assignment of a single server to multiple stations in a finite-population queueing network. The objective is to maximize the long-run average reward/throughput. We use sample-path comparisons to identify conditions on the network structure and service time distributions under which the optimal policy is an index policy. This index policy assigns the server to the non-empty station where it takes the shortest amount of time (in some stochastic sense) to complete a job. For example, in a network of multiple parallel stations, the optimal policy assigns the highest priority to the fastest station if service times can be ordered in likelihood ratios. Finally, by means of a numerical study, we test the shortest-expected-remaining-service-time policy on parallel-series networks with three stations and find that this index policy either coincides with the optimal policy or provides a near-optimal performance.     

Effects of system parameters on the optimal policy structure in a class of queueing control problems

This paper studies a class of queueing control problems involving commonly used control mechanisms such as admission control and pricing. It is well established that in a number of these problems, there is an optimal policy that can be described by a few parameters. From a design point of view, it is useful to understand how such an optimal policy varies with changes in system parameters. We present a general framework to investigate the policy implications of the changes in system parameters by using event-based dynamic programming. In this framework, the control model is represented by a number of common operators, and the effect of system parameters on the structured optimal policy is analyzed for each individual operator. Whenever a queueing control problem can be modeled by these operators, the effects of system parameters on the optimal policy follow from this analysis.      

A recursive method to the optimal control of an M/G/1 queueing system with finite capacity and infinite capacity

We study a single removable server in an infinite and a finite queueing systems with Poisson arrivals and general distribution service times. The server may be turned on at arrival epochs or off at service completion epochs. We present a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining service time, to obtain the steady state probability distribution of the number of customers in a finite system. The method is illustrated analytically for three different service time distributions: exponential, 3-stage Erlang, and deterministic. Cost models for infinite and finite queueing systems are respectively developed to determine the optimal operating policy at minimum cost.     

Optimal stochastic scheduling in a single server biclass retrial queueing system

The paper deals with the assignment of a single server to two retrial queues. Each customer reapplies for service after an exponentially distributed amount of time. The server operates at customer dependent exponential rates. There are holding costs and costs during service per customer and per unit of time. We provide conditions on which it is optimal to allocate the server to queue 1 or 2 in order to minimize the expected total costs until the system is cleared.     

Transient solution for a finite capacity M/G a,b /1 queueing system with vacations to the server

In this paper we consider a single server queueing system with Poisson input, general service and a waiting room that allows only a maximum of b customers to wait at any time. A minimum of a customers are required to start a service and the server goes for a vacation whenever he finds less than a customers in the waiting room after a service. If the server returns from a vacation to find less than a customers waiting, he begins another vacation immediately. Using the theory of regenerative processes we derive expressions for the time dependent system size probabilities at arbitrary epochs.     

Optimal control of a queueing system with an exponential and an Erlangian server and renewal input stream

Customers arrive in a renewal process at a queue which is served by an exponential and a two-stage Erlangian server. We prove the optimal policy for assignment of customers to the servers which for any t maximizes the expected number of served customers in [0,t].     

Steady-state probability of the randomized server control system with second optional service, server breakdowns and startup

This paper deals with the 〈N,p〉-policy M/G/1 queue with server breakdowns and general startup times, where customers arrive to demand the first essential service and some of them further demand a second optional service. Service times of the first essential service channel are assumed to follow a general distribution and that of the second optional service channel are another general distribution. The server breaks down according to a Poisson process and his repair times obey a general distribution in the first essential service channel and second optional service channel, respectively. The server operation starts only when N (N≥1) customers have accumulated, he requires a startup time before each busy period. When the system becomes empty, turn the server off with probability p (p∈[0,1]) and leave it on with probability (1?p). The method of maximum entropy principle is used to develop the approximate steady-state probability distribution of the queue length in the M/G(G, G)/1 queueing system. A study of the derived approximate results, compared to the established exact results for three different 〈N,p〉-policy queues, suggests that the maximum entropy principle provides a useful method for solving complex queueing systems.     

Analysis of a discrete-time queueing system with time-limited service

We analyze a discrete-time, single-server queueing system in which the length of each service period is limited. The server takes a vacation when the limit expires or the queue empties, whichever occurs first. In the former case, the preempted service is resumed after the vacation without loss or creation of any work. This system models the transmission of message frames from a station on timed-token local-area networks (for example, FDDI and IEEE 802.4 token bus). We study the process of the unfinished work and the joint process of the queue size and the remaining service time. By using the technique of discrete Fourier transforms to determine some unknown functions in the governing equations, we numerically obtain exact mean waiting times.A part of the work of H. Takagi was done while he was with IBM Research, Tokyo Research Laboratory.