Repair systems with exchangeable items and the longest queue mechanism

We consider a repair facility consisting of one repairman and two arrival streams of failed items, from bases 1 and 2. The arrival processes are independent Poisson processes, and the repair times are independent and identically exponentially distributed. The item types are exchangeable, and a failed item from base 1 could just as well be returned to base 2, and vice versa. The rule according to which backorders are satisfied by repaired items is the longest queue rule: At the completion of a service (repair), the repaired item is delivered to the base that has the largest number of failed items. We point out a direct relation between our model and the classical longer queue model. We obtain simple expressions for several probabilities of interest, and show how all two-dimensional queue length probabilities may be obtained. Finally, we derive the sojourn time distributions.     

Large deviation analysis of the single server queue

We establish the large deviation principle (LDP) for the virtual waiting time and queue length processes in the GI/GI/1 queue. The rate functions are found explicitly. As an application, we obtain the logarithmic asymptotics of the probabilities that the virtual waiting time and queue length exceed high levels at large times. Additional new results deal with the LDP for renewal processes and with the derivation of unconditional LDPs for conditional ones. Our approach applies in large deviations ideas and methods of weak convergence theory.This work was supported in part by AT&T Bell Labs.     

Maximizing throughput in finite-source parallel queue systems

Motivated by the dispatching of trucks to shovels in surface mines, we study optimal routing in a Markovian finite-source, multi-server queueing system with heterogeneous servers, each with a separate queue. We formulate the problem of routing customers to servers to maximize the system throughput as a Markov Decision Process. When the servers are homogeneous, we demonstrate that the Shortest Queue policy is optimal, and when the servers are heterogeneous, we partially characterize the optimal policy and present a near-optimal and simple-to-implement policy. We use the model to illustrate the substantial benefits of pooling, by comparing it to the permanent assignment of customers to servers.     

Stability and performance of greedy server systems

Consider a queueing system in which arriving customers are placed on a circle and wait for service. A traveling server moves at constant speed on the circle, stopping at the location of the customers until service completion. The server is greedy: always moving in the direction of the nearest customer. Coffman and Gilbert conjectured that this system is stable if the traffic intensity is smaller than 1; however, a proof or counterexample remains unknown. In this review, we present a picture of the current state of this conjecture and suggest new related open problems.     

服务台不可靠的重试排队系统均衡分析

本文研究服务台不可靠的M/M/1常数率重试排队系统中顾客的均衡进队策略, 其中服务台在正常工作和空闲状态下以不同的速率发生故障。在该系统中, 服务台前没有等待空间, 如果到达的顾客发现服务台处于空闲状态, 该顾客可占用服务台开始服务。否则, 如果服务台处于忙碌状态, 顾客可以选择留下信息, 使得服务台在空闲时可以按顺序在重试空间中寻找之前留下信息的顾客进行服务。当服务台发生故障时, 正在被服务的顾客会发生丢失, 且系统拒绝新的顾客进入系统。根据系统提供给顾客的不同程度的信息, 研究队长可见和不可见两种信息情形下系统的稳态指标, 以及顾客基于收入-支出函数的均衡进队策略, 并建立单位时间内服务商的收益和社会福利函数。比较发现, 披露队长信息不一定能提高服务商收益和社会福利。     

Importance sampling algorithms for first passage time probabilities in the infinite server queue

This paper applies importance sampling simulation for estimating rare event probabilities of the first passage time in the infinite server queue with renewal arrivals and general service time distributions. We consider importance sampling algorithms which are based on large deviations results of the infinite server queue, and we consider an algorithm based on the cross-entropy method, where we allow light-tailed and heavy-tailed distributions for the interarrival times and the service times. Efficiency of the algorithms is discussed by simulation experiments.     

Delay analysis of a two-class batch-service queue with class-dependent variable server capacity

In this paper, we analyse the delay of a random customer in a two-class batch-service queueing model with variable server capacity, where all customers are accommodated in a common single-server first-come-first-served queue. The server can only process customers that belong to the same class, so that the size of a batch is determined by the length of a sequence of same-class customers. This type of batch server can be found in telecommunications systems and production environments. We first determine the steady state partial probability generating function of the queue occupancy at customer arrival epochs. Using a spectral decomposition technique, we obtain the steady state probability generating function of the delay of a random customer. We also show that the distribution of the delay of a random customer corresponds to a phase-type distribution. Finally, some numerical examples are given that provide further insight in the impact of asymmetry and variance in the arrival process on the number of customers in the system and the delay of a random customer.     

