Sojourn times in polling systems with various service disciplines

We consider a polling system of N queues Q₁,…,Q_N, cyclically visited by a single server. Customers arrive at these queues according to independent Poisson processes, requiring generally distributed service times. When the server visits Q_i, i=1,…,N, it serves a number of customers according to a certain polling discipline. This discipline is assumed to belong to the class of branching-type disciplines, which includes the gated and exhaustive disciplines. The special feature of our study is that, within each queue, we do not restrict ourselves to service in order of arrival (FCFS); we are interested in the effect of different service disciplines, like Last-Come–First-Served, Processor Sharing, Random Order of Service, and Shortest Job First, on the sojourn time distribution of a typical customer that arrives to the system during steady-state. After a discussion of the joint distribution of the numbers of customers at each queue at visit epochs of the server to a particular queue, we determine the Laplace–Stieltjes transform of the cycle-time distribution, viz., the time between two successive visits of the server to, say, Q₁. This yields the transform of the joint distribution of past and residual cycle time, w.r.t. the arrival of a tagged customer at Q₁. Subsequently concentrating on the case of gated service at Q₁, we use that cycle-time result to determine the (Laplace–Stieltjes transform of the) sojourn-time distribution at Q₁, for each of the scheduling disciplines mentioned above.Next to locally gated polling disciplines, we also consider the globally gated discipline. Again, we consider various non-FCFS service disciplines at the queues, and we determine the (Laplace–Stieltjes transform of the) sojourn-time distribution at an arbitrary queue.     

基于混合服务策略轮询系统的性能分析

周期轮询系统已被广泛运用于各个领域,如计算机网络、工业制造系统等。在周期轮询系统中,最基本的队列调度策略有门限服务、限定服务以及完全服务。这些调度策略各有其优缺点,文章提出了一种基于混合服务的调度策略,对一些队列采用门限服务,对另一些队列采用限定服务,这样既可以避免在单一的完全服务中低优先级队列有可能出现的队列饥饿现象,又可以对不同的队列提供不同的服务质量。该文通过嵌入马尔可夫链和概率母函数的方法对基于混合服务的轮询系统进行分析,推导出队列的平均队长,并与采用门限服务的轮询系统进行比较,从而说明混合服务系统的优点。     

A model of the polling system for studying the broadband wireless networks

A study of the model of a cyclic (polling) system adequately describing the broadband wireless WiFi and WiMax centralized-control networks was presented. The server was assumed to have full information about the current system state. The queues are serviced by the exhaustive threshold discipline, that is, a queue is serviced if its length exceeds the given threshold. If the lengths of all queues are insufficient to start servicing, then the server stops polling the queue until any of them accumulates the required number of customers. Relying on the stationary probability distribution of the polling system states, the main performance characteristics such as the mean queue length, failure probability, and mean waiting time were established.     

新颖的离散时间队列系统模型(英文)

带有正负顾客的连续时间单台服务器的队列系统得到了深入研究且已应用于多agent服务系统和计算机网络系统,而带有正负顾客的离散时间Geo/Geo/1队列研究在最近才出现。在拓展离散时间单台服务器Geo/Geo/1队列的基础上,提出了一个具有正负几何到达顾客的离散时间单台服务器GI/M/1队列模型,分析了队列静态长度分布和在RCH与RCE情况下的等待时间长度分布。     

两类服务对象轮询模型的平均运行周期

系统地研究了两类服务对象轮询服务模型的平均运行周期．首先扩展了现有的每队列只具有单类服务对象的单类服务对象轮询服务模型，提出了每队列内具有两类服务对象的两类服务对象轮询服务模型(这两类对象分别采用门限服务和限定服务)．然后，在该模型稳定条件下，通过构造出队列队长的嵌入式马尔可夫链、概率母函数和Laplace-Stieltje变换，求解出平衡状态下该模型的平均运行周期．并且，通过指出队列稳定性与模型稳定性之间的差异，给出了在部分或者全部的限定式服务队列不稳定时．模型的平均运行周期．最后仿真验证了理论结果的正确性．     

