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.     

Scheduling in a multi-class series of queues with deterministic service times

We consider a problem of scheduling in a multi-class network of single-server queues in series, in which service times at the nodes are constant and equal. Such a model has potential application to automated manufacturing systems or packet-switched communication networks, where a message is divided into packets (or cells) of fixed lengths. The network is a series-type assembly or transfer line, with the exception that there is an additional class of jobs that requires processing only at the first node (class 0). There is a holding cost per unit time that is proportional to the total number of customers in the system. The objective is to minimize the (expected) total discounted holding cost over a finite or an infinite horizon. We show that an optimal policy gives priority to class-0 jobs at node 1 when at least one of a set ofm–1 inequalities on partial sums of the components of the state vector is satisfied. We solve the problem by two methods. The first involves formulating the problem as a (discrete-time) Markov decision process and using induction on the horizon length. The second is a sample-path approach using an interchange argument to establish optimality.The research of this author was supported by the National Science Foundation under Grant No. DDM-8719825. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.     

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.     

Flow time distributions in aK classM/G/1 priority feedback queue

In this paper, aK classM/G/1 queueing system with feedback is examined. Each arrival requires at least one, and possibly up toK service phases. A customer is said to be in classk if it is waiting for or receiving itskth phase of service. When a customer finishes its phasek ≤K service, it either leaves the system with probabilityp _k, or it instantaneously reenters the system as a classk + 1 customer with probability (1 −p _k). It is assumed thatp _k = 1. Service is non-preemptive and FCFS within a specified priority ordering of the customer classes. Level crossing analysis of queues and delay cycle results are used to derive the Laplace-Stieltjes Transform (LST) for the PDF of the sojourn time in classes 1,…,k;k ≤K.     

Inference and prediction in bulk arrival queues and queues with service in stages

This paper deals with the statistical analysis from a Bayesian point of view, of bulk arrival queues where the batch size is considered as a fixed constant. The focus is on prediction of the usual measures of performance of the system in the steady state. The probability generating function of the posterior predictive distribution of the number of customers in the system and the Laplace transform of the posterior predictive distribution of the waiting time in the system are obtained. Numerical inversion of these transforms is considered. Inference and prediction of its equivalent single queue with service in stages is also discussed. © 1998 John Wiley & Sons, Ltd.     

Time-dependent analysis of virtual waiting time behaviour in discrete time queues

Discrete time queueing models have been shown previously to be of practical use for modelling the approximate time-dependent behaviour of queue length in systems of the form M(t)/G/c. In this paper we extend these models to include the time-dependent behaviour of virtual waiting time.     

Sample-path conservation laws,with applications to scheduling queues and fluid systems

The achievable-region approach, based on strong conservation laws, has most often been applied to stochastic scheduling and other control problems in the context of performance measures that are steady-state expected quantities. For some problems, however, strong conservation laws hold for performance measures at every time point on every sample path. We exploit this property to study optimal control for certain scheduling problems on a sample-path basis. Examples include preemptive scheduling to minimize a weighted sum of work in the system in each class, nonpreemptive scheduling to minimize a weighted sum of the number of customers in each class (when all classes have the same service-time distribution), and scheduling the processing of fluid in a multiclass fluid system operating in a random environment. The last problem is solved by considering the related Skorohod problem and its minimal solution. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Waiting times in queues with relative priorities

This paper determines the mean waiting times for a single server multi-class queueing model with Poisson arrivals and relative priorities. If the server becomes idle, the probability that the next job is from class-i is proportional to the product between the number of class-i jobs present and their priority parameter.     

A note on the conservation law for continuous reflected processes and its application to queues with fluid inputs

In this note we provide a new derivation of a conservation law for stationary continuous reflected processes which arise in the context of fluid queueing models. This readily gives the so-called Little's law for fluid queues as a special case. We then apply the result to compute the Laplace transform of the stationary workload distribution for a queue with fluid ON-OFF inputs in terms of the Palm distribution associated with the beginning of ON periods. This revised version was published online in June 2006 with corrections to the Cover Date.     

