A single server queue with gated processor-sharing discipline

In this paper we consider a single server queue in which arrivals occur according to a Poisson process and each customer's service time is exponentially distributed. The server works according to the gated process-sharing discipline. In this discipline, the server provides service to a batch of at mostm customers at a time. Once a batch of customers begins service, no other waiting customer can receive service until all members of the batch have completed their service. For this queue, we derive performance characteristics, such as waiting time distribution, queue length distribution etc. For this queue, it is possible to obtain the mean conditional response time for a customer whose service time is known. This conditional response time is a nonlinear function (as opposed to the linear case for the ordinary processor-sharing queue). A special case of the queue (wherem=) has an interesting and unusual solution. For this special case, the size of the batch for service is a Markov chain whose steady state distribution can be explicitly written down. Apart from the contribution to the theory of Markov chains and queues, the model may be applicable to scheduling of computer and communication systems.     

Single-Server Queues with Markov-Modulated Arrivals and Service Speed

This paper considers single-server queues with several customer classes. Arrivals of customers are governed by the underlying continuous-time Markov chain with finite states. The distribution of the amount of work brought into the system on arrival is assumed to be general, which may differ with different classes. Further, the service speed depends on the state of the underlying Markov chain. We first show that given such a queue, we can construct the corresponding new queue with constant service speed by means of a change of time scale, and the time-average quantities of interest in the original queue are given in terms of those in the new queue. Next we characterize the joint distribution of the length of a busy period and the number of customers served during the busy period in the original queue. Finally, assuming the FIFO service discipline, we derive the Laplace–Stieltjes transform of the actual waiting time distribution in the original queue.     

The $$MMAP\left[ K \right]/PH\left[ K \right]/1$$ queues with a last-come-first-served preemptive service discipline

This paper studies two queueing systems with a Markov arrival process with marked arrivals and PH-distribution service times for each type of customer. Customers (regardless of their types) are served on a last-come-first-served preemptive resume and repeat basis, respectively. The focus is on the stationary distribution of queue strings in the system and busy periods. Efficient algorithms are developed for computing the stationary distribution of queue strings, the mean numbers of customers served in a busy period, and the mean length of a busy period. Comparison is conducted numerically between performance measures of queueing systems with preemptive resume and preemptive repeat service disciplines. A counter-intuitive observation is that for a class of service time distributions, the repeat discipline performs better than the resume one. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analysis of the M1,M2/G/1 G-queueing system with retrial customers

We consider a single server retrial queue with waiting places in service area and three classes of customers subject to the server breakdowns and repairs. When the server is unavailable, the arriving class-1 customer is queued in the priority queue with infinite capacity whereas class-2 customer enters the retrial group. The class-3 customers which are also called negative customers do not receive service. If the server is found serving a customer, the arriving class-3 customer breaks the server down and simultaneously deletes the customer under service. The failed server is sent to repair immediately and after repair it is assumed as good as new. We study the ergodicity of the embedded Markov chains and their stationary distributions. We obtain the steady-state solutions for both queueing measures and reliability quantities. Moreover, we investigate the stochastic decomposition law, the busy period of the system and the virtual waiting times. Finally, an application to cellular mobile networks is provided and the effects of various parameters on the system performance are analyzed numerically.     

Quasi-birth-and-death Markov processes with a tree structure and the MMAP[K]/PH[K]/N/LCFS non-preemptive queue

This paper studies a multi-server queueing system with multiple types of customers and last-come-first-served (LCFS) non-preemptive service discipline. First, a quasi-birth-and-death (QBD) Markov process with a tree structure is defined and some classical results of QBD Markov processes are generalized. Second, the MMAP[K]/PH[K]/N/LCFS non-preemptive queue is introduced. Using results of the QBD Markov process with a tree structure, explicit formulas are derived and an efficient algorithm is developed for computing the stationary distribution of queue strings. Numerical examples are presented to show the impact of the correlation and the pattern of the arrival process on the queueing process of each type of customer.     

Age Process, Workload Process, Sojourn Times, and Waiting Times in a Discrete Time SM[K]/PH[K]/1/FCFS Queue