Optimal control of parallel queues with impatient customers

We consider a queueing system with a number of identical exponential servers. Each server has its own queue with unlimited capacity. The service discipline in each queue is first-come-first-served (FCFS). Customers arrive according to a state-dependent Poisson process with an arrival rate which is a non-increasing function of the number of customers in the system. Upon arrival, a customer must join a server’s queue according to a stationary state-dependent policy, where the state is taken to be the number of customers in servers’ queues. No jockeying among queues is allowed. Each arriving customer is limited to a generally distributed patience time after which it must depart the system and is considered lost. Two models of customer behavior are considered: deadlines until the beginning of service and deadlines until the end of service. We seek an optimal policy to assign an arriving customer to a server’s queue. We show that, when the distribution of customer impatience satisfies certain property, the policy of joining shortest queue (SQ) stochastically minimizes the number of lost customers during any finite interval in the long run. This property is shown to always hold for the case of deterministic customer impatience.     

Decomposing the queue length distribution of processor-sharing models into queue lengths of permanent customer queues

We obtain a decomposition result for the steady state queue length distribution in egalitarian processor-sharing (PS) models. In particular, for multi-class egalitarian PS queues, we show that the marginal queue length distribution for each class equals the queue length distribution of an equivalent single class PS model with a random number of permanent customers. Similarly, the mean sojourn time (conditioned on the initial service requirement) for each class can be obtained by conditioning on the number of permanent customers. The decomposition result implies linear relations between the marginal queue length probabilities, which also hold for other PS models such as the egalitarian PS models with state-dependent system capacity that only depends on the total number of customers in the system. Based on the exact decomposition result for egalitarian PS queues, we propose a similar decomposition for discriminatory processor-sharing (DPS) models, and numerically show that the approximation is accurate for moderate differences in service weights.     

Optimal routing and buffer allocation for a class of finitecapacity queueing systems

The problem of routing jobs to K parallel queues with identical exponential servers and unequal finite buffer capacities is considered. Routing decisions are taken by a controller which has buffering space available to it and may delay routing of a customer to a queue. Using ideas from weak majorization, it is shown that the shorter nonfull queue delayed (SNQD) policy minimizes both the total number of customers in the system at any time and the number of customers that are rejected by that time. The SNQD policy always delays routing decisions as long as all servers are busy. Only when all the buffers at the controller are occupied is a customer routed to the queue with the shortest queue length that is not at capacity. Moreover, it is shown that, if a fixed number of buffers is to be distributed among the K queues, then the optimal allocation scheme is the one in which the difference between the maximum and minimum queue capacities is minimized, i.e. becomes either 0 or 1     

中心队列二次门限服务的轮询系统分析

采用嵌入Markov链和概率母函数的方法对门限服务优先级排队系统进行分析,提出普通队列和高优先级队列分别采用基本门限和二级门限的服务机制,得出了平均排队队长和平均查询周期的解析式。     

Polling models with renewal arrivals: A new method to derive heavy-traffic asymptotics

We consider asymmetric cyclic polling systems with an arbitrary number of queues, general service-time distributions, zero switch-over times, gated service at each queue, and with general renewal arrival processes at each of the queues. For this classical model, we propose a new method to derive closed-form expressions for the expected delay at each of the queues when the load tends to 1, under proper heavy-traffic (HT) scalings. In the literature on polling models, rigorous proofs of HT limits have only been obtained for polling models with Poisson-type arrival processes, whereas for renewal arrivals HT limits are based on conjectures [E.G. Coffman, A.A. Puhalskii, M.I. Reiman, Polling systems with zero switch-over times: A heavy-traffic principle, Ann. Appl. Probab. 5 (1995) 681–719; E.G. Coffman, A.A. Puhalskii, M.I. Reiman, Polling systems in heavy-traffic: A Bessel process limit, Math. Oper. Res. 23 (1998) 257–304; T.L. Olsen, R.D. van der Mei, Periodic polling systems in heavy-traffic: Renewal arrivals, OR Lett. 33 (2005) 17–25]. Therefore, the main contribution of this paper lies in the fact that we propose a new method to rigorously prove HT limits for a class of non-Poisson-type arrivals. The results are remarkably simple and provide new fundamental insight and reveal explicitly how the expected delay at each of the queues depends on the system parameters, and in particular on the interarrival-time distributions at each of the queues. The results also suggest simple approximations for the expected delay in stable polling systems. Numerical results show that the approximations are highly accurate when the system load is roughly 90% or more.     

