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.     

Stationary Distributions of GI/M/c Queue with PH Type Vacations

We study a GI/M/c type queueing system with vacations in which all servers take vacations together when the system becomes empty. These servers keep taking synchronous vacations until they find waiting customers in the system at a vacation completion instant.The vacation time is a phase-type (PH) distributed random variable. Using embedded Markov chain modeling and the matrix geometric solution methods, we obtain explicit expressions for the stationary probability distributions of the queue length at arrivals and the waiting time. To compare the vacation model with the classical GI/M/c queue without vacations, we prove conditional stochastic decomposition properties for the queue length and the waiting time when all servers are busy. Our model is a generalization of several previous studies.     

A queueing model for crowdsourcing

Crowdsourcing is getting popular after a number of industries such as food, consumer products, hotels, electronics, and other large retailers bought into this idea of serving customers. In this paper, we introduce a multi-server queueing model in the context of crowdsourcing. We assume that two types, say, Type 1 and Type 2, of customers arrive to a c-server queueing system. A Type 1 customer has to receive service by one of c servers while a Type 2 customer may be served by a Type 1 customer who is available to act as a server soon after getting a service or by one of c servers. We assume that a Type 1 customer will be available for serving a Type 2 customer (provided there is at least one Type 2 customer waiting in the queue at the time of the service completion of that Type 1 customer) with probability \(p, 0 \le p \le 1\). With probability \(q = 1 - p\), a Type 1 customer will opt out of serving a Type 2 customer provided there is at least one Type 2 customer waiting in the system. Upon completion of a service a free server will offer service to a Type 1 customer on an FCFS basis; however, if there are no Type 1 customers waiting in the system, the server will serve a Type 2 customer if there is one present in the queue. If a Type 1 customer decides to serve a Type 2 customer, for our analysis purposes that Type 2 customer will be removed from the system as Type 1 customer will leave the system with that Type 2 customer. Under the assumption of exponential services for both types of customers we study the model in steady state using matrix analytic methods and establish some results including explicit ones for the waiting time distributions. Some illustrative numerical examples are presented.     

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.     

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.     

Models and Approximations for Call Center Design

A call center is a facility for delivering telephone service, both incoming and outgoing. This paper addresses optimal staffing of call centers, modeled as M/G/n queues whose offered traffic consists of multiple customer streams, each with an individual priority, arrival rate, service distribution and grade of service (GoS) stated in terms of equilibrium tail waiting time probabilities or mean waiting times. The paper proposes a methodology for deriving the approximate minimal number of servers that suffices to guarantee the prescribed GoS of all customer streams. The methodology is based on an analytic approximation, called the Scaling-Erlang (SE) approximation, which maps the M/G/n queue to an approximating, suitably scaled M/G/1 queue, for which waiting time statistics are available via the Pollaczek-Khintchine formula in terms of Laplace transforms. The SE approximation is then generalized to M/G/n queues with multiple types of customers and non-preemptive priorities, yielding the Priority Scaling-Erlang (PSE) approximation. A simple goal-seeking search, utilizing SE/PSE approximations, is presented for the optimal staffing level, subject to GoS constraints. The efficacy of the methodology is demonstrated by comparing the number of servers estimated via the PSE approximation to their counterparts obtained by simulation. A number of case studies confirm that the SE/PSE approximations yield optimal staffing results in excellent agreement with simulation, but at a fraction of simulation time and space.     

Delay Distribution of (Im)Patient Customers in a Discrete Time D-MAP/PH/1 Queue with Age-Dependent Service Times

This paper presents an algorithmic procedure to calculate the delay distribution of (im)patient customers in a discrete time D-MAP/PH/1 queue, where the service time distribution of a customer depends on his waiting time. We consider three different situations: impatient customers in the waiting room, impatient customers in the system, that is, if a customer has been in the waiting room, respectively, in the system for a time units it leaves the waiting room, respectively, the system. In the third situation, all customers are patient – that is, they only leave the system after completing service. In all three situations the service time of a customer depends upon the time he has spent in the waiting room. As opposed to the general approach in many queueing systems, we calculate the delay distribution, using matrix analytic methods, without obtaining the steady state probabilities of the queue length. The trick used in this paper, which was also applied by Van Houdt and Blondia [J. Appl. Probab., Vol. 39, No. 1 (2002) pp. 213–222], is to keep track of the age of the customer in service, while remembering the D-MAP state immediately after the customer in service arrived. Possible extentions of this method to more general queues and numerical examples that demonstrate the strength of the algorithm are also included.     

Waiting Time Distributions in the Preemptive Accumulating Priority Queue

We consider a queueing system in which a single server attends to N priority classes of customers. Upon arrival to the system, a customer begins to accumulate priority linearly at a rate which is distinct to the class to which it belongs. Customers with greater accumulated priority levels are given preferential treatment in the sense that at every service selection instant, the customer with the greatest accumulated priority level is selected next for servicing. Furthermore, the system is preemptive so that the servicing of a customer is interrupted for customers with greater accumulated priority levels. The main objective of the paper is to characterize the waiting time distributions of each class. Numerical examples are also provided which exemplify the true benefit of incorporating an accumulating prioritization structure, namely the ability to control waiting times.     

Queues with system disasters and impatient customers when system is down

Consider a system operating as an M/M/c queue, where c=1, 1<c<∞, or c=∞. The system as a whole suffers occasionally a disastrous breakdown, upon which all present customers (waiting and served) are cleared from the system and lost. A repair process then starts immediately. When the system is down, inoperative, and undergoing a repair process, new arrivals become impatient: each individual customer, upon arrival, activates a random-duration timer. If the timer expires before the system is repaired, the customer abandons the queue never to return. We analyze this model and derive various quality of service measures: mean sojourn time of a served customer; proportion of customers served; rate of lost customers due to disasters; and rate of abandonments due to impatience.      

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     

