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.     

Two queues with alternating service and server breakdown

We consider a queueing system with two stations served by a single server in a cyclic manner. We assume that at most one customer can be served at a station when the server arrives at the station. The system is subject to service interuption that arises from server breakdown. When a server breakdown occurs, the server must be repaired before service can resume. We obtain the approximate mean delay of customers in the 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.     

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.     

Large Closed Queueing Networks in Semi-Markov Environment and Their Application

The paper studies closed queueing networks containing a server station and k client stations. The server station is an infinite server queueing system, and client stations are single-server queueing systems with autonomous service, i.e. every client station serves customers (units) only at random instants generated by a strictly stationary and ergodic sequence of random variables. The total number of units in the network is N. The expected times between departures in client stations are (N μ _j )⁻¹. After a service completion in the server station, a unit is transmitted to the jth client station with probability p _j (j=1,2,…,k), and being processed in the jth client station, the unit returns to the server station. The network is assumed to be in a semi-Markov environment. A semi-Markov environment is defined by a finite or countable infinite Markov chain and by sequences of independent and identically distributed random variables. Then the routing probabilities p _j (j=1,2,…,k) and transmission rates (which are expressed via parameters of the network) depend on a Markov state of the environment. The paper studies the queue-length processes in client stations of this network and is aimed to the analysis of performance measures associated with this network. The questions risen in this paper have immediate relation to quality control of complex telecommunication networks, and the obtained results are expected to lead to the solutions to many practical problems of this area of research.      

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.     

Discrete time analysis of MAP/PH/1 vacation queue with gated time‐limited service

We analyse a single‐server queue in which the server goes through alternating periods of vacation and work. In each work period, the server attends to the queue for no more than a fixed length of time, T. The system is a gated one in which the server, during any visit, does not attend to customers which were not in the system before its visit. As soon as all the customers within the gate have been served or the time limit has been reached (whichever occurs first) the server goes on a vacation. The server does not wait in the queue if the system is empty at its arrival for a visit. For this system the resulting Markov chain, of the queue length and some auxiliary variables, is level‐dependent. We use special techniques to carry out the steady state analysis of the system and show that when the information regarding the number of customers in the gate is not critical we are able to reduce this problem to a level‐independent Markov chain problem with large number of boundary states. For this modified system we use a hybrid method which combines matrix‐geometric method for the level‐independent part of the system with special solution method for the large complex boundary which is level‐dependent. This revised version was published online in June 2006 with corrections to the Cover Date.     

Probabilistic proof of the interchangeability of ./M/1 queues in series

Given a finite number of empty ./M/1 queues, let customers arrive according to an arbitrary arrival process and be served at each queue exactly once, in some fixed order. The process of departing customers from the network has the same law, whatever the order in which the queues are visited. This remarkable result, due to R. Weber [4], is given a simple probabilistic proof.     

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.     

A finite capacity multi-queueing system with priorities and with repeated server vacations

In this paper, we study an M/G/1 multi-queueing system consisting ofM finite capacity queues, at which customers arrive according to independent Poisson processes. The customers require service times according to a queue-dependent general distribution. Each queue has a different priority. The queues are attended by a single server according to their priority and are served in a non-preemptive way. If there are no customers present, the server takes repeated vacations. The length of each vacation is a random variable with a general distribution function. We derive steady state formulas for the queue length distribution and the Laplace transform of the queueing time distribution for each queue.     

Scheduling networks of queues: Heavy traffic analysis of a simple open network

We consider a queueing network with two single-server stations and two types of customers. Customers of type A require service only at station 1 and customers of type B require service first at station 1 and then at station 2. Each server has a different general service time distribution, and each customer type has a different general interarrival time distribution. The problem is to find a dynamic sequencing policy at station 1 that minimizes the long-run average expected number of customers in the system.The scheduling problem is approximated by a dynamic control problem involving Brownian motion. A reformulation of this control problem is solved, and the solution is interpreted in terms of the queueing system in order to obtain an effective sequencing policy. Also, a pathwise lower bound (for any sequencing policy) is obtained for the total number of customers in the network. We show via simulation that the relative difference between the performance of the proposed policy and the pathwise lower bound becomes small as the load on the network is increased toward the heavy traffic limit.     

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.     

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 multi-class discrete-time queueing system under the FCFS service discipline

