具有位相型修理的离散时间可修排队系统

本文研究了具有一般独立输入，位相型修理的离散时间可修排队系统，假定服务台对顾客的服务时间和服务台寿命服从几何分布，运用矩阵解析方法我们给出系统嵌入在到达时刻的稳态队长分布和等待时间分布，并证明这些分布均为离散位相型分布．我们也得到在广义服务时间内服务台发生故障次数的分布，证明它服从一个修正的几何分布．我们对离散时间可修排队与连续时间可修排队进行了比较，说明这两种排队系统在一些性能指标方面的区别之处．最后我们通过一些数值例子说明在这类系统中顾客的到达过程、服务时间和服务台的故障率之间的关系．     

离散时间服务台可修的排队系统MAP／PH（PH／PH）／1

本文研究离散时间可修排队系统,其中顾客的输入过程为离散马尔可夫到达过程（MAP）,服务台的寿命,服务台的顾客的服务时间和修理时间均为离散位相型（PH）变量,首先我们考虑广义服务过程,证明它是离散MAP,然后运用阵阵几何解理论,我们给出了系统的稳态队长分布和稳态等待时间分布,同时给出了系统的稳态可用度这一可靠性指标。     

Performance Analysis of the GI/M/1 Queue with Single Working Vacation and Vacations

In this paper, we consider a new class of the GI/M/1 queue with single working vacation and vacations. When the system become empty at the end of each regular service period, the server first enters a working vacation during which the server continues to serve the possible arriving customers with a slower rate, after that, the server may resume to the regular service rate if there are customers left in the system, or enter a vacation during which the server stops the service completely if the system is empty. Using matrix geometric solution method, we derive the stationary distribution of the system size at arrival epochs. The stochastic decompositions of system size and conditional system size given that the server is in the regular service period are also obtained. Moreover, using the method of semi-Markov process (SMP), we gain the stationary distribution of system size at arbitrary epochs. We acquire the waiting time and sojourn time of an arbitrary customer by the first-passage time analysis. Furthermore, we analyze the busy period by the theory of limiting theorem of alternative renewal process. Finally, some numerical results are presented.     

离散时间排队MAP/PH/3

本文研究具有马尔可夫到达过程的离散时间排队MAP/PH/3,系统中有三个服务台,每个服务台对顾客的服务时间均服从位相型分布。运用矩阵几何解的理论,我们给出了系统平稳的充要条件和系统的稳态队长分布。同时我们也给出了到达顾客所见队长分布和平均等待时间。     

Analysis of M/M/S queues with 1-limited service

In this paper, a multiple server queue, in which each server takes a vacation after serving one customer is studied. The arrival process is Poisson, service times are exponentially distributed and the duration of a vacation follows a phase distribution of order 2. Servers returning from vacation immediately take another vacation if no customers are waiting. A matrix geometric method is used to find the steady state joint probability of number of customers in the system and busy servers, and the mean and the second moment of number of customers and mean waiting time for this model. This queuing model can be used for the analysis of different kinds of communication networks, such as multi-slotted networks, multiple token rings, multiple server polling systems and mobile communication systems.     

Matrix analytic methods for a multi-server retrial queue with buffer

We present numerical methods for obtaining the stationary distribution of states for multi-server retrial queues with Markovian arrival process, phase type service time distribution with two states and finite buffer; and moments of the waiting time. The methods are direct extensions of the ones for the single server retrial queues earlier developed by the authors. The queue is modelled as a level dependent Markov process and the generator for the process is approximated with one which is spacially homogeneous above some levelN. The levelN is chosen such that the probability associated with the homogeneous part of the approximated system is bounded by a small tolerance and the generator is eventually truncated above that level. Solutions are obtained by efficient application of block Gaussian elimination.     

A recursive method to the optimal control of an M/G/1 queueing system with finite capacity and infinite capacity

We study a single removable server in an infinite and a finite queueing systems with Poisson arrivals and general distribution service times. The server may be turned on at arrival epochs or off at service completion epochs. We present a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining service time, to obtain the steady state probability distribution of the number of customers in a finite system. The method is illustrated analytically for three different service time distributions: exponential, 3-stage Erlang, and deterministic. Cost models for infinite and finite queueing systems are respectively developed to determine the optimal operating policy at minimum cost.     

Analysis of a finite MAP/G/1 queue with group services

