Retrial queues with server subject to breakdowns and repairs

In this paper we consider a single server retrial queue where the server is subject to breakdowns and repairs. New customers arrive at the service station according to a Poisson process and demand i.i.d. service times. If the server is idle, the incoming customer starts getting served immediately. If the server is busy, the incoming customer conducts a retrial after an exponential amount of time. The retrial customers behave independently of each other. The server stays up for an exponential time and then fails. Repair times have a general distribution. The failure/repair behavior when the server is idle is different from when it is busy. Two different models are considered. In model I, the failed server cannot be occupied and the customer whose service is interrupted has to either leave the system or rejoin the retrial group. In model II, the customer whose service is interrupted by a failure stays at the server and restarts the service when repair is completed. Model II can be handled as a special case of model I. For model I, we derive the stability condition and study the limiting behavior of the system by using the tools of Markov regenerative processes.Visiting from Department of Applied Mathematics, Korea Advanced Institute of Science and Technology, Cheongryang, Seoul, Korea.     

Work-Conserving Tandem Queues

Consider a tandem queue of two single-server stations with only one server for both stations, who may allocate a fraction α of the service capacity to station 1 and 1−α to station 2 when both are busy. A recent paper treats this model under classical Poisson, exponential assumptions.Using work conservation and FIFO, we show that on every sample path (no stochastic assumptions), the waiting time in system of every customer increases with α. For Poisson arrivals and an arbitrary joint distribution of service times of the same customer at each station, we find the average waiting time at each station for α = 0 and α = 1. We extend these results to k ≥ 3 stations, sample paths that allow for server breakdown and repair, and to a tandem arrangement of single-server tandem queues.This revised version was published online in June 2005 with corrected coverdate     

A mixed priority retrial queue with negative arrivals,unreliable server and multiple vacations

A retrial queue accepting two types of positive customers and negative arrivals, mixed priorities, unreliable server and multiple vacations is considered. In case of blocking the first type customers can be queued whereas the second type customers leave the system and try their luck again after a random time period. When a first type customer arrives during the service of a second type customer, he either pushes the customer in service in orbit (preemptive) or he joins the queue waiting to be served (non-preemptive). Moreover negative arrivals eliminate the customer in service and cause server’s abnormal breakdown, while in addition normal breakdowns may also occur. In both cases the server is sent immediately for repair. When, upon a service or repair completion, the server finds no first type customers waiting in queue remains idle and activates a timer. If timer expires before an arrival of a positive customer the server departs for multiple vacations. For such a system the stability conditions and the system state probabilities are investigated both in a transient and in a steady state. A stochastic decomposition result is also presented. Interesting applications are also discussed. Numerical results are finally obtained and used to investigate system performance.     

Mean delay analysis for a message priority-based polling scheme

We consider a multi-access communication channel such as a centrally-controlled polling system, a distributed token-based ring, or a bus network. A message priority-based polling procedure is used to control the access to the channel. This procedure requires the server to have no advance information concerning the number of messages resident at a station prior to its visit to the station. Messages arriving at each station belong to one of two priority classes: class-1 (high priority) and class-2 (low priority). Class-1 messages are served under an exhaustive service discipline, while class-2 messages are served under a limited service discipline. Class-1 messages have non-preemptive priority over class-2 messages resident at the same station. Using a fully symmetric system model, an exact expression for the sum of the mean waiting times of class-1 and class-2 messages is first derived. Upper and lower bounds for the mean message waiting times for each individual message class are then obtained.This work was supported by NFS Grant No. NCR-8914690, Pacific-Bell and MICRO Grant No. 90-135 and US West Contract No. D890701.     

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.     

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.     

具有两类故障特性的M/M/1排队系统均衡分析

考虑顾客在具有两种故障特性的马尔科夫排队系统中的均衡策略.在该系统中,正常工作的服务台随时都可能发生故障.假设服务台只要发生故障就不再接收新顾客,并且可能出现的故障类型有两种：（1）不完全故障：此类故障发生时,服务台仍有部分服务能力,以较低服务率服务完在场顾客后进行维修;（2）完全故障：此类故障发生时,服务台停滞服务并且立即进行维修,维修结束后重新接收新顾客.顾客到达时为了实现自身利益最大化都有选择是否进队的决策,基于线性“收益-损失”结构函数,分析了顾客在系统信息完全可见和几乎不可见情形下的均衡进队策略,及系统的平均社会收益,并在此基础上,通过一些数值例子展示系统参数对顾客策略行为的影响.     

A tandem GI/PH/1→•/PH/1/0 queue with blocking

