Instability of SRPT,SERPT and SJF multiclass queueing networks

Queueing Systems - We provide two examples of strictly subcritical multiclass queueing networks which are unstable under the shortest remaining processing time (SRPT) service protocol. Both of them...     

Linear loss networks

This paper investigates theoretical properties of throughput and cost in linear loss networks. The maximum throughput of the network with exponential service times is derived and the arrival process that maximizes throughput, given a fixed arrival rate, is established. For general service times, an asymptotically critical loading regime is identified such that the probability of an arbitrary customer being lost is strictly within (0,1) as the network size increases. This regime delivers throughput comparable to the maximum at a relatively low network cost. The paper establishes the asymptotic throughput and network cost under this critical loading.     

The cyclic queue and the tandem queue

We consider a closed queueing network, consisting of two FCFS single server queues in series: a queue with general service times and a queue with exponential service times. A fixed number \(N\) of customers cycle through this network. We determine the joint sojourn time distribution of a tagged customer in, first, the general queue and, then, the exponential queue. Subsequently, we indicate how the approach toward this closed system also allows us to study the joint sojourn time distribution of a tagged customer in the equivalent open two-queue system, consisting of FCFS single server queues with general and exponential service times, respectively, in the case that the input process to the first queue is a Poisson process.     

A Priority Tandem Queue with No Intermediate Buffer

Priority queues are important in modelling and analysis of manufacturing systems, and computer and communication networks. In this paper, a priority tandem queueing system with two stations in series is studied. There is no intermediate buffer between the two stations, and the lack of buffers may cause blocking at the first station. K types of customers arrive at the system according to Poisson processes. The expected delay in the system for each type of customer is obtained when all the customers have the same service time distribution at the second station. Two cases are studied in detail when service times are either all exponentially distributed or all deterministic.     

An approximation for multi-server queues with deterministic reneging times

This work was motivated by the timeout mechanism used in managing application servers in transaction processing environments. In such systems, a customer who stays in the queue longer than the timeout period is lost. We modeled a server node with a timeout threshold as a multi-server queue with Poisson arrivals, general service time distribution and deterministic reneging times. We proposed a scaling approach, and a fast and accurate approximation for the expected waiting time in the queue.     

System delay versus system content for discrete-time queueing systems subject to server interruptions

This paper concerns discrete-time queueing systems operating under a first-come-first-served queueing discipline, with deterministic service times of one slot and subject to independent server interruptions. For such systems, we derive a relationship between the probability generating functions of the system content during an arbitrary slot and of the system delay of an arbitrary customer. This relationship is valid regardless of the nature of the arrival process. From this relationship we derive a relationship between the first- and second-order moments of the distributions involved. It is shown that the relationship also applies to subsystems of the queueing system being discussed, and to the waiting time and queue content of a multi-server queueing system with geometric service times and uninterrupted servers.     

Product form solution for exponential G-networks with dependent service and completion of service of killed customers

Queueing networks with negative customers (G-networks), Poisson flow of positive customers, multi-server exponential nodes, and dependent service at the different nodes are studied. Every customer arriving at the network is defined by a set of random parameters: customer route, the length of customer route, customer volume and his service time at each route stage as well. A killed positive customer is removed at the last place in the queue and quits the network just after his remaining service time will be elaborated. For such G-networks, the multidimensional stationary distribution of the network state probabilities is shown to be representable in product form.     

A single-server discrete-time queue with correlated positive and negative customer arrivals

An MMBP/Geo/1 queue with correlated positive and negative customer arrivals is studied. In the infinite-capacity queueing system, positive customers and negative customers are generated by a Bernoulli bursty source with two correlated geometrically distributed periods. I.e., positive and negative customers arrive to the system according to two different geometrical arrival processes. Under the late arrival scheme (LAS), two removal disciplines caused by negative customers are investigated in the paper. In individual removal scheme, a negative customer removes a positive customer in service if any, while in disaster model, a negative customer removes all positive customers in the system if any. The negative customer arrival has no effect on the system if it finds the system empty. We analyze the Markov chains underlying the queueing systems and evaluate the performance of two systems based on generating functions technique. Some explicit solutions of the system, such as the average buffer content and the stationary probabilities are obtained. Finally, the effect of several parameters on the system performance is shown numerically.     

