Two competing discrete-time queues with priority

This paper considers a class of two discrete-time queues with infinite buffers that compete for a single server. Tasks requiring a deterministic amount of service time, arrive randomly to the queues and have to be served by the server. One of the queues has priority over the other in the sense that it always attempts to get the server, while the other queue attempts only randomly according to a rule that depends on how long the task at the head of the queue has been waiting in that position. The class considered is characterized by the fact that if both queues compete and attempt to get the server simultaneously, then they both fail and the server remains idle for a deterministic amount of time. For this class we derive the steady-state joint generating function of the state probabilities. The queueing system considered exhibits interesting behavior, as we demonstrate by an example.     

A single server queue with service interruptions

In this paper we characterize the queue-length distribution as well as the waiting time distribution of a single-server queue which is subject to service interruptions. Such queues arise naturally in computer and communication problems in which customers belong to different classes and share a common server under some complicated service discipline. In such queues, the viewpoint of a given class of customers is that the server is not available for providing service some of the time, because it is busy serving customers from a different class. A natural special case of these queues is the class of preemptive priority queues. In this paper, we consider arrivals according the Markovian Arrival Process (MAP) and the server is not available for service at certain times. The service times are assumed to have a general distribution. We provide numerical examples to show that our methods are computationally feasible. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Stability of a two-queue cyclic polling system with BMAPs under gated service and state-dependent time-limited service disciplines

The stability of a cyclic polling system, with a single server and two infinite-buffer queues, is considered. Customers arrive at the two queues according to independent batch Markovian arrival processes. The first queue is served according to the gated service discipline, and the second queue is served according to a state-dependent time-limited service discipline with the preemptive repeat-different property. The state dependence is that, during each cycle, the predetermined limited time of the server’s visit to the second queue depends on the queue length of the first queue at the instant when the server last departed from the first queue. The mean of the predetermined limited time for the second queue either decreases or remains the same as the queue length of the first queue increases. Due to the two service disciplines, the customers in the first queue have higher service priority than the ones in the second queue, and the service fairness of the customers with different service priority levels is also considered. In addition, the switchover times for the server traveling between the two queues are considered, and their means are both positive as well as finite. First, based on two embedded Markov chains at the cycle beginning instants, the sufficient and necessary condition for the stability of the cyclic polling system is obtained. Then, the calculation methods for the variables related to the stability condition are given. Finally, the influence of some parameters on the stability condition of the cyclic polling system is analyzed. The results are useful for engineers not only checking whether the given cyclic polling system is stable, but also adjusting some parameters to make the system satisfy some requirements under the condition that the system is stable.     

A two-queue,one-server model with priority for the longer queue

The queueing model studied consists of one server and two queues. Each queue has its own Poisson arrival stream and service time distribution. After a service completion, the server proceeds with a customer from the longer queue, if the queues are unequal; if the queues are equal, the server chooses with some probability a customer from one of the queues. The model is of practical interest in performance analysis, but also of theoretical interest because the functional equation to be solved has not yet been studied in the queueing literature. A basic analysis of this functional equation is presented. Some numerical results are given to assess the influence of the present service discipline. Some new properties of L.S. transforms of service time distributions are discussed in the appendix.Dr. T. Katayama has formulated the present problem and brought it to the author's attention during his visit in October/November 1984 to the NTT-Electr. Comm. Lab.'s Musashino, Tokyo 180.     

Equilibrium analysis in batch-arrival queues with complementary services

This paper studies a batch-arrival queue with two complementary services. The two services are complementary and any customer has no benefit from obtaining just one of them. To the best of the authors’ knowledge, there are no works contributed to the batch-arrival queues on analysis of the equilibrium behaviors in queueing systems by now. The properties of batch-arrival queues, which is more practical and universal in reality, induce different Nash equilibria under competition or monopoly compared with the single-arrival queues. We observe the joint effect of batch joining rate and cost structure on the behavior of customers and graphically interpret the equilibrium solutions under competition. Moreover, we discuss the model under three types of price structures and give comparisons from customer and server points.     

Strategic joining in M/M/1 retrial queues

The equilibrium and socially optimal balking strategies are investigated for unobservable and observable single-server classical retrial queues. There is no waiting space in front of the server. If an arriving customer finds the server idle, he occupies the server immediately and leaves the system after service. Otherwise, if the server is found busy, the customer decides whether or not to enter a retrial pool with infinite capacity and becomes a repeated customer, based on observation of the system and the reward–cost structure imposed on the system. Accordingly, two cases with respect to different levels of information are studied and the corresponding Nash equilibrium and social optimization balking strategies for all customers are derived. Finally, we compare the equilibrium and optimal behavior regarding these two information levels through numerical examples.     

