Small work-load mode in a queueing system with random nonstationary intensity

We consider a queueing system of M _t R|GI|1|∞ type with doubly stochastic Poisson arrival stream. The case of a small work load in such a system is studied. We derive an asymptotic expansion in the work-load smallness parameter of the distribution function of the virtual waiting time.     

A queueing model for a nonreliable multiterminal system with polling scheduling

This paper deals with a nonhomogeneous finite-source queueing model to describe the performance of a multiterminal system subject to random breakdowns under the polling service discipline. The model studied here is a closed queueing network which has three service stations. a CPU (single server), terminals (infinite server), a repairman (single server), and a finite number of customers (jobs) that have distinct service rates at the service stations. The CPU's repair has preemptive priority over the terminal repairs, and failure of the CPU stops the service of the other stations, thus the nodes are not independent. It can be viewed as a continuation of papers by the authors (see references), which discussed a FIFO (first-in, first-out) and a PPS (priority processor sharing) serviced queueing model subject to random breakdowns. All random variables are assumed to be independent and exponentially distributed. The system behavior can be described by a Markov chain, but the number of states is very large. The purpose of this paper is to give a recursive computational approach to solve steady-state equations and to illustrate the problem in question using some numerical results. Supported by the Hungarian National Foundation for Scientific Research (grant Nos. OTKA T014974/95 and T016933/95) Proceedings of the Seminar on Stability Problems for Stochastic Models. Hajdúszoboszló, Hungary, 1997, Part, II.     

Analysis of a discrete-time queueing system with time-limited service

We analyze a discrete-time, single-server queueing system in which the length of each service period is limited. The server takes a vacation when the limit expires or the queue empties, whichever occurs first. In the former case, the preempted service is resumed after the vacation without loss or creation of any work. This system models the transmission of message frames from a station on timed-token local-area networks (for example, FDDI and IEEE 802.4 token bus). We study the process of the unfinished work and the joint process of the queue size and the remaining service time. By using the technique of discrete Fourier transforms to determine some unknown functions in the governing equations, we numerically obtain exact mean waiting times.A part of the work of H. Takagi was done while he was with IBM Research, Tokyo Research Laboratory.     

User equilibria for a parallel queueing system with state dependent routing

Consider a system of two queues in parallel, one of which is a ⋅|M|1 single-server infinite capacity queue, and the other a ⋅|G ^(N)|∞ batch service queue. A stream of general arrivals choose which queue to join, after observing the current state of the system, and so as to minimize their own expected delay. We show that a unique user equilibrium (user optimal policy) exists and that it possesses various monotonicity properties, using sample path and coupling arguments. This is a very simplified model of a transportation network with a choice of private and public modes of transport. Under probabilistic routing (which is equivalent to the assumption that users have knowledge only of the mean delays on routes), the network may exhibit the Downs–Thomson paradox observed in transportation networks with expected delay increasing as the capacity of the ⋅|M|1 queue (private transport) is increased. We give examples where state-dependent routing mitigates the Downs–Thomson effect observed under probabilistic routing, and providing additional information on the state of the system to users reduces delay considerably.     

Stability of a priority queueing system with customer transfers

This paper is concerned with the stability of a preemptive priority queueing system with customer transfers. Conditions for the queueing system to be stable/unstable are found. An interesting result is that the stability/instability conditions are independent of the service rates of lower priority customers and the transfer rates.     

Rational joining behavior in a queueing system with abandonments

We consider individually and socially-optimal joining behavior in a first-come first-served M/M/1 queueing system where a customer's need for service may expire after an exponentially distributed length of time. We show that the individual behavior is independent of the rate of abandonment. We use the fact that the individual behavior in a last-come first-served M/M/1 queue is socially-optimal to compute the socially-optimal threshold.     

A note on conservation laws for a multiclass service queueing system with setup times

This paper derives a conservation law for mean waiting times in a single-server multi-class service queueing system (M ^X/G/1 type queue) with setup times which may be dependent on multiple customer classes and its arrival batch size by using the work decomposition property in the queueing system with vacations.     

On the optimality of a full-service policy for a queueing system with discounted costs

We provide weak sufficient conditions for a full-service policy to be optimal in a queueing control problem in which the service rate is a dynamic decision variable. In our model there are service costs and holding costs and the objective is to minimize the expected total discounted cost over an infinite horizon. We begin with a semi-Markov decision model for a single-server queue with exponentially distributed inter-arrival and service times. Then we present a general model with weak probabilistic assumptions and demonstrate that the full-service policy minimizes both finite-horizon and infinite-horizon total discounted cost on each sample path.     

An assignment problem for a parallel queueing system with two heterogeneous servers

