Optimal threshold policies in a two-class preemptive priority queue with admission and termination control

We consider a two-class 1 preemptive priority queue in which there are two essential, on-line decisions that have to be taken. The first is the decision to either accept or reject new type-1 or type-2 jobs. The second is the decision to abort jobs, i.e., to remove any type-1 or type-2 jobs from the system. We show that there exist optimal threshold policies for these two types of, decisions.     

Calculation of output characteristics of a priority queue through a busy period analysis

In this paper, we analyze some output characteristics of a discrete-time two-class priority queue by means of probability generating functions. Therefore, we construct a Markov chain which – after analysis – provides a.o. the probability generating functions of the lengths of the busy periods of both classes. It is furthermore shown how performance measures, related to the output process, are calculated from these functions. The queueing model is kept fairly simple to explain the method of analysis of the busy periods and the output characteristics of priority queues as clearly as possible.     

On the single server retrial queue with priority customers

We consider anM ₂/G ₂/1 type queueing system which serves two types of calls. In the case of blocking the first type customers can be queued whereas the second type customers must leave the service area but return after some random period of time to try their luck again. This model is a natural generalization of the classicM ₂/G ₂/1 priority queue with the head-of-theline priority discipline and the classicM/G/1 retrial queue. We carry out an extensive analysis of the system, including existence of the stationary regime, embedded Markov chain, stochastic decomposition, limit theorems under high and low rates of retrials and heavy traffic analysis.Visiting from: Department of Probability, Mechanics and Mathematics, Moscow State University, Moscow 119899, Russia.     

A two-queue,one-server model with priority for the longer queue

The queueing model studied consists of one server and two queues. Each queue has its own Poisson arrival stream and service time distribution. After a service completion, the server proceeds with a customer from the longer queue, if the queues are unequal; if the queues are equal, the server chooses with some probability a customer from one of the queues. The model is of practical interest in performance analysis, but also of theoretical interest because the functional equation to be solved has not yet been studied in the queueing literature. A basic analysis of this functional equation is presented. Some numerical results are given to assess the influence of the present service discipline. Some new properties of L.S. transforms of service time distributions are discussed in the appendix.Dr. T. Katayama has formulated the present problem and brought it to the author's attention during his visit in October/November 1984 to the NTT-Electr. Comm. Lab.'s Musashino, Tokyo 180.     

A simple proof for the constructions of optical priority queues

Constructions of optical queues by optical Switches and fiber Delay Lines (SDL) have received a lot of attention lately. In this short paper, we provide a simple proof for the construction of a priority queue with a switch and fiber delay lines in Sarwate and Anantharam (Queueing Syst. Theory Appl. 53, 115–125, 2006). Our proof not only gives the insights needed to understand why such a construction works, but also leads to a more general result that recovers the result in Sarwate and Anantharam (Queueing Syst. Theory Appl. 53, 115–125, 2006) as a special case. This research was supported in part by the National Science Council, Taiwan, ROC, under Contract NSC-93-2213-E-007-040, Contract NSC-93-2213-E-007-095, Contract NSC-94-2213-E-007-046, and the Program for Promoting Academic Excellence of Universities NSC 94-2752-E-007-002-PAE.     

How pre-emptive priority affects completion rate in an M/M/1 queue with Poisson reneging

Queuing problems in which customers leave the queue without obtaining service (i.e. renege) have many applications. This paper looks at a queue where arrival, service and reneging events are all generated by independent Poisson processes, and customers are selected for service according to priority. A closed-form expression is derived for the probability of completing service for each priority class if high-priority customers always pre-empt low-priority ones. This result has applications in modeling the value of communications between members of an interacting population, such as a formal organization or an online community.     

The efficiency of two indexed priority queue algorithms

Two priority queue algorithms, a linked linear sublist and ap-subtree algorithm, are analysed. Both of them use a search index that speeds up finding the correct sublist/subtree. In most cases the methods require a short processing time for the so-called HOLD-operation of the discrete event simulation. The relative power of the algorithms depends on the ratior of the total number of elements in the queue and the size of the search index. For large values ofr (16) thep-subtree algorithm is to be preferred. However, the more primitive data structure used by the sublist algorithm makes it possible to use a larger index leading to a smaller ratior.     

The permutational power of a priority queue

A priority queue transforms an input permutation of some set of sizen into an output permutation. It is shown that the number of such pairs (, ) is (n + 1) ^n–1. Some related enumerative and algorithmic questions are also considered.Supported by the National Science and Engineering Research Council of Canada under Grant A4219.     

Delay analysis of discrete-time priority queue with structured inputs

This paper investigates a discrete-time priority queue with multi-class customers. Applying a delay-cycle analysis, we explicitly derive the probability generating function of the waiting time for an individual class in a geometric batch input queue under preemptive-resume and head-of-the-line priority rules. The conservation law and waiting time characterization for a general class of discrete-time queues are also presented. The results in this paper cover several previous results as special cases.     

Analysis of the adaptive MMAP[K]/PH[K]/1 queue: A multi-type queue with adaptive arrivals and general impatience

