M/(G1, G2)/1 retrial queue under Bernoulli vacation schedules with general repeated attempts and starting failures

This paper investigates a batch arrival retrial queue with general retrial times, where the server is subject to starting failures and provides two phases of heterogeneous service to all customers under Bernoulli vacation schedules. Any arriving batch finding the server busy, breakdown or on vacation enters an orbit. Otherwise one customer from the arriving batch enters a service immediately while the rest join the orbit. After the completion of two phases of service, the server either goes for a vacation with probability p or may wait for serving the next customer with probability (1 − p). We construct the mathematical model and derive the steady-state distribution of the server state and the number of customers in the system/orbit. Such a model has potential application in transfer model of e-mail system.     

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.     

Economies of scale,competitiveness, and trade patterns within the European community: Clarendon Press,Oxford, 1983, 193 pages, £20.00

We consider two queues in series with input to each queue, which can be controlled by accepting or rejecting arriving customers. The objective is to maximize the discounted or average expected net benefit over a finite or infinite horizon, where net benefit is composed of (random) rewards for entering customers minus holding costs assessed against the customers at each queue. Provided that it costs more to hold a customer at the first queue than at the second, we show that an optimal policy is monotonic in the following senses: Adding a customer to either queue makes it less likely that we will accept a new customer into either queue; moreover moving a customer from the first queue to the second makes it more (less) likely that we will accept a new customer into the first (second) queue. Our model has policy implications for flow control in communication systems, industrial job shops, and traffic-flow systems. We comment on the relation between the control policies implied by our model and those proposed in the communicationa literature.     

Strategic behavior in queues with the effect of the number of customers behind

In this paper, we investigate the strategic behavior in queues by considering the effect of the number of customers behind. The equilibrium joining strategy of customers is obtained and its implications for the service system are examined. We find that the complete queue transparency (i.e., disclosing the real-time system information) can have positive effect on customers, which might encourage more customers to join. Further, the follow-the-crowd (FTC) behavior can be observed, which results in multiple equilibria. By comparing the customer welfare under two different information levels, we demonstrate that, somewhat surprisingly, the queue transparency does not necessarily hurt the customer welfare, and a higher customer welfare can be obtained in the transparent case than that in opaque case when the demand volume is large.     

Equilibrium customer strategies in a single server Markovian queue with setup times

We consider a single server Markovian queue with setup times. Whenever this system becomes empty, the server is turned off. Whenever a customer arrives to an empty system, the server begins an exponential setup time to start service again. We assume that arriving customers decide whether to enter the system or balk based on a natural reward-cost structure, which incorporates their desire for service as well as their unwillingness to wait. We examine customer behavior under various levels of information regarding the system state. Specifically, before making the decision, a customer may or may not know the state of the server and/or the number of present customers. We derive equilibrium strategies for the customers under the various levels of information and analyze the stationary behavior of the system under these strategies. We also illustrate further effects of the information level on the equilibrium behavior via numerical experiments.      

Scheduling service in tandem queues attended by a single server