Tandem queues are widely used in mathematical modeling of random processes describing the operation of manufacturing systems, supply chains, computer and telecommunication networks. Although there exists a lot of publications on tandem queueing systems, analytical research on tandem queues with non-Markovian input is very limited. In this paper, the results of analytical investigation of two-node tandem queue with arbitrary distribution of inter-arrival times are presented. The first station of the tandem is represented by a single-server queue with infinite waiting room. After service at the first station, a customer proceeds to the second station that is described by a single-server queue without a buffer. Service times of a customer at the first and the second server have PH (Phase-type) distributions. A customer, who completes service at the first server and meets a busy second server, is forced to wait at the first server until the second server becomes available. During the waiting period, the first server becomes blocked, i.e., not available for service of customers. We calculate the joint stationary distribution of the system states at the embedded epochs and at arbitrary time. The Laplace–Stieltjes transform of the sojourn time distribution is derived. Key performance measures are calculated and numerical results presented.     

A simple heuristic for load balancing in parallel processing networks with highly variable service time distributions

Suppose that customers arrive at a service center (call center, web server, etc.) with two stations in accordance with independent Poisson processes. Service times at either station follow the same general distribution, are independent of each other and are independent of the arrival process. The system is charged station-dependent holding costs at each station per customer per unit time. At any point in time, a decision-maker may decide to move, at a cost, some number of jobs in one queue to the other. The goals of this paper are twofold. First, we are interested in providing insights into this decision-making scenario. We do so, in the important case that the service time distribution is highly variable or simply has a heavy tail. Secondly, we propose that the savvy use of Markov decision processes can lead to easily implementable heuristics when features of the service time distribution can be captured by introducing multiple customer classes. To this end, we consider a two-station proxy for the original system, where the service times are assumed to be exponential, but of one of two classes with different rates. We prove structural results for this proxy and show that these results lead to heuristics that perform well.     

A batch arrival retrial queue with general retrial times under Bernoulli vacation schedule for unreliable server and delaying repair

This paper deals with the steady state behaviour of an M^x/G/1 queue with general retrial time and Bernoulli vacation schedule for an unreliable server, which consists of a breakdown period and delay period. Here we assume that customers arrive according to compound Poisson processes. While the server is working with primary customers, it may breakdown at any instant and server will be down for short interval of time. Further concept of the delay time is also introduced. The primary customer finding the server busy, down or vacation are queued in the orbit in accordance with FCFS (first come first served) retrial policy. After the completion of a service, the server either goes for a vacation of random length with probability p or may continue to serve for the next customer, if any with probability (1 − p). We carry out an extensive analysis of this model. Finally, we obtain some important performance measures and reliability indices of this model.     

A simple policy for multiple queues with size-independent service times

We consider a service system with two Poisson arrival queues. A server chooses which queue to serve at each moment. Once a queue is served, all the customers will be served within a fixed amount of time. This model is useful in studying airport shuttling or certain online computing systems. We propose a simple yet optimal state-independent policy for this problem which is not only easy to implement, but also performs very well.     

A heavy traffic limit theorem for a class of open queueing networks with finite buffers

We consider a queueing network of d single server stations. Each station has a finite capacity waiting buffer, and all customers served at a station are homogeneous in terms of service requirements and routing. The routing is assumed to be deterministic and hence feedforward. A server stops working when the downstream buffer is full. We show that a properly normalized d-dimensional queue length process converges in distribution to a fd-dimensional semimartingale reflecting Brownian motion (RBM) in a d-dimensional box under a heavy traffic condition. The conventional continuous mapping approach does not apply here because the solution to our Skorohod problem may not be unique. Our proof relies heavily on a uniform oscillation result for solutions to a family of Skorohod problems. The oscillation result is proved in a general form that may be of independent interest. It has the potential to be used as an important ingredient in establishing heavy traffic limit theorems for general finite buffer networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

A product form solution to a system with multi-type jobs and multi-type servers

We consider a memoryless single station service system with servers \(\mathcal{S}=\{m_{1},\ldots,m_{K}\}\), and with job types \(\mathcal{C}=\{a,b,\ldots\}\). Service is skill-based, so that server m _i can serve a subset of job types \(\mathcal{C}(m_{i})\). Waiting jobs are served on a first-come-first-served basis, while arriving jobs that find several idle servers are assigned to a feasible server randomly. We show that there exist assignment probabilities under which the system has a product-form stationary distribution, and obtain explicit expressions for it. We also derive waiting time distributions in steady state.     

Discrete NT-policy single server queue with Markovian arrival process and phase type service