In this paper we introduce the adaptive MMAP[K] arrival process and analyze the adaptive MMAP[K]/PH[K]/1 queue. In such a queueing system, customers of K different types with Markovian inter-arrival times and possibly correlated customer types, are fed to a single server queue that makes use of r thresholds. Service times are phase-type and depend on the type of customer in service. Type k customers are accepted with some probability a_i,k if the current workload is between threshold i − 1 and i. The manner in which the arrival process changes its state after generating a type k customer also depends on whether the customer is accepted or rejected.     

Time-dependent analysis of a queue with batch arrivals andn levels of nonpreemptive priority

A queueing system with batch arrivals andn classes of customers with nonpreemptive priorities between them is considered. Each batch arrives according to the Poisson distribution and contains customers of all classes while the service times follow arbitrary distributions with different probability density functions for each class. For such a model the system states probabilities both in the transient and in the steady state are analysed and also expressions for the Laplace transforms of the busy period densities for each class and for the general busy period are obtained.     

A first passage time problem for spectrally positive Lévy processes and its application to a dynamic priority queue

We study a first passage time problem for a class of spectrally positive Lévy processes. By considering the special case where the Lévy process is a compound Poisson process with negative drift, we obtain the Laplace–Stieltjes transform of the steady-state waiting time distribution of low-priority customers in a two-class M/GI/1$M/GI/1$ queue operating under a dynamic non-preemptive priority discipline. This allows us to observe how the waiting time of customers is affected as the policy parameter varies.     

Optimal intensity control of a multi-class queue

We study a mixed problem of optimal scheduling and input and output control of a single server queue with multi-classes of customers. The model extends the classical optimal scheduling problem by allowing the general point processes as the arrival and departure processes and the control of the arrival and departure intensities. The objective of our scheduling and control problem is to minimize the expected discounted inventory cost over an infinite horizon, and the problem is formulated as an intensity control. We find the well-knownc is the optimal solution to our problem.Supported in part by NSF under grant ECS-8658157, by ONR under contract N00014-84-K-0465, and by a grant from AT&T Bell Laboratories.The work was done while the author was a postdoctoral fellow in the Division of Applied Sciences, Harvard University, Cambridge, Massachusetts 02138.     

Admission control and pricing in a queue with batch arrivals

We investigate a problem of admission control in a queue with batch arrivals. We consider a single server with exponential service times and a compound Poisson arrival process. Each arriving batch computes its expected benefit and decides whether or not to enter the system. The controller’s problem is to set state dependent prices for arriving batches. Once prices have been set we formulate the admission control problem, derive properties of the value function, and obtain the optimal admission policy.     

Optimal admission policies for a finite queue with bursty arrivals

We consider a service system with a single server, a finite waiting room and two classes of customers with deterministic service time. Primary jobs arrive at random and are admitted whenever there is room in the system. At the beginning of each period, secondary jobs can be admitted from an infinite pool. A revenue is earned upon admission of each job, with the primary jobs bringing a higher contribution than the secondary jobs, the objective being to maximize the total discounted revenue over an infinite horizon. We model the system as a discrete time Markov decision process and show that a monotone admission policy is optimal when the number of primary arrivals has a fixed distribution. Moreover, when the primary arrival distribution varies with time according to a finite state Markov chain, we show that the optimal policy is conditionally monotone and that the numerical computation of an optimal policy, in this case, is substantially more difficult than in the case of stationary arrivals.This research was supported in part by the National Science Foundation, under grant ECS-8803061, while the author was at the University of Arizona.     

Optimal regulation of the service rate for a queue with finite waiting space

The optimal control for the service rate of a single-server queue with limited waiting space is derived. Costs are associated with providing the service and with waiting. A comparison with the traditional steady-state result is made.     

Waiting time analysis of a two-stage queueing system with priorities

A two-stage queueing system with two types of customers and non-preemptive priorities is analyzed. There is no waiting space between stages and so the blocking phenomenon is observed. The arrivals follow a Poisson distribution for the high priority customers and a gamma distribution for the low priority customers, while all service times are arbitrarily distributed. We derive expressions for the Laplace transform of the waiting time density of a low priority customer both in the transient and the steady state.     

Optimal control of a queue under a quality-of-service constraint with bounded and unbounded rates

We consider a simple Markovian queue with Poisson arrivals and exponential service times for jobs. The controller chooses state-dependent service rates from an action space. The queue has a finite buffer, and when full, new jobs get rejected. The controller’s objective is to choose optimal service rates that meet a quality-of-service constraint. We solve this problem analytically and compute it numerically under two cases: When the action space is unbounded and when it is bounded.     

Optimality of a Threshold Policy in theM/M/ queue with repeated vacations

Consider anM/M/1 queueing system with server vacations where the server is turned off as soon as the queue gets empty. We assume that the vacation durations form a sequence of i.i.d. random variables with exponential distribution. At the end of a vacation period, the server may either be turned on if the queue is non empty or take another vacation. The following costs are incurred: a holding cost ofh per unit of time and per customer in the system and a fixed cost of each time the server is turned on. We show that there exists a threshold policy that minimizes the long-run average cost criterion. The approach we use was first proposed in Blanc et al. (1990) and enables us to determine explicitly the optimal threshold and the optimal long-run average cost in terms of the model parameters.