Asymptotically optimal staffing of service systems with joint QoS constraints

We consider the problem of staffing large-scale service systems with multiple customer classes and multiple dedicated server pools under joint quality-of-service (QoS) constraints. We first analyze the case in which arrival rates are deterministic and the QoS metric is the probability a customer is queued, given by the Erlang-C formula. We use the Janssen–Van Leeuwaarden–Zwart bounds to obtain asymptotically optimal solutions to this problem. The second model considered is one in which the arrival rates are not completely known in advance (before the server staffing levels are chosen), but rather are known via a probability distribution. In this case, we provide asymptotically optimal solutions to the resulting stochastic integer program, leveraging results obtained for the case of deterministic arrivals.     

Stochastic Networks: Admission and Routing Using Penalty Functions

We propose an admission and routing control policy for a network of service facilities in a stochastic setting in order to maximize a long run average reward. Queueing and reneging before entering the network is allowed; we introduce orbiting as an approximation to the queueing. Once a customer has entered the network, it incurs no more waiting. Our control policy is easy to implement and we prove that it performs well in steady state as long as the capacity request sizes are relatively small compared to the capacity of the service facilities. The policy is a target tracking policy: a linear program provides a target operating point and an exponential penalty function is used to translate the optimal deterministic point into a feasible admission and routing policy. This translation essentially transforms the admission and routing control problem into a problem of load balancing via the construction of fictitious systems. Simulation studies are included to illustrate that our policy also performs well when request sizes are moderate or large with respect to the capacity.     

Temporal and spatial chaos in a van der Waals fluid due to periodic thermal fluctuations

The Mel'nikov technique is applied to prove the existence of deterministic chaos in two problems for a van der Waals fluid. The first problem shows that temporal chaos results as a result of small time periodic fluctuations about a subcritical temperature when the fluid is initially quenched in the unstable spinoidal region. The second problem shows that spatial chaos arises from small spatially periodic flunctions in an infinite tube of fluid if the ambient pressure is appropriately chosen.     

Service level robustness in stochastic production planning under random machine breakdowns

In this paper, we consider a multi-period, multi-product production planning problem where the production rate and the customer service level are random variables due to machine breakdowns. In order to determine robust production plans, constraints are introduced in the stochastic capacitated lot-sizing problem to ensure that a pre-specified customer service level is met with high probability. The probability of meeting a service level is evaluated by using the first passage time theory of a Wiener process to a boundary. A two-step optimization approach is proposed to solve the developed model. In the first step, the mean-value deterministic model is solved. Then, a method is proposed in the second step to improve the probability of meeting service level. The resulting approach has the advantage of not being a scenario-based one. It is shown that substantial improvements in service level robustness are often possible with minimal increases in expected cost.     

Estimating characteristics of queueing networks using transactional data

We are motivated by queueing networks in which queues are difficult to observe but services are easy to record. Our goal is to estimate the queues from service data. More specifically, we consider an open queueing network with Poisson external arrivals, multi‐server stations, general service times and Markovian switches of customers between stations. Customers' transitions between stations may be either immediate or of exponentially distributed durations. Each customer is supplied with an Identification Number (ID) upon entering the network. Operational data is collected which includes transaction times (starts and terminations of services) and ID's of served customers. Our objective is to estimate the evolution of the queues in the network, given the collected data. We cover estimation at both end of busy periods and in real time. The applicability of the theory is demonstrated by analyzing a service operation. This revised version was published online in June 2006 with corrections to the Cover Date.     

A complete and simple solution for a discrete-time multi-server queue with bulk arrivals and deterministic service times

A complete distribution for the system content of a discrete-time multi-server queue with an infinite buffer is presented, where each customer arriving in a group requires a deterministic service time that could be greater than one slot. In addition, when the service time equals one slot, a complete distribution for the delay is also presented.     

The Maximum Queue Length for Heavy-Tailed Service Times in the M/G/1 FB Queue