The problem with the FCFS server discipline in discrete-time queueing systems is that it doesn’t actually determine what happens if multiple customers enter the system at the same time, which in the discrete-time paradigm translates into ‘during the same time-slot’. In other words, it doesn’t specify in which order such customers are served. When we consider multiple types of customers, each requiring different service time distributions, the precise order of service even starts to affect quantities such as queue content and delays of arbitrary customers, so specifying this order will be prime. In this paper we study a multi-class discrete-time queueing system with a general independent arrival process and generally distributed service times. The service discipline is FCFS and customers entering during the same time-slot are served in random order. It will be our goal to search for the steady-state distribution of queue content and delays of certain types of customers. If one thinks of the time-slot as a continuous but bounded time period, the random order of service is equivalent to FCFS if different customers have different arrival epochs within this time-slot and if the arrival epochs are independent of customer class. For this reason we propose two distinct ways of analysing; one utilizing permutations, the other considering a slot as a bounded continuous time frame.     

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     

Stability of a spatial polling system with greedy myopic service

This paper studies a spatial queueing system on a circle, polled at random locations by a myopic server that can only observe customers in a bounded neighborhood. The server operates according to a greedy policy, always serving the nearest customer in its neighborhood, and leaving the system unchanged at polling instants where the neighborhood is empty. This system is modeled as a measure-valued random process, which is shown to be positive recurrent under a natural stability condition that does not depend on the server??s scan radius. When the interpolling times are light-tailed, the stable system is shown to be geometrically ergodic. The steady-state behavior of the system is briefly discussed using numerical simulations and a heuristic light-traffic approximation.     

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 MIP-based approach to solve the prize-collecting local access network design problem

This paper presents a new combinatorial optimization problem that can be used to model the deployment of broadband telecommunications systems in which optical fiber cables are installed between a central office and a number of end-customers. In this capacitated network design problem the installation of optical fiber cables with sufficient capacity is required to carry the traffic from the central office to the end-customers at minimum cost. In the situation motivating this research the network does not necessarily need to connect all customers (or at least not with the best available technology). Instead, some nodes are potential customers. The aim is to select the customers to be connected to the central server and to choose the cable capacities to establish these connections. The telecom company takes the strategic decision of fixing a percentage of customers that should be served, and aims for minimizing the total cost of the network providing this minimum service. For that reason the underlying problem is called the Prize-Collecting Local Access Network Design problem (PC-LAN).     

On the M/G/1 queue with feedback and optional server vacations based on a single vacation policy

We study a single server queue with batch arrivals and general (arbitrary) service time distribution. The server provides service to customers, one by one, on a first come, first served basis. Just after completion of his service, a customer may leave the system or may opt to repeat his service, in which case this customer rejoins the queue. Further, just after completion of a customer's service the server may take a vacation of random length or may opt to continue staying in the system to serve the next customer. We obtain steady state results in explicit and closed form in terms of the probability generating functions for the number of customers in the queue, the average number of customers and the average waiting time in the queue. Some special cases of interest are discussed and some known results have been derived. A numerical illustration is provided.     

Delay analysis of a two-class batch-service queue with class-dependent variable server capacity

In this paper, we analyse the delay of a random customer in a two-class batch-service queueing model with variable server capacity, where all customers are accommodated in a common single-server first-come-first-served queue. The server can only process customers that belong to the same class, so that the size of a batch is determined by the length of a sequence of same-class customers. This type of batch server can be found in telecommunications systems and production environments. We first determine the steady state partial probability generating function of the queue occupancy at customer arrival epochs. Using a spectral decomposition technique, we obtain the steady state probability generating function of the delay of a random customer. We also show that the distribution of the delay of a random customer corresponds to a phase-type distribution. Finally, some numerical examples are given that provide further insight in the impact of asymmetry and variance in the arrival process on the number of customers in the system and the delay of a random customer.