非对称门限服务与完全服务的性能解析

为了能在无线传感器网络选择一种合适的非对称轮询服务,对非对称门限服务与完全服务的性能进行了分析和比较判定了两种服务在不同情况下其各自特性的优越性.通常在分析非对称轮询服务的时候,一般采用由浅入深的分析方法.所以两队列的服务模型将会作为基础,借此进行拓展,对多队列的非对称服务进行解析.分析过程中使用了马尔科夫链和概率母函数的方法构建了服务系统的数学模型.通过对数学模型的解析给出了非对称服务系统平均排队队长和平均查询周期的表达式.根据理论值的精确计算与实验仿真值的对比结果,可以验证出二者是保持一致的.并且,对未来在无线传感器网络中实现非对称的门限服务和完全服务进行了初步设计,可以实现将多跳的路由协议,转变成单跳的轮询协议,减少数据传输的冲突性.     

一种轮询系统的平均周期时间

文中首先介绍了非抢先优先权队列门限服务轮询系统的操作原则,在此基础上,通过对系统嵌入马尔可大链,构造队列母函数及Ｌａｐｌａｃｅ－Ｓｔｉｅｌｔｊｅｓ变换,求解出了系统的平均周期时间,并且通过计算机的仿真验证了公式的正确性。     

A pseudoconservation law for a time-limited service polling system with structured batch poisson arrivals

We consider a cyclic-service queueing system (polling system) with time-limited service, in which the length of a service period for each queue is controlled by a timer, i.e., the server serves customers until the timer expires or the queue becomes empty, whichever occurs first, and then proceeds to the next queue. The customer whose service is interrupted due to the timer expiration is attended according to the nonpreemptive service discipline. For the cyclic-service system with structured batch Poisson arrivals (M^x/G/1) and an exponential timer, we derive a pseudoconservation law and an exact mean waiting time formula for the symmetric system.     

The combined gated-exhaustive vacation system in discrete time

We consider a discrete-time gated vacation system. The available buffer space is divided into two subsequent queues separated by a gate and new customers arrive either before or after this gate. Whenever all customers after the gate are served, the server takes a vacation. After each vacation, the gate opens which causes all waiting customers to move to the buffer space after the gate. The model under investigation allows to capture performance of a.o. the exhaustive and the gated queueing systems with multiple or single vacations. Using a probability generating functions approach, we obtain expressions for performance measures such as moments of system contents at various epochs in equilibrium and of customer delay. We conclude with a numerical example.     

On a batch arrival Poisson queue with a random setup time and vacation period