We consider a discrete time single server queueing system in which arrivals are governed by the Markovian arrival process. During a service period, all customers are served exhaustively. The server goes on vacation as soon as he/she completes service and the system is empty. Termination of the vacation period is controlled by two threshold parameters N and T, i.e. the server terminates his/her vacation as soon as the number waiting reaches N or the waiting time of the leading customer reaches T units. The steady state probability vector is shown to be of matrix-geometric type. The average queue length and the probability that the server is on vacation (or idle) are obtained. We also derive the steady state distribution of the waiting time at arrivals and show that the vacation period distribution is of phase type.     

Geo/Geo/1 retrial queue with working vacations and vacation interruption

Consider a Geo/Geo/1 retrial queue with working vacations and vacation interruption, and assume requests in the orbit try to get service from the server with a constant retrial rate. During the working vacation period, customers can be served at a lower rate. If there are customers in the system after a service completion instant, the vacation will be interrupted and the server comes back to the normal working level. We use a quasi birth and death process to describe the considered system and derive a condition for the stability of the model. Using the matrix-analytic method, we obtain the stationary probability distribution and some performance measures. Furthermore, we prove the conditional stochastic decomposition for the queue length in the orbit. Finally, some numerical examples are presented.     

A heavy-traffic analysis of a closed queueing system with a GI/∞ service center

This paper studies the heavy-traffic behavior of a closed system consisting of two service stations. The first station is an infinite server and the second is a single server whose service rate depends on the size of the queue at the station. We consider the regime when both the number of customers, n, and the service rate at the single-server station go to infinity while the service rate at the infinite-server station is held fixed. We show that, as n→∞, the process of the number of customers at the infinite-server station normalized by n converges in probability to a deterministic function satisfying a Volterra integral equation. The deviations of the normalized queue from its deterministic limit multiplied by √n converge in distribution to the solution of a stochastic Volterra equation. The proof uses a new approach to studying infinite-server queues in heavy traffic whose main novelty is to express the number of customers at the infinite server as a time-space integral with respect to a time-changed sequential empirical process. This gives a new insight into the structure of the limit processes and makes the end results easy to interpret. Also the approach allows us to give a version of the classical heavy-traffic limit theorem for the G/GI/∞ queue which, in particular, reconciles the limits obtained earlier by Iglehart and Borovkov. This revised version was published online in June 2006 with corrections to the Cover Date.     

Symmetric queues served in cyclic order

Consider a symmetrical system of n queues served in cyclic order by a single server. It is shown that the stationary number of customers in the system is distributed as the sum of three independent random variables, one being the stationary number of customers in a standard M/G/1 queue. This fact is used to establish an upper bound for the mean waiting time for the case where at most k customers are served at each queue per visit by the server. This approach is also used to rederive the mean waiting times for the cases of exhaustive service, gated service, and serve at most one customer at each queue per visit by the server.     

A game theoretic model for two types of customers competing for service

Two types of customers arrive at a single server station and demand service. If a customer finds the server busy upon arrival (or retrial) he immediately departs and conducts a retrial after an exponential period of time and persists this way until he gets served. Both types of customers face linear costs for waiting and conducting retrials and wish to find optimal retrial rates which will minimize these costs. This problem is analysed as a two-person nonzero sum game. Both noncooperative strategies are studied.     

Dynamic scheduling of a single-server two-class queue with constant retrial policy

We analyze the non-preemptive assignment of a single server to two infinite-capacity retrial queues. Customers arrive at both queues according to Poisson processes. They are served on first-come-first-served basis following a cost-optimal routing policy. The customer at the head of a queue generates a Poisson stream of repeated requests for service, that is, we have a constant retrial policy. All service times are exponential, with rates depending on the queues. The costs to be minimized consist of costs per unit time that a customer spends in the system. In case of a scheduling problem that arise when no new customers arrive an explicit condition for server allocation to the first or the second queue is given. The condition presented covers all possible parameter choices. For scheduling that also considers new arrivals, we present the conditions under which server assignment to either queue 1 or queue 2 is cost-optimal.     

Ergodicity of a polling network

The polling network considered here consists of a finite collection of stations visited successively by a single server who is following a Markovian routing scheme. At every visit of a station a positive random number of the customers present at the start of the visit are served, whereupon the server takes a positive random time to walk to the station to be visited next. The network receives arrivals of customer groups at Poisson instants, and all customers wait until served, whereupon they depart from the network. Necessary and sufficient conditions are derived for the server to be able to cope with the traffic. For the proof a multidimensional imbedded Markov chain is studied.