Analysis of the M [X]/G/1 queues with second multi-optional service and unreliable server

A bulk-arrival single server queueing system with second multi-optional service and unreliable server is studied in this paper. Customers arrive in batches according to a homogeneous Poisson process, all customers demand the first ＂essential＂ service, whereas only some of them demand the second ＂multi-optional＂ service. The first service time and the second service all have general distribution and they are independent. We assume that the server has a service-phase dependent, exponentially distributed life time as well as a servicephase dependent, generally distributed repair time. Using a supplementary variable method, we obtain the transient and the steady-state solutions for both queueing and reliability measures of interest.     

Strong approximations for Markovian service networks

Inspired by service systems such as telephone call centers, we develop limit theorems for a large class of stochastic service network models. They are a special family of nonstationary Markov processes where parameters like arrival and service rates, routing topologies for the network, and the number of servers at a given node are all functions of time as well as the current state of the system. Included in our modeling framework are networks of M _t /M _t /n _t queues with abandonment and retrials. The asymptotic limiting regime that we explore for these networks has a natural interpretation of scaling up the number of servers in response to a similar scaling up of the arrival rate for the customers. The individual service rates, however, are not scaled. We employ the theory of strong approximations to obtain functional strong laws of large numbers and functional central limit theorems for these networks. This gives us a tractable set of network fluid and diffusion approximations. A common theme for service network models with features like many servers, priorities, or abandonment is “non-smooth” state dependence that has not been covered systematically by previous work. We prove our central limit theorems in the presence of this non-smoothness by using a new notion of derivative. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

AN M/G/1 RETRIAL QUEUE WITH SECOND MULTI-OPTIONAL SERVICE, FEEDBACK AND UNRELIABLE SERVER

An M/G/1 retrial queue with two-phase service and feedback is studied in this paper, where the server is subject to starting failures and breakdowns during service. Primary customers get in the system according to a Poisson process, and they will receive service immediately if the server is available upon arrival. Otherwise, they will enter a retrial orbit and are queued in the orbit in accordance with a first-come-first-served （FCFS） discipline. Customers are allowed to balk and renege at particular times. All customers demand the first “essential” service, whereas only some of them demand the second “multi-optional” service. It is assumed that the retrial time, service time and repair time of the server are all arbitrarily distributed. The necessary and sufficient condition for the system stability is derived. Using a supplementary variable method, the steady-state solutions for some queueing and reliability measures of the system are obtained.     

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.     

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     

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 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.     

MAP/(PH/PH)/c Queue with Self-Generation of Priorities and Non-Preemptive Service

Abstract

Customers arriving according to a Markovian arrival process are served at a c server facility. Waiting customers generate into priority while waiting in the system (self-generation of priorities), at a constant rate γ; such a customer is immediately taken for service, if at least one of the servers is free. Else it waits at a waiting space of capacity c exclusively for priority generated customers, provided there is vacancy. A customer in service is not preempted to accommodate a priority generated customer. The service times of ordinary and priority generated customers follow distinct PH-distributions. It is proved that the system is always stable. We provide a numerical procedure to compute the optimal number of servers to be employed to minimize the loss to the system. Several performance measures are evaluated.     

On single-server closed queues with priorities and state dependent parameters

A wide class of closed single-channel queues is considered. The more general model involvesm +w + 1 “permanent” customers that occasionally require service. Them customers are of the first priority and the rest are of the second priority. The input rate and service of customers depend upon the total number of customers waiting for service. Such a system can also be described in terms of servicing machines processes with reserve replacement and multi-channel queues with finite waiting room. Two dual models, with and without idle periods, are treated. An explicit relation between the servicing processes of both models is derived. The semi-regenerative techniques originally developed in the author's earlier work [4] are extended and used to derive the probability distribution of the processes in equilibrium. Applications and examples are discussed. This paper is a part of work supported by the National Science Foundation under Grant No. DMS-8706186.     

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.     

Fluid limits of many-server queues with abandonments,general service and continuous patience time distributions

This paper extends the works of Kang and Ramanan (2010) and Kaspi and Ramanan (2011), removing the hypothesis of absolute continuity of the service requirement and patience time distributions. We consider a many-server queueing system in which customers enter service in the order of arrival in a non-idling manner and where reneging is considerate. Similarly to Kang and Ramanan (2010), the dynamics of the system are represented in terms of a process that describes the total number of customers in the system as well as two measure-valued processes that record the age in service of each of the customers being served and the “potential” waiting times. When the number of servers goes to infinity, fluid limit is established for this triple of processes. The convergence is in the sense of probability and the limit is characterized by an integral equation.     

On the guaranteed throughput and efficiency of closed re-entrant lines