In this paper, we study a discrete time queueing system with multiple types of customers and a first-come-first-served (FCFS) service discipline. Customers arrive according to a semi-Markov arrival process and the service times of individual customers have PH-distributions. A GI/M/1 type Markov chain for a generalized age process of batches of customers is introduced. The steady state distribution of the GI/M/1 type Markov chain is found explicitly and, consequently, the steady state distributions of the age of the batch in service, the total workload in the system, waiting times, and sojourn times of different batches and different types of customers are obtained. We show that the generalized age process and a generalized total workload process have the same steady state distribution. We prove that the waiting times and sojourn times have PH-distributions and find matrix representations of those PH-distributions. When the arrival process is a Markov arrival process with marked transitions, we construct a QBD process for the age process and the total workload process. The steady state distributions of the waiting times and the sojourn times, both at the batch level and the customer level, are obtained from the steady state distribution of the QBD process. A number of numerical examples are presented to gain insight into the waiting processes of different types of customers.AMS subject classification: 60K25, 60J10This revised version was published online in June 2005 with corrected coverdate     

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.     

A BMAP/SM/1 queue with service times depending on the arrival process

We study a BMAP/>SM/1 queue with batch Markov arrival process input and semi‐Markov service. Service times may depend on arrival phase states, that is, there are many types of arrivals which have different service time distributions. The service process is a heterogeneous Markov renewal process, and so our model necessarily includes known models. At first, we consider the first passage time from level {κ+1} (the set of the states that the number of customers in the system is κ+1) to level {κ} when a batch arrival occurs at time 0 and then a customer service included in that batch simultaneously starts. The service descipline is considered as a LIFO (Last‐In First‐Out) with preemption. This discipline has the fundamental role for the analysis of the first passage time. Using this first passage time distribution, the busy period length distribution can be obtained. The busy period remains unaltered in any service disciplines if they are work‐conserving. Next, we analyze the stationary workload distribution (the stationary virtual waiting time distribution). The workload as well as the busy period remain unaltered in any service disciplines if they are work‐conserving. Based on this fact, we derive the Laplace–Stieltjes transform for the stationary distribution of the actual waiting time under a FIFO discipline. In addition, we refer to the Laplace–Stieltjes transforms for the distributions of the actual waiting times of the individual types of customers. Using the relationship between the stationary waiting time distribution and the stationary distribution of the number of customers in the system at departure epochs, we derive the generating function for the stationary joint distribution of the numbers of different types of customers at departures. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal admission policies for a finite queue with bursty arrivals

We consider a service system with a single server, a finite waiting room and two classes of customers with deterministic service time. Primary jobs arrive at random and are admitted whenever there is room in the system. At the beginning of each period, secondary jobs can be admitted from an infinite pool. A revenue is earned upon admission of each job, with the primary jobs bringing a higher contribution than the secondary jobs, the objective being to maximize the total discounted revenue over an infinite horizon. We model the system as a discrete time Markov decision process and show that a monotone admission policy is optimal when the number of primary arrivals has a fixed distribution. Moreover, when the primary arrival distribution varies with time according to a finite state Markov chain, we show that the optimal policy is conditionally monotone and that the numerical computation of an optimal policy, in this case, is substantially more difficult than in the case of stationary arrivals.This research was supported in part by the National Science Foundation, under grant ECS-8803061, while the author was at the University of Arizona.     

有Bernoulli休假和可选服务的M/G/1重试反馈排队模型

考虑具有可选服务的M/G/1重试反馈排队模型,其中服务台有Bernoulli休假策略.系统外新到达的顾客服从参数为λ的泊松过程.重试区域只允许队首顾客重试,重试时间服从一般分布.所有的顾客都必须接受必选服务,然而只有其中部分接受可选服务.每个顾客每次被服务完成后可以离开系统或者返回到重试区域.服务台完成一次服务以后,可以休假也可以继续为顾客服务.通过嵌入马尔可夫链法证明了系统稳态的充要条件.利用补充变量的方法得到了稳态时系统和重试区域中队长分布.我们还得到了重试期间服务台处于空闲的概率,重试区域为空的概率以及其他各种指标.并证出在系统中服务员休假和服务台空闲的时间定义为广义休假情况下也具有随机分解特征.     

Optimal utilization of service facility for ak-out-of-n system with repair by extending service to external customers in a retrial queue