Perishable Inventory System at Service Facilities with N Policy

Abstract

This article presents a perishable stochastic inventory system under continuous review at a service facility in which the waiting hall for customers is of finite size M. The service starts only when the customer level reaches N (< M), once the server has become idle for want of customers. The maximum storage capacity is fixed as S. It is assumed that demand for the commodity is of unit size. The arrivals of customers to the service station form a Poisson process with parameter λ. The individual customer is issued a demanded item after a random service time, which is distributed as negative exponential. The items of inventory have exponential life times. It is also assumed that lead time for the reorders is distributed as exponential and is independent of the service time distribution. The demands that occur during stock out periods are lost.The joint probability distribution of the number of customers in the system and the inventory levels is obtained in steady state case. Some measures of system performance in the steady state are derived. The results are illustrated with numerical examples.     

Waiting time in a multi-server cutoff-priority gueue, and its application to an urban ambulance service

We consider a priority queue in steady state with N servers, two classes of customers, and a cutoff service discipline. Low priority arrivals are "cut off" (refused immediate service) and placed in a queue whenever N1 or more servers are busy, in order to keep N-N1 servers free for high priority arrivals. A Poisson arrival process for each class, and a common exponential service rate, are assumed. Two models are considered: one where high priority customers queue for service and one where they are lost if all servers are busy at an arrival epoch. Results are obtained for the probability of n servers busy, the expected low priority waiting time, and (in the case where high priority customers do not queue) the complete low priority waiting time distribution. The results are applied to determine the number of ambulances required in an urban fleet which serves both emergency calls and low priority patients transfers.     

Two Queues with Weighted One-Way Overflow

We consider an open queueing network consisting of two queues with Poisson arrivals and exponential service times and having some overflow capability from the first to the second queue. Each queue is equipped with a finite number of servers and a waiting room with finite or infinite capacity. Arriving customers may be blocked at one of the queues depending on whether all servers and/or waiting positions are occupied. Blocked customers from the first queue can overflow to the second queue according to specific overflow routines. Using a separation method for the balance equations of the two-dimensional server and waiting room demand process, we reduce the dimension of the problem of solving these balance equations substantially. We extend the existing results in the literature in three directions. Firstly, we allow different service rates at the two queues. Secondly, the overflow stream is weighted with a parameter p ∈ [0,1], i.e., an arriving customer who is blocked and overflows, joins the overflow queue with probability p and leaves the system with probability 1 − p. Thirdly, we consider several new blocking and overflow routines. An erratum to this article can be found at     

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.     

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.     

Performance of service policies in a specialized service system with parallel servers

This paper considers a scheduling problem occurring in a specialized service system with parallel servers. In the system, customers are divided into the “ordinary” and “special” categories according to their service needs. Ordinary customers can be served by any server, while special customers can be served only by the flexible servers. We assume that the service time for any ordinary customer is the same and all special customers have another common service time. We analyze three classes of service policies used in practice, namely, policies with priority, policies without priority and mixed policies. The worst-case performance ratios are obtained for all of these service policies.     

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.     

Waiting time distributions in the accumulating priority queue

We are interested in queues in which customers of different classes arrive to a service facility, and where performance targets are specified for each class. The manager of such a queue has the task of implementing a queueing discipline that results in the performance targets for all classes being met simultaneously. For the case where the performance targets are specified in terms of ratios of mean waiting times, as long ago as the 1960s, Kleinrock suggested a queueing discipline to ensure that the targets are achieved. He proposed that customers accumulate priority as a linear function of their time in the queue: the higher the urgency of the customer’s class, the greater the rate at which that customer accumulates priority. When the server becomes free, the customer (if any) with the highest accumulated priority at that time point is the one that is selected for service. Kleinrock called such a queue a time-dependent priority queue, but we shall refer to it as the accumulating priority queue. Recognising that the performance of many queues, particularly in the healthcare and human services sectors, is specified in terms of tails of waiting time distributions for customers of different classes, we revisit the accumulating priority queue to derive its waiting time distributions, rather than just the mean waiting times. We believe that some elements of our analysis, particularly the process that we call the maximum priority process, are of mathematical interest in their own right.     

A Discrete-Time Single-Server Queueing System Under Multiple Vacations and Setup-Closedown Times

Abstract

This article concerns a Geo/G/1/∞ queueing system under multiple vacations and setup-closedown times. Specifically, the operation of the system is as follows. After each departure leaving an empty system, the server is deactivated during a closedown time. At the end of each closedown time, if at least a customer is present in the system, the server begins the service of the customers (is reactivated) without setup; however, if the system is completely empty, the server takes a vacation. At the end of each vacation, if there is at least a customer in the system, the server requires a startup time (is reactivated) before beginning the service of the customers; nevertheless, if there are not customers waiting in the system, the server takes another vacation. By applying the supplementary variable technique, the joint generating function of the server state and the system length together with the main performance measures are derived. We also study the length of the different busy periods of the server. The stationary distributions of the time spent waiting in the queue and in the system under the FCFS discipline are analysed too. Finally, a cost model with some numerical results is presented.     

Analysis of MAP/PH1,PH2/1 queue with vacations and optional secondary services

In this paper we study a queueing model in which the customers arrive according to a Markovian arrival process (MAP). There is a single server who offers services on a first-come-first-served basis. With a certain probability a customer may require an optional secondary service. The secondary service is provided by the same server either immediately (if no one is waiting to receive service in the first stage) or waits until the number waiting for such services hits a pre-determined threshold. The model is studied as a QBD-process using matrix-analytic methods and some illustrative examples are discussed.