The finite capacity queues, GI/PH/1/N and PH/G/1/N, in which customers are served in groups of varying sizes were recently introduced and studied in detail by the author. In this paper we consider a finite capacity queue in which arrivals are governed by a particular Markov renewal process, called a Markovian arrival process (MAP). With general service times and with the same type of service rule, we study this finite capacity queueing model in detail by obtaining explicit expressions for (a) the steady-state queue length densities at arrivals, at departures and at arbitrary time points, (b) the probability distributions of the busy period and the idle period of the server and (c) the Laplace-Stieltjes transform of the stationary waiting time distribution of an admitted customer at points of arrivals. Efficient algorithmic procedures for computing the steady-state queue length densities and other system performance measures when services are of phase type are discussed. An illustrative numerical example is presented.     

Analysis of a Two‐Phase Queueing System with Vacations and Bernoulli Feedback

Abstract

We consider a two‐phase queueing system with server vacations and Bernoulli feedback. Customers arrive at the system according to a Poisson process and receive batch service in the first phase followed by individual services in the second phase. Each customer who completes the individual service returns to the tail of the second phase service queue with probability 1 ? σ. If the system becomes empty at the moment of the completion of the second phase services, the server takes vacations until he finds customers. This type of queueing problem can be easily found in computer and telecommunication systems. By deriving a relationship between the generating functions for the system size at various embedded epochs, we obtain the system size distribution at an arbitrary time. The exhaustive and gated cases for the batch service are considered.     

Analysis of the MAP/G a ,b /1/N Queue

The Markovian arrival process (MAP) is used to represent the bursty and correlated traffic arising in modern telecommunication network. In this paper, we consider a single server finite capacity queue with general bulk service rule in which arrivals are governed by MAP and service times are arbitrarily distributed. The distributions of the number of customers in the queue at arbitrary, post-departure and pre-arrival epochs have been obtained using the supplementary variable and the embedded Markov chain techniques. Computational procedure has been given when the service time distribution is of phase type.     

The BMAP/PH/N retrial queue with Markovian flow of breakdowns

We consider a multi-server retrial queue with the Batch Markovian Arrival Process (BMAP). The servers are identical and independent of each other. The service time distribution of a customer by a server is of the phase (PH) type. If a group of primary calls meets idle servers the primary calls occupy the corresponding number of servers. If the number of idle servers is insufficient the rest of calls go to the orbit of unlimited size and repeat their attempts to get service after exponential amount of time independently of each other. Busy servers are subject to breakdowns and repairs. The common flow of breakdowns is the MAP. An event of this flow causes a failure of any busy server with equal probability. When a server fails the repair period starts immediately. This period has PH type distribution and does not depend on the repair time of other broken-down servers and the service time of customers occupying the working servers. A customer whose service was interrupted goes to the orbit with some probability and leaves the system with the supplementary probability. We derive the ergodicity condition and calculate the stationary distribution and the main performance characteristics of the system. Illustrative numerical examples are presented.     

Tail probabilities for M/G/∞ input processes (I): Preliminary asymptotics

The infinite server model of Cox with arbitrary service time distribution appears to provide a large class of traffic models - Pareto and log-normal distributions have already been reported in the literature for several applications. Here we begin the analysis of the large buffer asymptotics for a multiplexer driven by this class of inputs. To do so we rely on recent results by Duffield and O’Connell on overflow probabilities for the general single server queue. In this paper we focus on the key step in this approach: The appropriate large deviations scaling is shown to be related to the forward recurrence time of the service time distribution, and a closed form expression is derived for the corresponding generalized limiting log-moment generating function associated with the input process. Three different regimes are identified. In a companion paper we apply these results to obtain the large buffer asymptotics under a variety of service time distributions. This revised version was published online in June 2006 with corrections to the Cover Date.     

服务台休假的GI/Geom/1离散时间排队

本文研究了具有位相型休假、位相型启动和单重几何休假的离散时间排队,假定 顾客到达间隔服从一般分布,服务时间服从几何分布,运用矩阵解析方法我们得到了这 些排队系统中顾客在到达时刻稳态队长分布及其随机分解.     

Profit maximization in flexible serial queueing networks

We analyze the tradeoff between efficiency and service quality in tandem systems with flexible servers and finite buffers. We reward efficiency by assuming that a revenue is earned each time a job is completed, and penalize poor service quality by incorporating positive holding costs. We study the dynamic assignment of servers to tasks with the objective of maximizing the long-run average profit. For systems of arbitrary size, structured service rates, and linear or nonlinear holding costs, we determine the server assignment policy that maximizes the profit. For systems with two stations, two servers with arbitrary service rates, and linear holding costs, we show that the optimal server assignment policy is of threshold type and determine the value of this threshold as a function of the revenue and holding cost. The threshold can be interpreted as the best possible buffer size, and hence our results prove the equivalence of addressing service quality via a holding cost and via limiting the buffer size. Furthermore, we identify the optimal buffer size when each buffer space comes at a cost. We provide numerical results that suggest that the optimal policy also has a threshold structure for nonlinear holding costs. Finally, for larger systems with arbitrary service rates, we propose effective server assignment heuristics.     

