Expected waiting times in polling systems under priority disciplines

In this paper, we analyse a service system which consists of several queues (stations) polled by a single server in a cyclic order with arbitrary switchover times. Customers from several priority classes arrive into each of the queues according to independent Poisson processes and require arbitrarily distributed service times. We consider the system under various priority service disciplines: head-of-the-line priority limited to one and semi-exhaustive, head-of-the-line priority limited to one with background customers, and global priority limited to one. For the first two disciplines we derive a pseudo conservation law. For the third discipline, we show how to obtain the expected waiting time of a customer from any given priority class. For the last discipline we find the expected waiting time of a customer from the highest priority class. The principal tool for our analysis is the stochastic decomposition law for a single server system with vacations.     

Strong approximations for priority queues; head-of-the-line-first discipline

In this paper, we obtain strong approximation theorems for a single server queue withr priority classes of customers and a head-of-the-line-first discipline. By using priority queues of preemptive-resume discipline as modified systems, we prove strong approximation theorems for the number of customers of each priority in the system at timet, the number of customers of each priority that have departed in the interval [0,t], the work load in service time of each priority class facing the server at timet, and the accumulated time in [0,t] during which there are neither customers of a given priority class nor customers of priority higher than that in the system.Research supported by the National Natural Science Foundation of China.     

On multiple priority multi-server queues with impatience

We consider Markovian multi-server queues with two types of impatient customers: high- and low-priority ones. The first type of customer has a non-preemptive priority over the other type. After entering the queue, a customer will wait a random length of time for service to begin. If service has not begun by this time he or she will abandon and be lost. We consider two cases where the discipline of service within each customer type is first-come first-served (FCFS) or last-come first-served (LCFS). For each type of customer, we focus on various performance measures related to queueing delays: unconditional waiting times, and conditional waiting times given service and given abandonment. The analysis we develop holds also for a priority queue with mixed policies, that is, FCFS for the first type and LCFS for the second one, and vice versa. We explicitly derive the Laplace–Stieltjes transforms of the defined random variables. In addition we show how to extend the analysis to more than two customer types. Finally we compare FCFS and LCFS and gain insights through numerical experiments.     

排队论在销售管理中的应用

销售性企业如何才能降低销售时的综合成本是一个值得研究的问题.以排队论为基础对这一问题展开讨论,分析了顾客到达企业时的排队方式,得出了单队多服务通道要比多队多服务通道排队方式要优;分析了系统的服务规则及评价指标,并建立了一个输入率可变、服务率可变且先到先服务的、有不耐烦顾客的销售模型,以及一个输入率可变、服务率可变且有非强占优先权的销售模型,分别得出了系统的平均服务率及顾客在系统中的平均等待时间,从而建立了企业销售时的综合成本函数,并结合实例给出了求综合成本函数最小值的方法.     

Multi-Server Queueing Systems with Multiple Priority Classes

We present the first near-exact analysis of an M/PH/k queue with m > 2 preemptive-resume priority classes. Our analysis introduces a new technique, which we refer to as Recursive Dimensionality Reduction (RDR). The key idea in RDR is that the m-dimensionally infinite Markov chain, representing the m class state space, is recursively reduced to a 1-dimensionally infinite Markov chain, that is easily and quickly solved. RDR involves no truncation and results in only small inaccuracy when compared with simulation, for a wide range of loads and variability in the job size distribution. Our analytic methods are then used to derive insights on how multi-server systems with prioritization compare with their single server counterparts with respect to response time. Multi-server systems are also compared with single server systems with respect to the effect of different prioritization schemes—“smart” prioritization (giving priority to the smaller jobs) versus “stupid” prioritization (giving priority to the larger jobs). We also study the effect of approximating m class performance by collapsing the m classes into just two classes. Supported by NSF Career Grant CCR-0133077, NSF Theory CCR-0311383, NSF ITR CCR-0313148, and IBM Corporation via Pittsburgh Digital Greenhouse Grant 2003. AMS subject classification: 60K25, 68M20, 90B22, 90B36     

Stationary distribution of queue length in G / M / 1 queue with two-stage service policy

We consider a G / M / 1 queue with two-stage service policy. The server starts to serve with rate of μ₁ customers per unit time until the number of customers in the system reaches λ. At this moment, the service rate is changed to that of μ₂ customers per unit time and this rate continues until the system is empty. We obtain the stationary distribution of the number of customers in the system.     

Analysis of customers’ impatience in queues with server vacations