Convex comparison of service disciplines in real time queues

We present a comparison of the service disciplines in real time queueing systems (the customers have a deadline before which they should enter the service booth). We state that giving priority to customers having an early deadline minimizes the average stationary lateness. We show this result by comparing adequate random vectors with the Schur convex majorization ordering.     

The “least flexible job first” rule in scheduling and in queueing

We consider an environment with m$m$ machines in parallel operating at different speeds. The processing requirements of all jobs are independent and have the same exponential distribution. Job j$j$ may only be processed on a specific subset of the m$m$ machines, referred to as its restricted set. The restricted sets are nested and preemptions are allowed. We show that the Least Flexible Job to the Fastest Machine (LFJ-FM) minimizes the expected makespan and the total expected completion time.     

Prediction in Markovian bulk arrival queues

This paper deals with the statistical analysis of bulk arrival queues from a Bayesian point of view. The focus is on prediction of the usual measures of performance of the system in equilibrium. Posterior predictive distribution of the number of customers in the system is obtained through its probability generating function. Posterior distribution of the waiting time, in the queue and in the system, of the first customer of an arriving group is expressed in terms of their Laplace and Laplace–Stieltjes transform. Discussion of numerical inversion of these transforms is addressed.     

Optimal scheduling policies in time sharing service systems

We consider optimal scheduling problems in a TSSS (Time Sharing Service System), i.e., a tandem queueing network consisting of multiple service stations, all of which are served by a single server. In each station, a customer can receive service time up to the prescribed station dependent upper bound, but he must proceed to the next station in order to receive further service. After the total amount of the received services reaches his service requirement, he departs from the network. The optimal policy for this system minimizes the long-run average expected waiting cost per unit of time over the infinite planning horizon. It is first shown that, if the distribution of customer's service requirement is DMRL (Decreasing Mean Residual Life), the policy of giving the highest priority to the customer with the most attained service time is optimal under a set of some appropriate conditions. This implies that any policy without interruptions and preemptions of services is optimal. If the service requirement is DFR (Decreasing Failure Rate), on the other hand, it is shown that the policy of giving the highest priority to the customer with the least attained service time, i.e., the so-called LAST (Least Attained Service Time first) is optimal under another set of some appropriate conditions. These results can be generalized to the case in which there exist multiple classes of customers, but each class satisfies one of the above sets of conditions.     

Delay performance in stochastic processing networks with priority service

We evaluate the delay performance of an open multi-class stochastic processing network of multi-server resources with preemptive-resume priority service. We show that the stationary distribution of aggregate queue lengths has product form. For each service class we derive explicit expressions for the following stationary performance measures: The mean and, under feedforward routing, the Laplace transform of the delay distribution at each resource. We show that these measures are the same as if the resources were operating in isolation.     

Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time

We are interested in the problem of scheduling orders for different product types in a facility with a number of machines in parallel. Each order asks for certain amounts of various different product types which can be produced concurrently. Each product type can be produced on a subset of the machines. Two extreme cases of machine environments are of interest. In the first case, each product type can be produced on one and only one machine which is dedicated to that product type. In the second case, all machines are identical and flexible; each product type can be produced by any one of the machines. Moreover, when a machine in this case switches over from one product type to another, no setup is required. Each order has a release date and a weight. Preemptions are not allowed. The objective is minimizing the total weighted completion time of the orders. Even when all orders are available at time 0, both types of machine environments have been shown to be NP-hard for any fixed number (≥2) of machines. This paper focuses on the design and analysis of approximation algorithms for these two machine environments. We also present empirical comparisons of the various algorithms. The conclusions from the empirical analyses provide insights into the trade-offs with regard to solution quality, speed, and memory space. Electronic Supplementary Material The online version of this article () contains supplementary material, which is available to authorized users. This research is supported by the National Science Foundation through grants DMI-0300156 and DMI-0245603.