对一类等待空间有限的抢占优先权排队的分析

讨论M/M/1抢占优先权排队模型, 且假设低优先权顾客的等待空间有限. 该模型可以用有限位相拟生灭过程来描述. 由矩阵解析方法, 对该拟生灭过程进行了分析, 并得到排队模型平稳队长的计算公式, 最后还用数值 结果说明了方法的有效性.     

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.     

On finite capacity queues with time dependent arrival rates

We consider the finite capacity M/M/1−K$M/M/1-K$ queue with a time dependent arrival rate λ(t)$\lambda \left(t\right)$. Assuming that the capacity K$K$ is large and that the arrival rate varies slowly with time (as t/K$t/K$), we construct asymptotic approximations to the probability of finding n$n$ customers in the system at time t$t$, as well as the mean number. We consider various time ranges, where the system is nearly empty, nearly full, or is filled to a fraction of its capacity. Extensive numerical studies are used to back up the asymptotic analysis.     

Loss probability in a finite discrete-time queue in terms of the steady state distribution of an infinite queue

We consider a discrete-time single-server queue with arrivals governed by a stationary Markov chain, where no arrivals are assumed to occur only when the Markov chain is in a particular state. This assumption implies that off-periods in the arrival process are i.i.d. and geometrically distributed. For this queue, we establish the exact relationship between queue length distributions in a finite-buffer queue and the corresponding infinite-buffer queue. With the result, the exact loss probability is obtained in terms of the queue length distribution in the corresponding infinite-buffer queue. Note that this result enables us to compute the loss probability very efficiently, since the queue length distribution in the infinite-buffer queue can be efficiently computed when off-periods are geometrically distributed. This revised version was published online in June 2006 with corrections to the Cover Date.     

Economic application in a finite capacity multi-channel queue with second optional channel

We consider a finite capacity M/M/R queue with second optional channel. The interarrival times of arriving customers follow an exponential distribution. The service times of the first essential channel and the second optional channel are assumed to follow an exponential distribution. As soon as the first essential service of a customer is completed, a customer may leave the system with probability (1 − θ) or may opt for the second optional service with probability θ (0 ? θ ? 1). Using the matrix-geometric method, we obtain the steady-state probability distributions and various system performance measures. A cost model is established to determine the optimal solutions at the minimum cost. Finally, numerical results are provided to illustrate how the direct search method and the tabu search can be applied to obtain the optimal solutions. Sensitivity analysis is also investigated.     

Equilibrium arrival times to a queue with order penalties

Suppose customers need to choose when to arrive to a congested queue with some desired service at the end, provided by a single server that operates only during a certain time interval. We study a model where the customers incur not only congestion (waiting) costs but also penalties for their index of arrival. Arriving before other customers is desirable when the value of service decreases with every admitted customer. This may be the case for example when arriving at a concert or a bus with unmarked seats or going to lunch in a busy cafeteria. We provide game theoretic analysis of such queueing systems with a given number of customers, specifically we characterize the arrival process which constitutes a symmetric Nash equilibrium.     

Discrete-time analysis of a classified multi-server queue with burst arrivals and a shared buffer

We study a discrete-time, classified multi-server queue with a shared buffer. There arem servers and each server belongs to one ofk classes (mk), so thatk kinds of jobs can be served in the system. We characterize a bursty arrival process using bursts which consist of the same kind of jobs. Once the first job of a burst arrives at the queue, the successive jobs will arrive on every time slot until the last job of the burst arrives. The numbers of jobs of a burst and the inter-arrival times of bursts are assumed to be i.i.d., respectively, and the service time is assumed to be equal to one slot. We propose an efficient numerical method to exactly obtain the job loss probability, the waiting time distribution and the mean queue length. We apply this model to the ATM switch with a shared buffer and obtain the performance measures. Numerical results show the advantage of the ATM switch with a shared buffer compared to the one with output buffers.     

Stationary analysis of a discrete-time GI/D-MSP/1 queue with multiple vacations

This paper analyzes the steady-state behavior of a discrete-time single-server queueing system with correlated service times and server vacations. The vacation times of the server are independent and geometrically distributed, and their durations are integral multiples of slot duration. The customers are served one at a time under discrete-time Markovian service process. The new service process starts with the initial phase distribution independent of the path followed by the previous service process when the server returns from a vacation and finds at least one waiting customer. The matrix-geometric method is used to obtain the probability distribution of system-length at prearrival epoch. With the help of Markov renewal theory approach, we also derive the system-length distribution at an arbitrary epoch. The analysis of actual-waiting-time distribution in the queue measured in slots has also been carried out. In addition, computational experiences with a variety of numerical results are discussed to display the effect of the system parameters on the performance measures.     