Working vacations queueing model with multiple types of server breakdowns

This paper deals with a single server working vacation queueing model with multiple types of server breakdowns. In a working vacations queueing model, the server works at a different rate instead of being completely idle during the vacation period; the arrival rate varies according to the server’s status. It is assumed that the server is subject to interruption due to multiple types of breakdowns and is sent immediately for repair. Each type of breakdown requires a finite random number of stages of repair. The life time of the server and the repair time of each phase are assumed to be exponentially distributed. We propose a matrix–geometric approach for computing the stationary queue length distribution. Various performance indices namely the expected length of busy period, the expected length of working vacation period, the mean waiting time and average delay, etc. are established. In order to validate the analytical approach, by taking illustration, we compute numerical results. The sensitivity analysis is also performed to explore the effect of different parameters.     

Analysis of the MAP/PH/1/K queue with service control

We consider a finite capacity queue with Markovian arrivals, in which the service rates are controlled by two pre-determined thresholds, M and N. The service rate is increased when the buffer size exceeds N and then brought back to normal service rate when the buffer size drops to M. The normal and fast service times are both assumed to be of phase type with representations (β, S), and β θS), respectively, where θ>1. For this queueing model, steady state analysis is performed. The server duration in normal as well as fast periods is shown to be of phase type. The departure process is modelled as a MAP and the parameter matrices of the MAP are identified. Efficient algorithms for computing system performance measures are presented. We also discuss an optimization problem and present an efficient algorithm for arriving at an optimal solution. Some numerical examples are discussed.     

A server backup model with Markovian arrivals and phase type services

We consider a finite capacity queueing system with one main server who is supported by a backup server. We assume Markovian arrivals, phase type services, and a threshold-type server backup policy with two pre-determined lower and upper thresholds. A request for a backup server is made whenever the buffer size (number of customers in the queue) hits the upper threshold and the backup server is released from the system when the buffer size drops to the lower threshold or fewer at a service completion of the backup server. The request time for the backup server is assumed to be exponentially distributed. For this queuing model we perform the steady state analysis and derive a number of performance measures. We show that the busy periods of the main and backup servers, the waiting times in the queue and in the system, are of phase type. We develop a cost model to obtain the optimal threshold values and study the impact of fixed and variable costs for the backup server on the optimal server backup decisions. We show that the impact of standard deviations of the interarrival and service time distributions on the server backup decisions is quite different for small and large values of the arrival rates. In addition, the pattern of use of the backup server is very different when the arrivals are positively correlated compared to mutually independent arrivals.     

Analysis of an SPP/G/1 system with multiple vacations and E-limited service discipline

Many researchers have studied variants of queueing systems with vacations. Most of them have dealt with M/G/1 systems and have explicitly analyzed some of their performance measures, such as queue length, waiting time, and so on. Recently, studies on queueing systems whose arrival processes are not Poissonian have appeared. We consider a single server queueing system with multiple vacations and E-limited service discipline, where messages arrive to the system according to a switched Poisson process. First, we consider the joint probability density functions of the queue length and the elapsed service time or the elapsed vacation time. We derive the equations for these pdf's, which include a finite number of unknown values. Using Rouché's theorem, we determine the values from boundary conditions. Finally, we derive the transform of the stationary queue length distribution explicitly.     

A tandem GI/PH/1→•/PH/1/0 queue with blocking

Tandem queues are widely used in mathematical modeling of random processes describing the operation of manufacturing systems, supply chains, computer and telecommunication networks. Although there exists a lot of publications on tandem queueing systems, analytical research on tandem queues with non-Markovian input is very limited. In this paper, the results of analytical investigation of two-node tandem queue with arbitrary distribution of inter-arrival times are presented. The first station of the tandem is represented by a single-server queue with infinite waiting room. After service at the first station, a customer proceeds to the second station that is described by a single-server queue without a buffer. Service times of a customer at the first and the second server have PH (Phase-type) distributions. A customer, who completes service at the first server and meets a busy second server, is forced to wait at the first server until the second server becomes available. During the waiting period, the first server becomes blocked, i.e., not available for service of customers. We calculate the joint stationary distribution of the system states at the embedded epochs and at arbitrary time. The Laplace–Stieltjes transform of the sojourn time distribution is derived. Key performance measures are calculated and numerical results presented.