In this paper, we consider an optimization problem for a parallel queueing system with two heterogeneous servers. Each server has its own queue and customers arrive at each queue according to independent Poisson processes. Each service time is independent and exponentially distributed. When a customer arrives at queue 1, the customers in queue 1 can be transferred to queue 2 by paying an assignment cost which is proportional to the number of moved customers. Holding cost is a function of the pair of queue lengths of the two servers. Our objective is to minimize the expected total discounted cost. We use the dynamic programming approach for this problem. Considering the pair of queue lengths as a state space, we show that the optimal policy has a switch over structure under some conditions on the holding cost.     

Analysis of a two-phase queueing system with a fixed-size batch policy

We consider a single-server, two-phase queueing system with a fixed-size batch policy. Customers arrive at the system according to a Poisson process and receive batch service in the first-phase followed by individual services in the second-phase. The batch service in the first-phase is applied for a fixed number (k) of customers. If the number of customers waiting for the first-phase service is less than k when the server completes individual services, the system stays idle until the queue length reaches k. We derive the steady state distribution for the system’s queue length. We also show that the stochastic decomposition property can be applied to our model. Finally, we illustrate the process of finding the optimal batch size that minimizes the long-run average cost under a linear cost structure.     

An optimality criterion for a limited capacity queueing system

A single server, limited capacity queueing system with Poisson arrivals and exponential service is studied. The joint probability distribution of the number of times the system reaches its capacity in time interval (0t] and the number of customers in the system at time i has been obtained. From, the joint probability, the probability that the system has reached its capacity m times in time interval (0t] has been determined and the expectation and variance have been found explicitly. A criterion for the system to be optimum is established and is illustrated numerically.     

Waiting time analysis of a two-stage queueing system with priorities

A two-stage queueing system with two types of customers and non-preemptive priorities is analyzed. There is no waiting space between stages and so the blocking phenomenon is observed. The arrivals follow a Poisson distribution for the high priority customers and a gamma distribution for the low priority customers, while all service times are arbitrarily distributed. We derive expressions for the Laplace transform of the waiting time density of a low priority customer both in the transient and the steady state.     

The stability of a non-homogeneous queueing system with regenerative input

A queueing system with nonidentical service channels, a regenerative input, and a renewal service process at each channel is considered. The ergodic conditions are found when the basic process describing the system (and including the queue-size and the waiting time vector) is regenerative with finite expectation of the regeneration cycle length. The asymptotic properties of the embedded renewal process of the regeneration points are used. The zero-delayed and delayed cases are considered separately. Some queueing network applications are discussed. Supported by the Nordic Council of Ministers. Proceedings of the XVII Seminar on Stability Problems for Stochastic Models, Kazan, Russia, 1995, Part II.     

Strategic customer behavior in a queueing system with a loss subsystem

In the spirit of Little’s law \(L=\lambda W\) and its extension \(H=\lambda G\) we use sample-path analysis to give a general conservation law. For queueing models the law relates the asymptotic average workload in the system to the conditional asymptotic average sojourn time and service times distribution function. This law generalizes previously obtained conservation laws for both single- and multi-server systems, and anticipating and non-anticipating scheduling disciplines. Applications to single- and multi-class queueing and other systems that illustrate the versatility of this law are given. In particular, we show that, for anticipative and non-anticipative scheduling rules, the unconditional delay in a queue is related to the covariance of service times and queueing delays.     

Optimal admission control in a queueing system with heterogeneous traffic

We consider optimal admission control of the GI/PH/1-type queueing system. The problem is then reduced to that of determining multi-threshold strategies. Some numerical examples are presented. The results have applications in the optimal input control of information flow in a computer communication network with heterogeneous traffic.     

Controlling arrivals for a queueing system with an unreliable server: Newton-Quasi method

This paper deals with the control policy of a removable and unreliable server for an M/M/1/K queueing system, where the removable server operates an F-policy. The so-called F-policy means that when the number of customers in the system reaches its capacity K (i.e. the system becomes full), the system will not accept any incoming customers until the queue length decreases to a certain threshold value F. At that time, the server initiates an exponential startup time with parameter γ and starts allowing customers entering the system. It is assumed that the server breaks down according to a Poisson process and the repair time has an exponential distribution. A matrix analytical method is applied to derive the steady-state probabilities through which various system performance measures can be obtained. A cost model is constructed to determine the optimal values, say (F^∗, μ^∗, γ^∗), that yield the minimum cost. Finally, we use the two methods, namely, the direct search method and the Newton-Quasi method to find the global minimum (F^∗, μ^∗, γ^∗). Numerical results are also provided under optimal operating conditions.     

Optimal inventory replenishment policy for a queueing system with finite waiting room capacity

We treat an inventory control problem in a facility that provides a single type of service for customers. Items used in service are supplied by an outside supplier. To incorporate lost sales due to service delay into the inventory control, we model a queueing system with finite waiting room and non-instantaneous replenishment process and examine the impact of finite buffer on replenishment policies. Employing a Markov decision process theory, we characterize the optimal replenishment policy as a monotonic threshold function of reorder point under the discounted cost criterion. We present a simple procedure that jointly finds optimal buffer size and order quantity.