Sample-path analysis of general arrival queueing systems with constant amount of work for all customers

We consider a discrete-time queueing system where the arrival process is general and each arriving customer brings in a constant amount of work which is processed at a deterministic rate. We carry out a sample-path analysis to derive an exact relation between the set of system size values and the set of waiting time values over a busy period of a given sample path. This sample-path relation is then applied to a discrete-time $G/D/c$ queue with constant service times of one slot, yielding a sample-path version of the steady-state distributional relation between system size and waiting time as derived earlier in the literature. The sample-path analysis of the discrete-time system is further extended to the continuous-time counterpart, resulting in a similar sample-path relation in continuous time.     

A queueing model with bonus service for certain customers

A queueing model is introduced in which the management has a policy, because of economic reasons, of not operating the service counter unless a certain number, R + 1, of customers are available during each busy period. Thus, the first R customers who arrive must wait until the service counter is opened. Such a policy may cause the management to provide or render additional services to the first R customers. Assuming Poisson arrivals and that both regular and additional services follow exponential distributions, explicit expressions are derived for the stationary queue length and busy period distributions and their expected values. In the special case where R = 1, an explicit expression is presented for the stationary distribution of the waiting time.     

Local balance in queueing networks with positive and negative customers

This paper investigates to what extent a recently developed new product form result for queueing networks with positive and negative customers fits into the class of product form queueing networks that satisfy a notion of partial or local balance. As such, this paper investigates whether this new product form is still a consequence of an appropriate notion of local balance. To this end, a new and non-standard type of local balance is introduced as an extension of standard local balance. This new type of local balance appears more restrictive and is no longer directly sufficient for global balance. Nevertheless, based on this new type of local balance, some extensions such as blocking phenomena for queueing networks with positive and negative customers can be concluded.     

On the stability of queueing systems under precedence restrictions for the service of customers

We consider queueing systems under precedence-based queueing disciplines and derive conditions for the stability of the system. The precedence restrictions are posed on customers' service in a way that a service can start only if some previous customers are served completely and some later customers arrived already. The stability depends on the interarrival times only through their means and the stability condition splits into two terms: with respect to a typical customer, one is representing the influences of future arrivals and one is representing the influences of past arrivals.     

Continuity of queueing systems with refusals

This paper considers queueing systems of the type G ¦G¦m¦ 0. The sequence y= {Y _n ,n=0,1,2,...} is introduced, where Y _n is the number of busy apparatuses at the moment of call number n; this sequence is related by rule (1) in the paper to the determining sequence X={X _n ,n=0,1,2,...}. Also introduced are the respective sets ={x} andy ={y}. This paper uses a method of V. M. Zolotarev to study the continuity of the associated map F: Y with the help of selected metrics on and y, and constructs quantitative estimates of general type, and also in concrete cases. It is shown that asm, the estimates are transformed into the respective estimates in [2], which are related to the case G¦G¦.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 87, pp. 125–142, 1979.In conclusion, I consider it a pleasant duty to thank Professor V. M. Zolotarev for posing the problem, and his constant attention to my work.     

Markov-modulated queueing systems

Markov-modulated queueing systems are those in which the primary arrival and service mechanisms are influenced by changes of phase in a secondary Markov process. This influence may be external or internal, and may represent factors such as changes in environment or service interruptions. An important example of such a model arises in packet switching, where the calls generating packets are identified as customers being served at an infinite server system. In this paper we first survey a number of different models for Markov-modulated queueing systems. We then analyze a model in which the workload process and the secondary process together constitute a Markov compound Poisson process. We derive the properties of the waiting time, idle time and busy period, using techniques based on infinitesimal generators. This model was first investigated by G.J.K. Regterschot and J.H.A. de Smit using Wiener-Hopf techniques, their primary interest being the queue-length and waiting time.     

Analysis of queueing systems with customer interjections

In this paper we study queueing systems with customer interjections. Customers are distinguished into normal customers and interjecting customers. All customers join a single queue waiting for service. A normal customer joins the queue at the end and an interjecting customer tries to cut in the queue. The waiting times of normal customers and interjecting customers are studied. Two parameters are introduced to describe the interjection behavior: the percentage of customers interjecting and the tolerance level of interjection by individual customers. The relationship between the two parameters and the mean and variance of waiting times is characterized analytically and numerically.     

Matched queueing systems with a double input

In this paper, we study the matched queueing system with a double input, M o M/PH/1, where the two inputs are two independent Poisson processes, and the service time is of PH-distribution. The L.S. transforms and the expectations of the distributions of occupation time and virtual waiting time of the type-1 customer are derived. The probability that the server is working, the mean non-idle period, and the mean busy period are also derived. The related algorithms are given with numerical results.This project is supported by the National Natural Science Foundation of China.     

Analysis of discrete-time queueing systems with priority jumps

This text is a summary of the author’s PhD thesis supervised by Herwig Bruneel and Joris Walraevens, and defended on 5 March 2009 at Ghent University. The thesis is written in English and is available from the author upon request. The work deals with several priority scheduling disciplines with so-called priority jumps. An efficient priority scheduling discipline is of great importance in modern telecommunication devices. Static priority scheduling achieves maximum service differentiation between different types of traffic, but may have a too severe impact on the performance of lower-priority traffic. Introducing priority jumps aims for a more gradual service differentiation. In the thesis, we propose several (types of) jumping mechanisms, and we analyse their effect on the performance of a discrete-time queueing system.     

Ergodicity conditions for queueing systems with repeated calls

Translated from Problemy Ustoichivosti Stokhasticheskikh Modelei, pp. 3–8, 1991.     

Performance optimization of queueing systems with perturbation realization

After the intensive studies of queueing theory in the past decades, many excellent results in performance analysis have been obtained, and successful examples abound. However, exploring special features of queueing systems directly in performance optimization still seems to be a territory not very well cultivated. Recent progresses of perturbation analysis (PA) and sensitivity-based optimization provide a new perspective of performance optimization of queueing systems. PA utilizes the structural information of queueing systems to efficiently extract the performance sensitivity information from a sample path of system. This paper gives a brief review of PA and performance optimization of queueing systems, focusing on a fundamental concept called perturbation realization factors, which captures the special dynamic feature of a queueing system. With the perturbation realization factors as building blocks, the performance derivative formula and performance difference formula can be obtained. With performance derivatives, gradient-based optimization can be derived, while with performance difference, policy iteration and optimality equations can be derived. These two fundamental formulas provide a foundation for performance optimization of queueing systems from a sensitivity-based point of view. We hope this survey may provide some inspirations on this promising research topic.     

A queueing system where customers require a random number of servers simultaneously

A closed single node queueing system with multiple classes is analyzed numerically. The node consists of M identical servers fed by a single queue. Each customer of class r, 1 ⩽ r ⩽ M, acquires r servers simultaneously at the beginning of its service. All r servers are released at the same time upon completion of its service. The service time of a class r customer is exponentially distributed with a mean depending on r. This queueing model is analyzed with a view to obtaining performance measures such as throughput, distribution of busy servers, and queue-length distribution.     

Statistical analysis of queueing systems

This paper provides an overview of the literature on statistical analysis of queueing systems. Topics discussed include: model identification, estimation, hypothesis testing and other related aspects. Not all of these statistical problems are covered in books on queueing theory or stochastic processes. The bibliography is not exhaustive, but comprehensive enough to provide sources from the literature.