The single server queue with vacation has been extended to include several types of extensions and generalisations, to which attention has been paid by several researchers (e.g. see Doshi, B. T., Single server queues with vacations — a servey. Queueing Systems, 1986, 1, 29–66; Takagi, H., Queueing Analysis: A Foundation of Performance evaluation, Vol. 1, Vacation and Priority systems, Part. 1. North Holland, Amsterdam, 1991; Medhi, J., Extensions and generalizations of the classical single server queueing system with Poisson input. J. Ass. Sci. Soc., 1994, 36, 35–41, etc.). The interest in such types of queues have been further enhanced in resent years because of their theoretical structures as well as their application in many real life situations such as computer, telecommunication, airline scheduling as well as production/inventory systems. This paper concerns the model building of such a production/inventory system, where machine undergoes extra operation (such as machine repair, preventive maintenance, gearing up machinery, etc.) before the processing of raw material is to be started. To be realistic, we also assume that raw materials arrive in batch. This production system can be formulated as an M^x/M/1 queues with a setup time. Further, from the utility point of view of idle time this model can also be formulated as a case of multiple vacation model, where vacation begins at the end of each busy period. Besides, the production/inventory systems, such a model is generally fitted to airline scheduling problems also. In this paper an attempt has been made to study the steady state behavior of such an M^x/M/1 queueing system with a view to provide some system performance measures, which lead to remarkable simplification when solving other similar types of queueing models.This paper deals with the steady state behaviour of a single server batch arrival Poisson queue with a random setup time and a vacation period. The service of the first customer in each busy period is preceded by a random setup period, on completion of which service starts. As soon as the system becomes empty the server goes on vacation for a random length of time. On return from vacation, if he finds customer(s) waiting, the server starts servicing the first customer in the queue. Otherwise it takes another vacation and so on. We study the steady state behaviour of the queue size distribution at random (stationary) point of time as well as at departure point of time and try to show that departure point queue size distribution can be decomposed into three independent random variables, one of which is the queue size of the standard M^x/M/1 queue. The interpretation of the other two random variables will also be provided. Further, we derive analytically explicit expressions for the system state (number of customers in the system) probabilities and provide their appropriate interpretations. Also, we derive some system performance measures. Finally, we develop a procedure to find mean waiting time of an arbitrary customer.     

Analysis of the M/G/1 queue with discriminatory random order service policy

We consider an M/G/1 queue with different classes of customers and discriminatory random order service (DROS) discipline. The DROS discipline generalizes the random order service (ROS) discipline: when the server selects a customer to serve, all customers waiting in the system have the same selection probability under ROS discipline, whereas customers belonging to different classes may have different selection probabilities under DROS discipline. For the M/G/1 queue with DROS discipline, we derive equations for the joint queue length distributions and for the waiting time distributions of each class. We also obtain the moments of the queue lengths and the waiting time of each class. Numerical results are given to illustrate our results.     

Optimal scheduling of two competing queues with blocking

Consideration is given to the problem of optimal scheduling for two queues for service at a single station, where the queues have finite capacities and the service rate is class-dependent. The cost structure is linear in the number of holding customers in the queues, combined with blocking costs incurred whenever arrivals encounter a full queue. The authors derive the optimal policy minimizing this criterion when the blocking cost is larger than the holding cost for each queue. Then they show that the optimal policy is of the switching type. Numerical results are included to support the analytical findings     

Markovian bulk service queue with delayed vacations

An M/M(a, b)/1 queueing system with multiple vacations is studied, in which if the number of customers in the queue is a - 1 either at a service completion epoch or at a vacation completion point, the server will wait for an exponential time in the system which is called the changeover time. During this changeover time if there is an arrival the server will start service immediately, otherwise at the end of the changeover time the server will go for a vacation. The duration of vacation is also exponential. This paper is concerned with the determination of the stationary distribution of the number of customers in the queue and the waiting time distribution of an arriving customer. The expected queue length is also obtained. Sample numerical illustrations are given.     

Analysis of a multi-server queue with two priority classes and (M, N)-threshold service schedule I: non-preemptive priority

In this paper, we propose an ( M , N )-threshold non-preemptive priority service schedule for a queueing system consisting of two-parallel queues and a multi-server. The arrival process for each queue is Poisson, and the service times are exponentially distributed with different means. We derive the generating functions of the stationary joint queue-length distribution, and then obtain the mean queue length and the mean waiting time for each queue.     

Parallel exponential queues with dependent service rates

A system of two parallel single-server exponential queues is considered. These queues operate independently except that the service rate in each queue changes whenever the other queue is empty. By treating one of the queues as bounded, this model can be shown to have a matrix-geometric steady state vector which can be computed efficiently. Algorithms are also developed to compute the characteristics of the departure stream of customers from each queue. Some numerical results are presented, and based on these results an efficient approximation scheme for the system is developed which may possibly be extended to systems with more than two parallel queues.