Chaos in a simple deterministic queueing system

We present a simple discrete-time deterministic queueing model, with one server and two queueing lines. The input rates of both queues are constant and their sum equals the server-capacity. In each time period the server has to decide how much time to spend on each of the two queues. The servers decision rule is a nonlinear, but increasing function of the difference between the two queue-lengths. We investigate how the dynamical behaviour of the queue-lengths and the service process depend on the steepness of the decision function and the ratio of the input rates of the two queues. We show that if the decision function is steep, then for many input-ratios chaotic dynamics occurs.     

Queueing Networks of Random Link Topology: Stationary Dynamics of Maximal Throughput Schedules

In this paper, we study the stationary dynamics of a processing system comprised of several parallel queues and a single server of constant rate. The connectivity of the server to each queue is randomly modulated, taking values 1 (connected) or 0 (severed). At any given time, only the currently connected queues may receive service. A key issue is how to schedule the server on the connected queues in order to maximize the system throughput. We investigate two dynamic schedules, which are shown to stabilize the system under the highest possible traffic load, by scheduling the server on the connected queue of maximum backlog (workload or job number). They are analyzed under stationary ergodic traffic flows and connectivity modulation. The results also extend to the more general case of random server rate.We then investigate the dynamics of acyclic (feed-forward) queueing networks with nodes of the previous type. Their links (connectivities) are stochastically modulated, inducing fluctuating network topologies. We focus on the issue of network throughput and show that it is maximized by simple node server schedules. Rate ergodicity of the traffic flows traversing the network is established, allowing the computation of the maximal throughput.Queueing networks of random topology model several practical systems with unreliable service, including wireless communication networks with extraneous interference, flexible manufacturing systems with failing components, production management under random availability of resources etc.Research supported in part by the National Science Foundation.This revised version was published online in June 2005 with corrected coverdate     

Invariance relations in single server queues with LCFS service discipline

This paper is concerned with single server queues having LCFS service discipline. We give a condition to hold an invariance relation between time and customer average queue length distributions in the queues. The relation is a generalization of that in an ordinary GI/M/1 queue. We compare the queue length distributions for different single server queues with finite waiting space under the same arrival process and service requirement distribution of customer and derive invariance relations among them.This research was supported in part by a grant from the Tokyo Metropolitan Government. The latter part of this paper was written while the author resided at the University of California, Berkeley.     

Heavy Traffic Analysis of Two Coupled Processors

We consider two parallel queues. When both are non-empty, they behave as two independent M/M/1 queues. If one queue is empty the server in the other works at a different rate. We consider the heavy traffic limit, where the system is close to instability. We derive and analyze the heavy traffic diffusion approximation for this model. In particular, we obtain simple integral representations for the joint steady state density of the (scaled) queue lengths. Asymptotic and numerical properties of the solution are studied.     

A two-queue model with Bernoulli service schedule and switching times

In this paper, we present a detailed analysis of a cyclic-service queueing system consisting of two parallel queues, and a single server. The server serves the two queues with a Bernoulli service schedule described as follows. At the beginning of each visit to a queue, the server always serves a customer. At each epoch of service completion in the ith queue at which the queue is not empty, the server makes a random decision: with probability p_i, it serves the next customer; with probability 1-p_i, it switches to the other queue. The server takes switching times in its transition from one queue to the other. We derive the generating functions of the joint stationary queue-length distribution at service completion instants, by using the approach of the boundary value problem for complex variables. We also determine the Laplace-Stieltjes transforms of waiting time distributions for both queues, and obtain their mean waiting times. This revised version was published online in June 2006 with corrections to the Cover Date.     

An Arrival Time Approach to M/G/1-type Queues with Generalized Vacations

We propose a simple way, called the arrival time approach, of finding the queue length distributions for M/G/1-type queues with generalized server vacations. The proposed approach serves as a useful alternative to understanding complicated queueing processes such as priority queues with server vacations and MAP/G/1 queues with server vacations.     

Stochastic scheduling of parallel queues with set-up costs