This paper treats the maximum queue length M, in terms of the number of customers present, in a busy cycle in the M/G/1 queue. The distribution of M depends both on the service time distribution and on the service discipline. Assume that the service times have a logconvex density and the discipline is Foreground Background (FB). The FB service discipline gives service to the customer(s) that have received the least amount of service so far. It is shown that under these assumptions the tail of M is bounded by an exponential tail. This bound is used to calculate the time to overflow of a buffer, both in stable and unstable queues.     

Network of Single-Server Queues with Dependent Service Times

A network of single-server nodes fed by customers of several classes is considered. Each customer is equipped with the random work to be done for completing service. The distribution of this work and the rate of its decreasing during the service depend on the node, the class of the customer, the queue contents and the residual work loads of the customers at the node. The service discipline is LCFS preemptive-resume. For both open and closed network, the stationary distribution is derived. In general, this distribution is not a product form. For the open network, sufficient conditions yielding the product form are given. For both open and closed network, sufficient invariance conditions are found.     

A single server queue with cyclically indexed arrival and service rates

In this paper we consider a queueing model that results from at least two apparently unrelated areas. One motivation to study a system of this type results from a test case of a computer simulation factor screening technique calledfrequency domain methodology. A second motivation comes from manufacturing, where due to cyclic scheduling of upstream machines, the arrival process to downstream machines is periodic. The model is a single server queue with FIFO service discipline and exponential interarrival and service times where the arrival and/or service rates are deterministic cyclic functions of the customer sequence number. We provide steady state results for the mean number in the system for the model with cyclic arrival and fixed service rates and for the model with fixed arrival and cyclic service rates. For the model with both cyclic arrival and service rates, upper and lower bounds are developed for the steady state mean waiting time in the system. Throughout the paper various implications and/or insights derived from the results of this study are discussed for frequency domain methodology.The authors acknowledge the financial support of the CBA/GSB Faculty Research Committee of the College of Business Administration, The University of Texas at Austin.     

On the Two-Class M/M/1 System under Preemptive Resume and Impatience of the Prioritized Customers

The paper deals with the two-class priority M/M/1 system, where the prioritized class-1 customers are served under FCFS preemptive resume discipline and may become impatient during their waiting for service with generally distributed maximal waiting times. The class-2 customers have no impatience. The required mean service times may depend on the class of the customer. As the dynamics of class-1 customers are related to the well analyzed M/M/1+GI system, our aim is to derive characteristics for class-2 customers and for the whole system. The solution of the balance equations for the partial probability generating functions of the detailed system state process is given in terms of the weak solution of a family of boundary value problems for ordinary differential equations, where the latter can be solved explicitly only for particular distributions of the maximal waiting times. By means of this solution formulae for the joint occupancy distribution and for the sojourn and waiting times of class-2 customers are derived generalizing corresponding results recently obtained by Choi et al. in case of deterministic maximal waiting times. The latter case is dealt as an example in our paper.     

Sequencing and scheduling N customers for a stochastic server

In this paper, we study the problem of sequencing and scheduling N customers for a single-server system. The goal is to balance the expected customer flow times and the expected system completion time. Customers are scheduled to enter the system by appointments only and the service times are exponentially distributed with different rates. The optimization of such a system involves determining the customer service order (sequencing) and the interarrival times (scheduling). We show that the service order depends upon the order of service rates and the optimal schedule can be obtained by solving a set of nonlinear equations. Numerical examples are used to illustrate the method.     

Stochastic models of space priority mechanisms with Markovian arrival processes

In this paper, we study a single-server queue with finite capacity in which several space priority mechanisms are implemented. The arrival process is the general Markovian arrival process (MAP) which has been used to model the bursty arrival processes commonly arising in communication applications. The service times are generally distributed. These buffer mechanisms enable the Asynchronous Transfer Mode (ATM) layer to adapt the quality of the cell transfer to the quality of service requirements of the specific broadband ISDN services and to improve the utilization of the network resources. This is done by a selective discarding of cells according to the class they belong to. Computable expressions for various performance parameters are obtained. Numerical results are given for the case of a two-state Markov-modulated Poisson process (MMPP) and deterministic service times. The values derived can be used to evaluate the benefits of using priorities in an ATM network when the traffic is bursty and to make a comparative study of the buffer mechanisms. These results extend the models previously developed, which were limited to Poisson arrivals.