Scheduling service in tandem queues attended by a single server

Consider a tandem queue model with a single server who can switch instantaneously from one queue to another. Customers arrive according to a Poisson process with rate λ . The amount of service required by each customer at the i^th queue is an exponentially distributed random variable with rate μ_i. Whenever two or more customers are in the system, the decision as to which customer should be served first depends on the optimzation criterion. In this system all server allocation policies in the finite set of work conserving deterministic policies have the same expected first passage times (makespan) to empty the system of customers from any initial state. However, a unique policy maximizes the first passage probability of empty-ing the system before the number of customers exceeds K, for any value of K, and it stochastically minimizes (he number of customers in the system at any time t > 0 . This policy always assigns the server to the non empty queue closest to the exit     

Optimal control for parallel queues with a single batch server

We consider a queueing system with multiple Poisson arrival queues and a single batch server that has infinite capacity and a fixed service time. The problem is to allocate the server at each moment to minimize the long-run average waiting cost. We propose a Cost-Arrival Weighted (CAW) policy for this problem based on the structure of the optimal policy of a corresponding fluid model. We show that this simple policy enjoys a superior performance by numerical experiments.     

Large sample inference from single server queues

Problems of large sample estimation and tests for the parameters in a single server queue are discussed. The service time and the interarrivai time densities are assumed to belong to (positive) exponential families. The queueing system is observed over a continuous time interval (0,T] whereT is determined by a suitable stopping rule. The limit distributions of the estimates are obtained in a unified setting, and without imposing the ergodicity condition on the queue length process. Generalized linear models, in particular, log-linear models are considered when several independent queues are observed. The mean service times and the mean interarrival times after appropriate transformations are assumed to satisfy a linear model involving unknown parameters of interest, and known covariates. These models enhance the scope and the usefulness of the standard queueing systems.Partially supported by the U. S. Army Research Office through the Mathematical Sciences Institute of Cornell University.     

Duality relations for certain single server queues

In this paper, relations are given between the joint distribution of several variables in a GI/G/1 queue and the joint distribution of variables associated with the busy cycle in the dual queue, that is in the queue which results from the original when the interarrival times and the service times are interchanged. It is assumed that the primal queue has the preemptive-resume last-come-first-served queue discipline while the dual queue may have any queue discipline which is work conserving. These relations generalize a result given recently for M/G/1 and GI/M/1 queues.     

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.     

Single server retrial queues with two way communication

The main aim of this paper is to study the steady state behavior of an M/G/1-type retrial queue in which there are two flows of arrivals namely ingoing calls made by regular customers and outgoing calls made by the server when it is idle. We carry out an extensive stationary analysis of the system, including stability condition, embedded Markov chain, steady state joint distribution of the server state and the number of customers in the orbit (i.e., the retrial group) and calculation of the first moments. We also obtain light-tailed asymptotic results for the number of customers in the orbit. We further formulate a more complicate but realistic model where the arrivals and the service time distributions are modeled in terms of the Markovian arrival process (MAP) and the phase (PH) type distribution.     

Invariance relations in single server queues with LCFS service discipline

This paper is concerned with single server queues having LCFS service discipline. We give a condition to hold an invariance relation between time and customer average queue length distributions in the queues. The relation is a generalization of that in an ordinary GI/M/1 queue. We compare the queue length distributions for different single server queues with finite waiting space under the same arrival process and service requirement distribution of customer and derive invariance relations among them.This research was supported in part by a grant from the Tokyo Metropolitan Government. The latter part of this paper was written while the author resided at the University of California, Berkeley.     

Maximum likelihood estimation for single server queues from waiting time data

Maximum likelihood estimators for the parameters of a GI/G/1 queue are derived based on the information on waiting times {W _t },t=1,...,n, ofn successive customers. The consistency and asymptotic normality of the estimators are established. A simulation study of the M/M/1 and M/E _k /1 queues is presented.     

On normal approximation for maximum likelihood estimation from single server queues

This paper is concerned with the rate of convergence of the distribution of the maximum likelihood estimators of the arrival and the service rates in a GI/G/1 queueing system. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

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.     

Optimal use of excess capacity in two interconnected queues

We consider a two-stage tandem queueing network where jobs from station 1 join station 2 with a certain probability. Each job incurs a linear holding cost, different for each station. Each station is attended by a dedicated server, and there is an additional server that is either constrained to serve in station 1 or can serve in both stations. Assuming no switching or other operating costs for the additional server, we seek an allocation strategy that minimizes expected holding costs. For a clearing system we show that the optimal policy is characterized by a switching curve for which we provide a lower bound on its slope. We also specify a subset of the state space where the optimal policy can be explicitly determined.     

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.     

Insensitivity in discrete time queues with a moving server

Queues in which customers request service consisting of an integral number of segments and in which the server moves from service station to service station are of considerable interest to practitioners working on digital communications networks. In this paper, we present insensitivity theorems and thereby equilibrium distributions for two discrete time queueing models in which the server may change from one customer to another after completion of each segment of service. In the first model, exactly one segment of service is provided at each time point whether or not an arrival occurs, while in the second model, at most one arrival or service occurs at each time point. In each model, customers of typet request a service time which consists ofl segments in succession with probabilityb _t(l). Examples are given which illustrate the application of the theorems to round robin queues, to queues with a persistent server, and to queues in which server transition probabilities do not depend on the server's previous position. In addition, for models in which the probability that the server moves from one position to another depends only on the distance between the positions, an amalgamation procedure is proposed which gives an insensitive model on a coarse state space even though a queue may not be insensitive on the original state space. A model of Daduna and Schassberger is discussed in this context.This work was supported by the Australian Research Council.     

Optimal design of multi‐server Markovian queues with polynomial waiting and service costs

This paper is concerned with the optimal design of queueing systems. The main decisions in the design of such systems are the number of servers, the appropriate control to have on the arrival rates, and the appropriate service rate these servers should possess. In the formulation of the objective function to this problem, most publications use only linear cost rates. The linear rates, especially for the waiting cost, do not accurately reflect reality. Although there are papers involving nonlinear cost functions, no paper has ever considered using polynomial cost functions of degree higher than two. This is because simple formulas for computing the higher moments are not available in the literature. This paper is an attempt to fill this gap in the literature. Thus, the main contributions of our work are as follows: (i) the derivation of a very simple formula for the higher moments of the waiting time for the M/M/s queueing system, which requires only the knowledge of the expected waiting time; (ii) proving their convexity with respect to the design variables; and (iii) modeling and solving more realistic design problems involving general polynomial cost functions. We also focus on simultaneous optimization of the staffing level, arrival rate and service rate. Copyright © 2013 John Wiley & Sons, Ltd.     

A two-stage tandem queue attended by a moving server with holding and switching costs

We consider a two-stage tandem queue attended by a moving server, with homogeneous Poisson arrivals and general service times. Two different holding costs for stages 1 and 2 and different switching costs from one stage to the other are considered. We show that the optimal policy in the second stage is greedy; and if the holding cost rate in the second stage is greater or equal to the rate in the first stage, then the optimal policy in the second stage is also exhaustive. Then, the optimality condition for sequential service policy in systems with zero switchover times is introduced. Considering some properties of the optimal policy, we then define a Triple-Threshold (TT) policy to approximate the optimal policy in the first stage. Finally, a model is introduced to find the optimal TT policy, and using numerical results, it is shown that the TT policy accurately approximates the optimal policy. This revised version was published online in June 2006 with corrections to the Cover Date.     

Dynamic server assignment in a two-queue model

We consider a polling model of two M/G/1 queues, served by a single server. The service policy for this polling model is of threshold type. Service at queue 1 is exhaustive. Service at queue 2 is exhaustive unless the size of queue 1 reaches some level T during a service at queue 2; in the latter case the server switches to queue 1 at the end of that service. Both zero- and nonzero switchover times are considered. We derive exact expressions for the joint queue length distribution at customer departure epochs, and for the steady-state queue-length and sojourn time distributions. In addition, we supply a simple and very accurate approximation for the mean queue lengths, which is suitable for optimization purposes.     

Optimal admission control for two station tandem queues with loss

We consider a two-station tandem queue with a buffer size of one at the first station and a finite buffer size at the second station. Silva et al. (2013) gave a criterion determining the optimal admission control policy for this model. In this paper, we improve the results of Silva et al. (2013) and also solve the problem conjectured by Silva et al. (2013).