On sojourn times in the finite capacity queue with processor sharing

We consider a processor shared M/M/1 queue that can accommodate at most a finite number K of customers. We give an exact expression for the sojourn time distribution in this finite capacity model, in terms of a Laplace transform. We then give the tail behavior, for the limit K→∞.     

Analysis of stationary discrete-time GI/D-MSP/1 queue with finite and infinite buffers

This paper considers a single-server queueing model with finite and infinite buffers in which customers arrive according to a discrete-time renewal process. The customers are served one at a time under discrete-time Markovian service process (D-MSP). This service process is similar to the discrete-time Markovian arrival process (D-MAP), where arrivals are replaced with service completions. Using the imbedded Markov chain technique and the matrix-geometric method, we obtain the system-length distribution at a prearrival epoch. We also provide the steady-state system-length distribution at an arbitrary epoch by using the supplementary variable technique and the classical argument based on renewal-theory. The analysis of actual-waiting-time (in the queue) distribution (measured in slots) has also been investigated. Further, we derive the coefficient of correlation of the lagged interdeparture intervals. Moreover, computational experiences with a variety of numerical results in the form of tables and graphs are discussed.     

The discrete-time queue with autoregressive inputs revisited

In this paper, we present an exact queuing analysis of a discrete-time queue whose arrival process is correlated and consists of a discrete autoregressive model of order 1 (DAR(1)). The functional equation describing this DAR(1)/D/1 queuing model, originally derived in Hwang and Sohraby (Queuing Systems 43 (2003)29–41), is manipulated and transformed into a mathematical tractable form. By using simple analytical transform techniques, we show how our proposed approach allows us to derive an equivalent (yet simpler) expression for the steady-state probability generating function (pgf) of the queue length, as originally derived in Hwang and Sohraby (Queuing Systems 43 (2003)29–41). From this pgf, we characterize the distribution of the packet delay. New numerical results related to packet loss ratio and mean delay of the DAR(1)/D/1 queue are also presented. The proposed approach outlines an alternate solution technique and a general framework under which more complex time-series based queuing models can be analyzed. AMS Subject Classifications 60K25     

A discrete-time single-server queue with set-up time

This paper studies a generalization of the GI/G/1 queueing system in which there is a random ‘set-up’ time for customers who arrive when the server is idle. Mathematical methods are given for finding various transient characteristics of the system.     

Quasi-reversibility of a discrete-time queue and related models

We consider a discrete-time queueing system and its application to related models. The model is defined byX _n+1=X_n+A_n-D_n+1 with discrete states, whereX _n is the queue-length at the nth time epoch,A _n is the number of arrivals at the start of the nth slot andD _n+1 is the number of outputs at the end of the nth slot. In this model, the arrival process {A _n} is described as a sequence of independently and identically distributed random variables. The departureD _n+1 depends only on the system sizeX _n+A_n at the beginning of the time slot.We study the reversibility for the model. The departure discipline in which the system has quasi-reversibility is determined. Models with special arrival processes were studied by Walrand [8] and sawa [7]. In this paper, we generalize their results. Moreover, we consider discrete-time queueing networks with some reversible nodes. We then obtain the product-form solution for these networks.     

A single-server batch arrival queue with returning customers

We consider a new class of batch arrival retrial queues. By contrast to standard batch arrival retrial queues we assume if a batch of primary customers arrives into the system and the server is free then one of the customers starts to be served and the others join the queue and then are served according to some discipline. With the help of Lyapunov functions we have obtained a necessary and sufficient condition for ergodicity of embedded Markov chain and the joint distribution of the number of customers in the queue and the number of customers in the orbit in steady state. We also have suggested an approximate method of analysis based on the corresponding model with losses.     

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.     

批到达M/G/1重试排队的队长的尾渐近

用随机分解法研究成批到达服务时间为次指数分布的重试排队中队长的尾行为,得到了该系统与其相应的标准排队系统队长尾分布的关系;对次指数尾,结果也能用于正则变化尾,进而得到正则变化尾渐近．     

Performance analysis of discrete-time queue GI/G/1 with negative arrivals

In this paper, we consider a discrete-time GI/G/1 queueing model with negative arrivals. By deriving the probability generating function of actual service time of ordinary customers, we reduced the analysis to an equivalent discrete-time GI/G/1 queueing model without negative arrival, and obtained the probability generating function of buffer contents and random customer delay.     

A discrete-time retrial queue with multiplicative repeated attempts

The repeated attempts have been always made individually by each unsatisfied customer in discrete-time retrial queues. However, the time between two consecutive repeated requests can be independent of the number of customers applying for service. This paper considers a new retrial discipline, that we call multiplicative, which extends both types of repeated attempts.