A closed network is said to be “guaranteed efficient” if the throughput converges under all non-idling policies to the capacity of the bottlenecks in the network, as the number of trapped customers increases to infinity. We obtain a necessary condition for guaranteed efficiency of closed re-entrant lines. For balanced two-station systems, this necessary condition is almost sufficient, differing from it only by the strictness of an inequality. This near characterization is obtained by studying a special type of virtual station called “alternating visit virtual station”. These special virtual stations allow us to relate the necessary condition to certain indices arising in heavy traffic studies using a Brownian network approximation, as well as to certain policies proposed as being extremal with respect to the asymptotic loss in the throughput. Using the near characterization of guaranteed efficiency we also answer the often pondered question of whether an open network or its closed counterpart has greater throughput - the answer is that neither can assure a greater guaranteed throughput. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Multiserver queue with addressed retrials

This paper presents a multiserver retrial queueing system with servers kept apart, thereby rendering it impossible for one to know the status (idle/busy) of the others. Customers proceeding to one channel will have to go to orbit if the server in it is busy and retry after some time to some channel, not necessarily the one already tried. Each orbital customer, independently of others, chooses the server randomly according to some specified probability distribution. Further this distribution is identical for all customers. We assume that the same ‘orbit’ is used by all retrial customers, between repeated attempts, to access the servers. We derive the system state probability distribution under Poisson arrival process of external customers, exponentially distributed service times and linear retrial rates to access the servers. Several system state characteristics are obtained and numerical illustrations provided. AMS subject classification: Primary 60K25 60K20     

Pricing and setup/closedown policies in unobservable queues with strategic customers

In this paper we study unobservable Markovian queueing systems with three types of setup/closedown policies: interruptible, skippable and insusceptible setup/closedown policies, respectively. For a system with the interruptible setup/closedown policy, service starts as soon as a customer arrives during a closedown time; However, for a system with the skippable setup/closedown policy, customers arriving in a closedown time (if any) can be served only after the closedown time finishes and the following setup time can be skipped; Then for a system with the insusceptible setup/closedown policy, customers arriving in a closedown time can??t be served until the following setup time finishes. We assume that customers need a price for service, and derive the equilibrium and socially optimal balking strategies for customers as well as the maximal social welfare. Then we make pricing control to motivate customers to adopt the optimal strategies and obtain an appropriate price that also maximizes server??s profit. Moreover, we numerically make some comparisons between the various performance measures.     

A critically loaded multirate link with trunk reservation

We consider a loss system model of interest in telecommunications. There is a single service facility with N servers and no waiting room. There are K types of customers, with type ί customers requiring A _ί servers simultaneously. Arrival processes are Poisson and service times are exponential. An arriving type ί customer is accepted only if there are Rί(⩾A_ί ) idle servers. We examine the asymptotic behavior of the above system in the regime known as critical loading where both N and the offered load are large and almost equal. We also assume that R ₁,..., R _K-1 remain bounded, while R _K ^N ←∞ and R _K ^N /√N ← 0 as N ← ∞. Our main result is that the K dimensional “queue length” process converges, under the appropriate normalization, to a particular K dimensional diffusion. We show that a related system with preemption has the same limit process. For the associated optimization problem where accepted customers pay, we show that our trunk reservation policy is asymptotically optimal when the parameters satisfy a certain relation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Flexible servers in tandem lines with setup costs

We study the dynamic assignment of flexible servers to stations in the presence of setup costs that are incurred when servers move between stations. The goal is to maximize the long-run average profit. We provide a general problem formulation and some structural results, and then concentrate on tandem lines with two stations, two servers, and a finite buffer between the stations. We investigate how the optimal server assignment policy for such systems depends on the magnitude of the setup costs, as well as on the homogeneity of servers and tasks. More specifically, for systems with either homogeneous servers or homogeneous tasks, small buffer sizes, and constant setup cost, we prove the optimality of “multiple threshold” policies (where servers’ movement between stations depends on both the number of jobs in the system and the locations of the servers) and determine the values of the thresholds. For systems with heterogeneous servers and tasks, small buffers, and constant setup cost, we provide results that partially characterize the optimal server assignment policy. Finally, for systems with larger buffer sizes and various service rate and setup cost configurations, we present structural results for the optimal policy and provide numerical results that strongly support the optimality of multiple threshold policies.     

Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates

We provide an approximate analysis of the transient sojourn time for a processor sharing queue with time varying arrival and service rates, where the load can vary over time, including periods of overload. Using the same asymptotic technique as uniform acceleration as demonstrated in [12] and [13], we obtain fluid and diffusion limits for the sojourn time of the M_t/M_t/1 processor-sharing queue. Our analysis is enabled by the introduction of a “virtual customer” which differs from the notion of a “tagged customer” in that the former has no effect on the processing time of the other customers in the system. Our analysis generalizes to non-exponential service and interarrival times, when the fluid and diffusion limits for the queueing process are known.