Many models for customers impatience in queueing systems have been studied in the past; the source of impatience has always been taken to be either a long wait already experienced at a queue, or a long wait anticipated by a customer upon arrival. In this paper we consider systems with servers vacations where customers’ impatience is due to an absentee of servers upon arrival. Such a model, representing frequent behavior by waiting customers in service systems, has never been treated before in the literature. We present a comprehensive analysis of the single-server, M/M/1 and M/G/1 queues, as well as of the multi-server M/M/c queue, for both the multiple and the single-vacation cases, and obtain various closed-form results. In particular, we show that the proportion of customer abandonments under the single-vacation regime is smaller than that under the multiple-vacation discipline. This work was supported by the Euro-Ngi network of excellence.     

Recursive calculation of moments in priority queues

We reconsider the discrete-time priority queue with two classes. The server serves high-priority customers as long as there are such customers, and only turns to the low-priority customers when there are no high-priority customers. Relying on a multivariate recursive extension of Faà di Bruno's formula, we find recursive equations to calculate the moments of the queue lengths. This allows for calculation of many more moments in much shorter time than conventionally possible.     

Waiting time analysis of the multiple priority dual queue with a preemptive priority service discipline

The dual queue consists of two queues, called the primary queue and the secondary queue. There is a single server in the primary queue but the secondary queue has no service facility and only serves as a holding queue for the overloaded primary queue. The dual queue has the additional feature of a priority scheme to help reduce congestion. Two classes of customers, class 1 and 2, arrive to the dual queue as two independent Poisson processes and the single server in the primary queue dispenses an exponentially distributed service time at the rate which is dependent on the customer’s class. The service discipline is preemptive priority with priority given to class 1 over class 2 customers. In this paper, we use matrix-analytic method to construct the infinitesimal generator of the system and also to provide a detailed analysis of the expected waiting time of each class of customers in both queues.     

Optimal server scheduling in nonpreemptive finite-population queueing systems

We consider a finite-population queueing system with heterogeneous classes of customers and a single server. For the case of nonpreemptive service, we fully characterize the structure of the server's optimal service policy that minimizes the total average customer waiting costs. We show that the optimal service policy may never serve some classes of customers. For those classes that are served, we show that the optimal service policy is a simple static priority policy. We also derive sufficient conditions that determine the optimal priority sequence.     

带有优先权、不耐烦顾客及负顾客的$M_1,M_2/G_1,G_2/1$可修重试排队系统

研究了带有优先权,不耐烦顾客及负顾客的M1,M2/G1,G2/1可修重试排队系统.假设两类顾客的优先级不同且各自的到达过程分别服从独立的泊松过程.有优先权的顾客到达系统时如服务器忙,则以概率H1排队等候服务,以概率1-H1离开系统;而没有优先权的顾客只能一定的概率进入Orbit中进行重试,直到重试成功.此外,假设有服从Poisson过程的负顾客到达:当负顾客到达系统时,若发现服务台忙,将带走正在接受服务的顾客并使机器处于修理状态;若服务台空闲或已经处于失效状态,则负顾客立即消失,对系统没有任何影响.应用补充变量及母函数法给出了该模型的系统指标稳态解的拉氏变换表达式,并得到了此模型主要的排队指标及可靠性指标.     

On a Two-Queue Priority System with Impatience and its Application to a Call Center*

We consider an s-server priority system with a protected and an unprotected queue. The arrival rates at the queues and the service rate may depend on the number n of customers being in service or in the protected queue, but the service rate is assumed to be constant for n > s. As soon as any server is idle, a customer from the protected queue will be served according to the FCFS discipline. However, the customers in the protected queue are impatient. If the offered waiting time exceeds a random maximal waiting time I, then the customer leaves the protected queue after time I. If I is less than a given deterministic time, then he leaves the system, else he will be transferred by the system to the unprotected queue. The service of a customer from the unprotected queue will be started if the protected queue is empty and more than a given number of servers become idle. The model is a generalization of the many-server queue with impatient customers. The global balance conditions seem to have no explicit solution. However, the balance conditions for the density of the stationary state process for the subsystem of customers being in service or in the protected queue can be solved. This yields the stability conditions and the probabilities that precisely n customers are in service or in the protected queue. For obtaining performance measures for the unprotected queue, a system approximation based on fitting impatience intensities is constructed. The results are applied to the performance analysis of a call center with an integrated voice-mail-server.     

Analysis of Queueing Systems with Synchronous Single Vacation for Some Servers