In this paper, we study ak-out-of-n system with single server who provides service to external customers also. The system consists of two parts: (i) a main queue consisting of customers (failed components of thek-out-of-n system) and (ii) a pool (of finite capacityM) of external customers together with an orbit for external customers who find the pool full. An external customer who finds the pool full on arrival, joins the orbit with probability γ and with probability 1- γ leaves the system forever. An orbital customer, who finds the pool full, at an epoch of repeated attempt, returns to orbit with probability δ (< 1) and with probability 1- δ leaves the system forever. We compute the steady state system size probability. Several performance measures are computed, numerical illustrations are provided.     

The MAP/(PH/PH)/1 queue with self-generation of priorities and non-preemptive service

Customers arriving according to a Markovian arrival process are served at a single server facility. Waiting customers generate priority at a constant rate γ$\gamma$; such a customer waits in a waiting space of capacity 1 if this waiting space is not already occupied by a priority generated customer; else it leaves the system. A customer in service will be completely served before the priority generated customer is taken for service (non-preemptive service discipline). Only one priority generated customer can wait at a time and a customer generating into priority at that time will have to leave the system in search of emergency service elsewhere. The service times of ordinary and priority generated customers follow PH-distributions. The matrix analytic method is used to compute the steady state distribution. Performance measures such as the probability of n consecutive services of priority generated customers, the probability of the same for ordinary customers, and the mean waiting time of a tagged customer are found by approximating them by their corresponding values in a truncated system. All these results are supported numerically.     

Single line queue with repeated demands

We analyze a model of a queueing system in which customers can only call in to request service: if the server is free, the customer enters service immediately, but if the service system is occupied, the unsatisfied customer must break contact and reinitiate his request later. Such a customer is said to be in “orbit”. In this paper we consider three models characterized by the discipline governing the order of re-request of service from orbit. First, all customers in orbit can reapply, but are discouraged and reduce their rate of demand as more customers join the orbit. Secondly, the FCFS discipline operates for the unsatisfied customers in orbit. Finally, the LCFS discipline governs the customers in orbit and the server takes an exponentially distributed vacation after each service is completed. We calculate several characteristics quantities of such systems, assuming a general service-time distribution and different exponential distributions for the times between arrivals of first and repeat requests.     

Numerical computation of response time distributions using stochastic reward nets

We consider the numerical computation of response time distributions for closed product form queueing networks using thetagged customer approach. We map this problem on to the computation of the time to absorption distribution of a finite-state continuous time Markov chain. The construction and solution of these Markov chains is carried out using a variation of stochastic Petri nets called stochastic reward nets (SRNs). We examine the effects of changing the service discipline and the service time distribution at a queueing center on the response time distribution. A multiserver queueing network example is also presented. While the tagged customer approach for computing the response time distribution is not new, this paper presents a new approach for computing the response time distributions using SRNs.This research was sponsored in part by the National Science Foundation under Grant CCR-9108114 and by the Naval Surface Warfare Center under contract N60921-92-C-0161.     

Mixed gated/exhaustive service in a polling model with priorities

In this paper we consider a single-server polling system with switch-over times. We introduce a new service discipline, mixed gated/exhaustive service, that can be used for queues with two types of customers: high and low priority customers. At the beginning of a visit of the server to such a queue, a gate is set behind all customers. High priority customers receive priority in the sense that they are always served before any low priority customers. But high priority customers have a second advantage over low priority customers. Low priority customers are served according to the gated service discipline, i.e. only customers standing in front of the gate are served during this visit. In contrast, high priority customers arriving during the visit period of the queue are allowed to pass the gate and all low priority customers before the gate. We study the cycle time distribution, the waiting time distributions for each customer type, the joint queue length distribution of all priority classes at all queues at polling epochs, and the steady-state marginal queue length distributions for each customer type. Through numerical examples we illustrate that the mixed gated/exhaustive service discipline can significantly decrease waiting times of high priority jobs. In many cases there is a minimal negative impact on the waiting times of low priority customers but, remarkably, it turns out that in polling systems with larger switch-over times there can be even a positive impact on the waiting times of low priority customers.     

带负顾客和非空竭服务随机休假的M~([x])/G/1可修排队系统

