Search

In 1964, Kleinrock proposed a queueing discipline for a single-server queue in which customers from different classes accumulate priority as linear functions of their waiting time. At the instant that a server becomes free, it selects the waiting customer with the highest accumulated priority, provided that the queue is nonempty. He developed a recursion for calculating the expected waiting time for each class. In 2014, Stanford, Taylor, and Ziedins reconsidered this queue, which they termed the accumulating priority queue (APQ), and derived the waiting time distribution for each class. Kleinrock and Finkelstein in 1967 also studied an accumulating priority system in which customers' priorities increase as a power-law function of their waiting time. They established that it is possible to associate a particular linear APQ with such a power-law APQ, so that the expected waiting times of customers from all classes are preserved. In this paper, we extend their analysis to characterise the class of nonlinear APQs for which an equivalent linear APQ can be found, in the sense that, for identical sample paths of the arrival and service processes, the ordering of all customers is identical at all times in both the linear and nonlinear systems. [ABSTRACT FROM AUTHOR]

The article presents a study on the performance of the accumulating priority queue, also known as the time-dependent priority queue as developed by L. Kleinrock in his study of queueing systems. Topics include waiting time distributions for priority queues, the accumulation of priority as a linear function of time, the mathematical aspects of the maximum priority process, and non-preemptive priority.

We study a simple network with two parallel batch-service queues, where service at a queue commences when the batch is full and each queue is served by infinitely many servers. A stream of general arrivals observe the current state of the system on arrival and choose which queue to join to minimize their own expected transit time. We show that for each set of parameter values there exists a unique user equilibrium policy and that it possesses various monotonicity properties. User equilibrium policies for probabilistic routing are also discussed and compared with the state-dependent setting. [ABSTRACT FROM AUTHOR]

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|∞ 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. [ABSTRACT FROM AUTHOR]

We consider admission and routing controls for a system of N parallel tandem queues with finite buffers as N becomes large, with the aim of minimizing costs due to loss. We obtain the fluid limit as N→∞, and solve a related optimization problem. Asymptotically, for N large, the optimal cost and associated control take one of two forms, depending on the ratio between the cost of blocking an arrival at entry and discarding after service at the first queue. [ABSTRACT FROM AUTHOR]

We consider a system of parallel, finite tandem queues with loss. Each tandem queue consists of two single-server queues in series, with capacities C1 and C2 and exponential service times with rates μ1and μ2 for the first and second queues, respectively. Customers that arrive at a queue that is full are lost. Customers arriving at the system can choose which tandem queue to enter. We show that, for customers choosing a queue to maximise the probability of their reaching the destination (or minimise their individual loss probability), it will sometimes be optimal to choose queues with more customers already present and/or with greater residual service requirements (where preceding customers are further from their final destination). [ABSTRACT FROM AUTHOR]