We study a multi-server M/M/c type queue with a single vacation policy for some idle servers. In this queueing system, if at a service completion instant, any d (d c) servers become idle, these d servers will take one and only one vacation together. During the vacation of d servers, the other c–d servers do not take vacation even if they are idle. Using a quasi-birth-and-death process and the matrix analytic method, we obtain the stationary distribution of the system. Conditional stochastic decomposition properties have been established for the waiting time and the queue length given that all servers are busy.     

The single-server scheduling problem with convex costs

Being probably one of the oldest decision problems in queuing theory, the single-server scheduling problem continues to be a challenging one. The original formulations considered linear costs, and the resulting policy is puzzling in many ways. The main one is that, either for preemptive or nonpreemptive problems, it results in a priority ordering of the different classes of customers being served that is insensitive to the individual load each class imposes on the server and insensitive to the overall load the server experiences. This policy is known as the cμ-rule. We claim and show that for convex costs, the optimal policy depends on the individual loads. Therefore, there is a need for an alternative generalization of the cμ-rule. The main feature of our generalization consists on first-order differences of the single stage cost function, rather than on its derivatives. The resulting policy is able to reach near optimal performances and is a function of the individual loads.     

A first passage time problem for spectrally positive Lévy processes and its application to a dynamic priority queue

We study a first passage time problem for a class of spectrally positive Lévy processes. By considering the special case where the Lévy process is a compound Poisson process with negative drift, we obtain the Laplace–Stieltjes transform of the steady-state waiting time distribution of low-priority customers in a two-class M/GI/1$M/GI/1$ queue operating under a dynamic non-preemptive priority discipline. This allows us to observe how the waiting time of customers is affected as the policy parameter varies.     

Approximations for the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">N</Emphasis>+<Emphasis Type="Italic">GI</Emphasis> type call center

In this paper, we propose approximations to compute the steady-state performance measures of the M/GI/N+GI queue receiving Poisson arrivals with N identical servers, and general service and abandonment-time distributions. The approximations are based on scaling a single server M/GI/1+GI queue. For problems involving deterministic and exponential abandon times distributions, we suggest a practical way to compute the waiting time distributions and their moments using the Laplace transform of the workload density function. Our first contribution is numerically computing the workload density function in the M/GI/1+GI queue when the abandon times follow general distributions different from the deterministic and exponential distributions. Then we compute the waiting time distributions and their moments. Next, we scale-up the M/GI/1+GI queue giving rise to our approximations to capture the behavior of the multi-server system. We conduct extensive numerical experiments to test the speed and performance of the approximations, which prove the accuracy of their predictions.      

Optimal scheduling policies in time sharing service systems

We consider optimal scheduling problems in a TSSS (Time Sharing Service System), i.e., a tandem queueing network consisting of multiple service stations, all of which are served by a single server. In each station, a customer can receive service time up to the prescribed station dependent upper bound, but he must proceed to the next station in order to receive further service. After the total amount of the received services reaches his service requirement, he departs from the network. The optimal policy for this system minimizes the long-run average expected waiting cost per unit of time over the infinite planning horizon. It is first shown that, if the distribution of customer's service requirement is DMRL (Decreasing Mean Residual Life), the policy of giving the highest priority to the customer with the most attained service time is optimal under a set of some appropriate conditions. This implies that any policy without interruptions and preemptions of services is optimal. If the service requirement is DFR (Decreasing Failure Rate), on the other hand, it is shown that the policy of giving the highest priority to the customer with the least attained service time, i.e., the so-called LAST (Least Attained Service Time first) is optimal under another set of some appropriate conditions. These results can be generalized to the case in which there exist multiple classes of customers, but each class satisfies one of the above sets of conditions.     

The N threshold policy for the GI/M/1 queue

We study a GI/M/1 queue with an N threshold policy. In this system, the server stops attending the queue when the system becomes empty and resumes serving the queue when the number of customers reaches a threshold value N. Using the embeded Markov chain method, we obtain the stationary distributions of queue length and waiting time and prove the stochastic decomposition properties.     

An Iterative Algorithm for a Multiple Finite-source Queueing Model with Dynamic Priority Scheduling

A multiple finite source queueing model with a single server and dynamic, non-preemptive priority service discipline is studied in this paper. The times the customers spend at the corresponding sources are exponentially distributed. The service times of the customers can follow exponential, Erlang or hyperexponential probability density function. By using results published earlier and an extension of mean value analysis, an iterative algorithm was developed to obtain approximate values of the mean waiting times in queues for the priority classes. The mean number of waiting customers and the server utilization of each class are obtained using the result of this algorithm and Little's formula. The algorithm is preferable to the earlier method, because it does not increase in complexity as the number of customer classes increases.