Transient analysis of a single server queue with catastrophes, failures and repairs

A transient solution is obtained analytically using continued fractions for the system size in an M/M/1 queueing system with catastrophes, server failures and non-zero repair time. The steady state probability of the system size is present. Some key performance measures, namely, throughput, loss probability and response time for the system under consideration are investigated. Further, reliability and availability of the system are analysed. Finally, numerical illustrations are used to discuss the system performance measures.      

An approximate analysis of a cyclic server queue with limited service and reservations

In this paper, we examine a queueing problem motivated by the pipeline polling protocol in satellite communications. The model is an extension of the cyclic queueing system withM-limited service. In this service mechanism, each queue, after receiving service on cyclej, makes a reservation for its service requirement in cyclej + 1. The main contribution to queueing theory is that we propose an approximation for the queue length and sojourn-time distributions for this discipline. Most approximate studies on cyclic queues, which have been considered before, examine the means only. Our method is an iterative one, which we prove to be convergent by using stochastic dominance arguments. We examine the performance of our algorithm by comparing it to simulations and show that the results are very good.     

Stationary analysis of the shortest queue first service policy

We analyze the so-called shortest queue first (SQF) queueing discipline whereby a unique server addresses queues in parallel by serving at any time, the queue with the smallest workload. Considering a stationary system composed of two parallel queues and assuming Poisson arrivals and general service time distributions, we first establish the functional equations satisfied by the Laplace transforms of the workloads in each queue. We further specialize these equations to the so-called “symmetric case,” with same arrival rates and identical exponential service time distributions at each queue; we then obtain a functional equation $$\begin{aligned} M(z) = q(z) \cdot M \circ h(z) + L(z) \end{aligned}$$ for unknown function M, where given functions \(q, L\) , and \(h\) are related to one branch of a cubic polynomial equation. We study the analyticity domain of function M and express it by a series expansion involving all iterates of function \(h\) . This allows us to determine empty queue probabilities along with the tail of the workload distribution in each queue. This tail appears to be identical to that of the head-of-line preemptive priority system, which is the key feature desired for the SQF discipline.     

Stability analysis of N-model systems under a static priority rule

We consider the stability of N-model systems that consist of two customer classes and two server pools. Servers in one of the pools can serve both classes, but those in the other pool can serve only one of the classes. The standard fluid models in general are not sufficient to establish the stability region of these systems under static priority policies. Therefore, we use a novel and a general approach to augment the fluid model equations based on induced Markov chains. Using this new approach, we establish the stability region of these systems under a static priority rule with thresholds when the service and interarrival times have phase-type distributions. We show that, in certain cases, the stability region depends on the distributions of the service and interarrival times (beyond their mean), on the number of servers in the system, and on the threshold value. We also show that it is possible to expand the stability region in these systems by increasing the variability of the service times (without changing their mean) while keeping the other parameters fixed. The extension of our results to parallel server systems and general service time distributions is also discussed.     

Stability analysis of linear impulsive differential systems under structural perturbation

The stability and asymptotic stability of the solutions of large-scale linear impulsive systems under structural perturbations are investigated. Sufficient conditions for stability and instability are formulated in terms of the fixed signs of special matrices.

---

Аналіз стійкості лінійних диференціальних імпу льсних систем із структурними зБуреннями

Досліджуються стійкість та асимптотична стійкість возв'язків великомасштабної лінійної імпульсної системи при структурних збуреннях. Достатні умови стійкості та нестійкості сформульовані на основі знаковизначеності спеціальних матриць.

---

---

This work was done while the author was visiting the Department of Mathematics, University of Ioannina, in the framwork of the NATO Science Fellowships Programme through the Greek Ministry of National Economy.     

Analysis of a single server queue with semi-Markovian service interruption