We consider the problem of allocating a single server to a system of queues with Poisson arrivals. Each queue represents a class of jobs and possesses a holding cost rate, general service distribution, and a set-up cost. The objective is to minimize the expected cost due to the waiting of jobs and the switching of the server. A set-up cost is required to effect an instantaneous switch from one queue to another. We partially characterize an optimal policy and provide a simple heuristic scheduling policy. The heuristic's performance is evaluated in the cases of two and three queues by comparison with a numerically obtained optimal policy. Simulation results are provided to demonstrate the effectiveness of our heuristic over a wide range of problem instances with four queues.     

On a dual hybrid queueing system

This article deals with a hybrid system, in which a single server processes two different queues of units, one called primary and the other one — secondary. The queueing process in the primary system is formed by a Poisson flow of groups of units, while the secondary system is closed. The server’s primary appointment (in hybrid mode I) is to process units in batches until the buffer content drops significantly. In this case, the server takes over a queue in the secondary system (activating hybrid mode II), and he is to complete some minimum amount of jobs (rendered in groups of random sizes during random times). When he is done with this work, he returns to the primary system. If the queue there is not long enough, he waits, thereby activating hybrid mode III. The authors first apply and embellish some techniques from fluctuation theory to find the exit times from respective hybrid modes and queue levels in both systems in terms of their joint functionals. The results are then utilized for the subsequent (semi-regenerative) analysis of the evolution of queueing processes. The authors obtain explicit formulas for the limiting distribution of the queueing process and the mean number of units processed in the secondary system.     

The 1-Center and 1-Highway problem revisited

We consider a two-queue polling model in which customers upon arrival join the shorter of two queues. Customers arrive according to a Poisson process and the service times in both queues are independent and identically distributed random variables having the exponential distribution. The two-dimensional process of the numbers of customers at the queue where the server is and at the other queue is a two-dimensional Markov process. We derive its equilibrium distribution using two methodologies: the compensation approach and a reduction to a boundary value problem.     

Conditional and unconditional distributions forM/G/1 type queues with server vacations

M/G/1 queues with server vacations have been studied extensively over the last two decades. Recent surveys by Boxma [3], Doshi [5] and Teghem [14] provide extensive summary of literature on this subject. More recently, Shanthikumar [11] has generalized some of the results toM/G/1 type queues in which the arrival pattern during the vacations may be different from that during the time the server is actually working. In particular, the queue length at the departure epoch is shown to decompose into two independent random variables, one of which is the queue length at the departure epoch (arrival epoch, steady state) in the correspondingM/G/1 queue without vacations. Such generalizations are important in the analysis of situations involving reneging, balking and finite buffer cyclic server queues. In this paper we consider models similar to the one in Shanthikumar [11] but use the work in the system as the starting point of our investigation. We analyze the busy and idle periods separately and get conditional distributions of work in the system, queue length and, in some cases, waiting time. We then remove the conditioning to get the steady state distributions. Besides deriving the new steady state results and conditional waiting time and queue length distributions, we demonstrate that the results of Boxma and Groenendijk [2] follow as special cases. We also provide an alternative approach to deriving Shanthikumar's [11] results for queue length at departure epochs.     

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.     

Equilibrium and optimal behavior of customers in Markovian queues with multiple working vacations

This paper studies the customers’ equilibrium and socially optimal joining–balking behavior in single-server Markovian queues with multiple working vacations. Different from the classical vacation policies, the server does not completely stop service but maintains a low service rate in vacation state in case there are customer arrivals. Based on different precision levels of the system information, we discuss the observable queues, the partially observable queues, and the unobservable queues, respectively. For each type of queues, we get both the customers’ equilibrium and socially optimal joining–balking strategies and make numerical comparisons between them. We numerically observe that their equilibrium strategy is unique, and especially, the customers’ equilibrium joining probability in vacation state is not necessarily smaller than that in busy state in the partially observable queues. Moreover, we also find that the customers’ individual behavior always deviates from the social expectation and makes the system more congested.     

A Markovian single server with upstream job and downstream demand arrival stream

In this paper we consider a Markovian single server system which processes items arriving from an upstream region (as usual in queueing systems) and is controlled by a demand arrival stream for finished items from a downstream area. A finite storage is available at the server to store finished items not immediately needed in the downstream area. The system considered corresponds to an assembly-like queue with two input streams. The system is stable in a strict sense only if all queues are finite, i.e., both random processes are synchronized via blocking. This notion leads to a complementary system with a very similar state space which is a pair of Markovian single servers with synchronous arrivals. In the mathematical analysis the main focus is on the state probabilities and expectation of minimum and maximum of the two input queues. This revised version was published online in June 2006 with corrections to the Cover Date.