Consider a tandem queue model with a single server who can switch instantaneously from one queue to another. Customers arrive according to a Poisson process with rate λ . The amount of service required by each customer at the i^th queue is an exponentially distributed random variable with rate μ_i. Whenever two or more customers are in the system, the decision as to which customer should be served first depends on the optimzation criterion. In this system all server allocation policies in the finite set of work conserving deterministic policies have the same expected first passage times (makespan) to empty the system of customers from any initial state. However, a unique policy maximizes the first passage probability of empty-ing the system before the number of customers exceeds K, for any value of K, and it stochastically minimizes (he number of customers in the system at any time t > 0 . This policy always assigns the server to the non empty queue closest to the exit     

Stochastic bounds for a polling system

In this note we consider two queueing systems: a symmetric polling system with gated service at allN queues and with switchover times, and a single-server single-queue model with one arrival stream of ordinary customers andN additional permanently present customers. It is assumed that the combined arrival process at the queues of the polling system coincides with the arrival process of the ordinary customers in the single-queue model, and that the service time and switchover time distributions of the polling model coincide with the service time distributions of the ordinary and permanent customers, respectively, in the single-queue model. A complete equivalence between both models is accomplished by the following queue insertion of arriving customers. In the single-queue model, an arriving ordinary customer occupies with probabilityp _i a position at the end of the queue section behind theith permanent customer,i = l, ...,N. In the cyclic polling model, an arriving customer with probabilityp _i joins the end of theith queue to be visited by the server, measured from its present position.For the single-queue model we prove that, if two queue insertion distributions {p _{i, i} = l, ...,N} and {q _{i, i} = l, ...,N} are stochastically ordered, then also the workload and queue length distributions in the corresponding two single-queue versions are stochastically ordered. This immediately leads to equivalent stochastic orderings in polling models.Finally, the single-queue model with Poisson arrivals andp ₁ = 1 is studied in detail.Part of the research of the first author has been supported by the Esprit BRA project QMIPS.     

Equilibrium customers’ choice between FCFS and random servers

Consider two servers of equal service capacity, one serving in a first-come first-served order (FCFS), and the other serving its queue in random order. Customers arrive as a Poisson process and each arriving customer observes the length of the two queues and then chooses to join the queue that minimizes its expected queueing time. Assuming exponentially distributed service times, we numerically compute a Nash equilibrium in this system, and investigate the question of which server attracts the greater share of customers. If customers who arrive to find both queues empty independently choose to join each queue with probability 0.5, then we show that the server with FCFS discipline obtains a slightly greater share of the market. However, if such customers always join the same queue (say of the server with FCFS discipline) then that server attracts the greater share of customers. This research was supported by the Israel Science Foundation grant No. 526/08.     

Queues with impolite customers

An interesting behavior of customers arriving to a queue for service concerns the manner in which they join the queue. The arrival discipline of the customers may be impolite, in the sense that an arriving customer who finds all servers busy may pick a position which is not necessarily at the end of the line. We introduce and discuss in detail such an arrival discipline of sufficient generality which has interesting applications. In particular, we show that the more impolite an arrival discipline is, the bigger is the variance of the waiting time. We also study a special model in more depth to provide simple computational formulas for several performance measures.     

Analysis of preemptive loss priority queues with preemption distance

In a queueing system with preemptive loss priority discipline, customers disappear from the system immediately when their service is preempted by the arrival of another customer with higher priority. Such a system can model a case in which old requests of low priority are not worthy of deferred service. This paper is concerned with preemptive loss priority queues in which customers of each priority class arrive in a Poisson process and have general service time distribution. The strict preemption in the existing model is extended by allowing the preemption distance parameterd such that arriving customers of only class 1 throughp — d can preempt the service of a customer of classp. We obtain closed-form expressions for the mean waiting time, sojourn time, and queue size from their distributions for each class, together with numerical examples. We also consider similar systems with server vacations.     

输入率可变且有差错服务的M/M/1排队系统的研究与应用

在到达系统的顾客数不变的情况下,顾客到达系统但是否进入系统接受服务对销售行业影响是巨大的.从排队长度对顾客输入率的影响着手,研究了顾客以泊松流到达系统,而到达系统的顾客进入系统接受服务的概率与队长有关的M/M/1排队模型,且系统服务会出差错.得出了进入系统的顾客流是泊松过程,且系统中的顾客数是生灭过程,并获得了该模型的平稳分布、顾客的平均输入率、系统的平均服务强度等多项指标,为销售行业调整自己的服务速度以影响排队长度及顾客输入率,进而提高自己的销售业绩提供了很有价值的参考.     

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.     

Queue Length Distribution in a FIFO Single-Server Queue with Multiple Arrival Streams Having Different Service Time Distributions

This paper considers the queue length distribution in a class of FIFO single-server queues with (possibly correlated) multiple arrival streams, where the service time distribution of customers may be different for different streams. It is widely recognized that the queue length distribution in a FIFO queue with multiple non-Poissonian arrival streams having different service time distributions is very hard to analyze, since we have to keep track of the complete order of customers in the queue to describe the queue length dynamics. In this paper, we provide an alternative way to solve the problem for a class of such queues, where arrival streams are governed by a finite-state Markov chain. We characterize the joint probability generating function of the stationary queue length distribution, by considering the joint distribution of the number of customers arriving from each stream during the stationary attained waiting time. Further we provide recursion formulas to compute the stationary joint queue length distribution and the stationary distribution representing from which stream each customer in the queue arrived.     

The discrete-time preemptive repeat identical priority queue

Priority queueing systems come natural when customers with diversified delay requirements have to wait to get service. The customers that cannot tolerate but small delays get service priority over customers which are less delay-sensitive. In this contribution, we analyze a discrete-time two-class preemptive repeat identical priority queue with infinite buffer space and generally distributed service times. Newly arriving high-priority customers interrupt the on-going service of a low-priority customer. After all high-priority customers have left the system, the interrupted service of the low-priority customer has to be repeated completely. By means of a probability generating functions approach, we analyze the system content and the delay of both types of customers. Performance measures (such as means and variances) are calculated and the impact of the priority scheduling is discussed by means of some numerical examples.     

TheM/G/1 queue with processor sharing and its relation to a feedback queue

The central model of this paper is anM/M/1 queue with a general probabilistic feedback mechanism. When a customer completes his ith service, he departs from the system with probability 1–p(i) and he cycles back with probabilityp(i). The mean service time of each customer is the same for each cycle. We determine the joint distribution of the successive sojourn times of a tagged customer at his loops through the system. Subsequently we let the mean service time at each loop shrink to zero and the feedback probabilities approach one in such a way that the mean total required service time remains constant. The behaviour of the feedback queue then approaches that of anM/G/1 processor sharing queue, different choices of the feedback probabilities leading to different service time distributions in the processor sharing model. This is exploited to analyse the sojourn time distribution in theM/G/1 queue with processor sharing.Some variants are also considered, viz., anM/M/1 feedback queue with additional customers who are always present, and anM/G/1 processor sharing queue with feedback.     

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 a discrete-time preemptive resume priority buffer

In this paper, we analyze a discrete-time preemptive resume priority queue. We consider two classes of customers which have to be served, where customers of one class have preemptive resume priority over customers of the other. Both classes contain customers with generally distributed service times. We show that the use of probability generating functions is beneficial for analyzing the system contents and customer delays of both classes. It is shown (theoretically as well as by some practical procedures) how moments and approximate tail probabilities of system contents and customer delays are calculated. The influence of the priority scheduling discipline and the service time distributions on the performance measures is shown by some numerical examples.     

Geometric equilibrium distributions for queues with interactive batch departures

Gelenbe et al. [1, 2] consider single server Jackson networks of queues which contain both positive and negative customers. A negative customer arriving to a nonempty queue causes the number of customers in that queue to decrease by one, and has no effect on an empty queue, whereas a positive customer arriving at a queue will always increase the queue length by one. Gelenbe et al. show that a geometric product form equilibrium distribution prevails for this network. Applications for these types of networks can be found in systems incorporating resource allocations and in the modelling of decision making algorithms, neural networks and communications protocols.In this paper we extend the results of [1, 2] by allowing customer arrivals to the network, or the transfer between queues of a single positive customer in the network to trigger the creation of a batch of negative customers at the destination queue. This causes the length of the queue to decrease by the size of the created batch or the size of the queue, whichever is the smallest. The probability of creating a batch of negative customers of a particular size due to the transfer of a positive customer can depend on both the source and destination queue.We give a criterion for the validity of a geometric product form equilibrium distribution for these extended networks. When such a distribution holds it satisfies partial balance equations which are enforced by the boundaries of the state space. Furthermore it will be shown that these partial balance equations relate to traffic equations for the throughputs of the individual queues.     

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.     

Stationary tail asymptotics of a tandem queue with feedback

Motivated by applications in manufacturing systems and computer networks, in this paper, we consider a tandem queue with feedback. In this model, the i.i.d. interarrival times and the i.i.d. service times are both exponential and independent. Upon completion of a service at the second station, the customer either leaves the system with probability p or goes back, together with all customers currently waiting in the second queue, to the first queue with probability 1−p. For any fixed number of customers in one queue (either queue 1 or queue 2), using newly developed methods we study properties of the exactly geometric tail asymptotics as the number of customers in the other queue increases to infinity. We hope that this work can serve as a demonstration of how to deal with a block generating function of GI/M/1 type, and an illustration of how the boundary behaviour can affect the tail decay rate.