In this paper we analyze a discrete-time single server queue where the service time equals one slot. The numbers of arrivals in each slot are assumed to be independent and identically distributed random variables. The service process is interrupted by a semi-Markov process, namely in certain states the server is available for service while the server is not available in other states. We analyze both the transient and steady-state models. We study the generating function of the joint probability of queue length, the state and the residual sojourn time of the semi-Markov process. We derive a system of Hilbert boundary value problems for the generating functions. The system of Hilbert boundary value problems is converted to a system of Fredholm integral equations. We show that the system of Fredholm integral equations has a unique solution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal control of parallel server systems with many servers in heavy traffic

We consider a parallel server system that consists of several customer classes and server pools in parallel. We propose a simple robust control policy to minimize the total linear holding and reneging costs. We show that this policy is asymptotically optimal under the many-server heavy traffic regime for parallel server systems when the service times are only server pool dependent and exponentially distributed. J.G. Dai’s research supported in part by National Science Foundation grants CMMI-0727400 and CNS-0718701, and by an IBM Faculty Award.     

Stability analysis of queueing systems

This paper contains a survey of some results on the stability of queueing systems obtained by the authors by means of the method of trial functions (developed from Lyapunov's direct method). In addition, the paper contains a series of new results on the stability of regenerative processes. All the qualitative statements are accompanied by the construction of quantitative estimates.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 87, pp. 41–61, 1979.     

An M/G/1 queue under hysteretic vacation policy with an early startup and un-reliable server

This paper considers the bi-level control of an M/G/1 queueing system, in which an un-reliable server operates N policy with a single vacation and an early startup. The server takes a vacation of random length when he finishes serving all customers in the system (i.e., the system is empty). Upon completion of the vacation, the server inspects the number of customers waiting in the queue. If the number of customers is greater than or equal to a predetermined threshold m, the server immediately performs a startup time; otherwise, he remains dormant in the system and waits until m or more customers accumulate in the queue. After the startup, if there are N or more customers waiting for service, the server immediately begins serving the waiting customers. Otherwise the server is stand-by in the system and waits until the accumulated number of customers reaches or exceeds N. Further, it is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. We obtain the probability generating function in the system through the decomposition property and then derive the system characteristics     

Stability analysis of switched homogeneous time-delay systems under synchronous and asynchronous commutation

In this work, stability analysis for a class of switched nonlinear time-delay systems is performed by applying Lyapunov–Krasovskii and Lyapunov–Razumikhin approaches. It is assumed that each subsystem in the family is homogeneous (of positive or negative degree) and asymptotically stable in the delay-free setting. The cases of existence of a common or multiple Lyapunov–Krasovskii functionals and a common Lyapunov–Razumikhin function are explored. The scenarios with synchronous and asynchronous switching are considered, and it is demonstrated that depending on the kind of commutation, one of the frameworks for stability analysis outperforms another, but finally leading to similar restrictions for both types of switching (despite the asynchronous one seems to be more demanded). The obtained results are applied to mechanical systems having restoring forces with real-valued powers.     

Extreme and high-level sojourns of the single server queue in heavy traffic

This study characterizes the behavior of large queue lengths in heavy traffic. We show that the distribution of the maximum queue length in a random time interval for a queueing systems in heavy traffic converges to a novel extreme value distribution. We also study the processes that record the times that the queue length exceeds a high level and the cumulative time the queue is above the level. We show that these processes converge in distribution to compound Poisson processes. This revised version was published online in June 2006 with corrections to the Cover Date.     

The equivalence of the transient behaviour formulae for the single server queue

It is indeed obvious to expect that the different results obtained for some problem are equal, but it needs to established. For the M/M/1/N queue, using a simple algebraic approach we will prove that the results obtained by Takâcs [17] Takâcs, L. 1960. Introduction to the Theory of Queues Oxford University Press.  [Google Scholar] and Sharma and Gupta [13] Sharma, O.P. and Gupta, U.C. 1982. Transient Behaviour of an M/M/l/N Queue. Stoch. Process Appl., 13: 327–331. [Crossref] , [Google Scholar] are equal. Furthermore, a direct proof to the equivalence between all formulae of the M/M/l/∞ queue is established. At the end of this paper, we will show that the time-dependent state probabilities for M/M/l/N queue can be written in series form; its coefficients satisfy simple recurrence relations which would allow for the rapid and efficient evaluation of the state probabilities. Moreover, a brief comparison of our technique, Sharma and Gupta's formula and Takâcs result is also given, for the CPU time computing the state probabilities.