研究了带负顾客和非空竭服务随机休假的M~([X])/G/1可修排队系统.负顾客不仅仅移除一个正在接受服务的正顾客,而且还使得服务器损坏而立即进行修理.通过构造一个具有吸收态的马尔可夫链求得了系统稳态存在的充分必要条件.利用补充变量法求得了系统的排队指标和可靠性指标.最后我们还给出了一个数值实例.     

有启动失败和可选服务的M/G/1重试排队系统

考虑具有可选服务的M/G/1重试排队模型,其中服务台有可能启动失败.系统外新到达的顾客服从参数为λ的泊松过程.重试区域只允许队首顾客重试,重试时间服务一般分布.所有的顾客都必须接受必选服务,然而只有其中部分接受可选服务.通过嵌入马尔可夫链法证明了系统稳态的充要条件.利用补充变量的方法得到了稳态时系统和重试区域中队长分布.我们还得到重试期间服务台处于空闲的概率,重试区域为空的概率以及其他各种指标.并证出在把系统中服务台空闲和修理的时间定义为广义休假情况下也具有随机分解特征.     

Matrix Product-Form Solution for an LCFS-PR Single-Server Queue with Multiple Arrival Streams Governed by a Markov Chain

This paper considers a stationary single-server queue with multiple arrival streams governed by a Markov chain, where customers are served on an LCFS preemptive-resume basis. Service times of customers from each arrival stream are generally distributed and service time distributions for different arrival streams may be different. Under these assumptions, it is shown that the stationary joint distribution of queue strings representing from which arrival stream each customer in the system arrived and remaining service times of respective customers in the system has a matrix product-form solution, where matrices constituting the solution are given in terms of the infinitesimal generator of a certain Markov chain. Compared with the previous works, the result in this paper is more general in the sense that general service time distributions are allowed, and it has the advantage of computational efficiency. Note also that the result is a natural extension of the classical result for the LCFS-PR M/G/1 queue. Further, utilizing the matrix product-form solution, we derive a new expression of the vector Laplace–Stieltjes transform of the stationary distribution of unfinished work in the work-conserving single-server queue with multiple arrival streams governed by a Markov chain, which is given by the sum of matrix-geometric series.     

批到达离散时间轮询系统中顾客等待时间及队长

本对批到达离散时间轮询系统进行研究,在门限服务原则下,推出了原客等待时间和轮询周期的概率母函数,利用Markov链理论,得出了队列队长均值。     

<Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1 type queueing-inventory systems with postponed work,reservation, cancellation and common life time

In this paper we analyze two single server queueing-inventory systems in which items in the inventory have a random common life time. On realization of common life time, all customers in the system are flushed out. Subsequently the inventory reaches its maximum level S through a (positive lead time) replenishment for the next cycle which follows an exponential distribution. Through cancellation of purchases, inventory gets added until their expiry time; where cancellation time follows exponential distribution. Customers arrive according to a Poisson process and service time is exponentially distributed. On arrival if a customer finds the server busy, then he joins a buffer of varying size. If there is no inventory, the arriving customer first try to queue up in a finite waiting room of capacity K. Finding that at full, he joins a pool of infinite capacity with probability γ (0 < γ < 1); else it is lost to the system forever. We discuss two models based on ‘transfer’ of customers from the pool to the waiting room / buffer. In Model 1 when, at a service completion epoch the waiting room size drops to preassigned number L ? 1 (1 < L < K) or below, a customer is transferred from pool to waiting room with probability p (0 < p < 1) and positioned as the last among the waiting customers. If at a departure epoch the waiting room turns out to be empty and there is at least one customer in the pool, then the one ahead of all waiting in the pool gets transferred to the waiting room with probability one. We introduce a totally different transfer mechanism in Model 2: when at a service completion epoch, the server turns idle with at least one item in the inventory, the pooled customer is immediately taken for service. At the time of a cancellation if the server is idle with none, one or more customers in the waiting room, then the head of the pooled customer go to the buffer directly for service. Also we assume that no customer joins the system when there is no item in the inventory. Several system performance measures are obtained. A cost function is discussed for each model and some numerical illustrations are presented. Finally a comparison of the two models are made.