Polling systems with multiple coupled servers

We consider polling systems with multiple coupled servers. We explore the class of systems that allow an exact analysis. For these systems we present distributional results for the waiting time, the marginal queue length, and the joint queue length at polling epochs. The class in question includes several single-queue systems with a varying number of servers, two-queue two-server systems with exhaustive service and exponential service times, as well as infinite-server systems with an arbitrary number of queues, exhaustive or gated service, and deterministic service times.     

Marginal productivity index policies for scheduling a multiclass delay-/loss-sensitive queue

This paper addresses the problem of scheduling a Markovian multiclass queue with a finite dedicated buffer for each class, where class-dependent linear holding and rejection cost rates model differing levels of tolerance to delay and loss. The goal is to design well-grounded and tractable scheduling policies that nearly minimize expected total discounted or long-run average cost. New dynamic index policies are introduced, awarding higher priority to classes with larger index values, where a class’ index measures the marginal productivity of work at its current state. The results are obtained by deploying the work-cost analysis approach to marginal productivity indices (MPIs) for restless bandits developed by the author, which is extended to the bias criterion. The MPI furnishes new insights: for a loss-sensitive class, it is a decreasing function of the number of empty buffer spaces, independent of the buffer size; for a delay-sensitive class, it is a decreasing function of the queue length. Such opposite orderings show that preventive work is more valuable than reactive work for the latter classes, whereas the opposite holds for the former. The results of a computational study on two-class instances are reported, shedding light on how the MPI policy’s relative performance varies with each parameter. Parameter ranges are thus identified where the MPI policy is near optimal, and substantially outperforms conventional benchmark policies. 2000 Mathematics Subject Classification 90B22 · 90B36 · 90B18 · 60K25 · 60K30 · 68M20     

Two thresholds of a batch arrival queueing system under modified T vacation policy with startup and closedown

This paper studies the operating characteristics of the variant of an M^[x]/G/1 vacation queue with startup and closedown times. After all the customers are served in the system exhaustively, the server shuts down (deactivates) by a closedown time, and then takes at most J vacations of constant time length T repeatedly until at least one customer is found waiting in the queue upon returning from a vacation. If at least one customer is present in the system when the server returns from a vacation, then the server reactivates and requires a startup time before providing the service. On the other hand, if no customers arrive by the end of the J th vacation, the server remains dormant in the system until at least one customer arrives. We will call the vacation policy modified T vacation policy. We derive the steady‐state probability distribution of the system size and the queue waiting time. Other system characteristics are also investigated. The long‐run average cost function per unit time is developed to determine the suitable thresholds of T and J that yield a minimum cost. Copyright © 2007 John Wiley & Sons, Ltd.     

Heavy traffic approximations for busy period in an M/G/∞ queue

A necessary and sufficient condition is given for busy period in an M/G/∞ queue to be asymptotically exponential with mean equal to expected busy period, as traffic intensity increases. The case where this condition fails is also investigated, and the results applied.     

Periodic solution to the time-inhomogeneous multi-server Poisson queue

We derive the periodic family of asymptotic distributions and the periodic moments for number in the queue for the multi-server queue with Poisson arrivals and exponential service for time-varying periodic arrival and departure rates, and time-varying periodic number of servers. The method is a straight-forward application of generating functions.     

多级适应性休假MX/G/1排队系统的离去过程

考虑多级适应性休假的M~X/G/1排队系统的离去过程.运用全概率分解,更新过程理论和拉普拉斯-斯蒂尔吉变换,讨论了从初始状态i(i=0,1,…)出发,在(0,t]中服务完顾客的平均数,揭示了离去过程的特殊结构,并由此得到了一些特殊排队模型的相应指标.     

Routing in Queues with Delayed Information

We compare two routing-control strategies in a high-speed communication network with c parallel channels (routes), where information on service completions in down-stream servers is randomly delayed. The controller can either hold arriving messages in a common buffer, dispatching them to servers only when the delayed information becomes available (Wait option), or route jobs to the various channels, in a round-robin fashion, immediately upon their arrival. Interpreting the delays as servers's vacations and considering overall queue sizes as a measure of performance, we show that the Wait strategy is superior as long as the mean information delay is below a threshold. We calculate threshold values for various combinations of load and c and show that, for a given load, the threshold increases with c and, for fixed c, the threshold decreases with an increasing load. If information is delayed on arrival instants, rather than on service completions, we show that the system can be viewed as a tandem queue and derive a generalization of a queue-decomposition result obtained by Altman, Kofman and Yechiali.     

Analysis of an M/G/∞ queue with batch arrivals and batch-dedicated servers

We analyze an M/G/∞ queue with batch arrivals, where jobs belonging to a batch have to be processed by the same server. The number of jobs in the system is characterized as a compound Poisson random variable through a scaling of the original arrival and batch size processes.     

Three Cases of Light-Traffic Insensitivity of the Loss Probability in a GI/G/m/0 Loss System to the Shape of the Service Time Distribution

A GI/G/m/0 loss system is considered. Three cases of light-traffic insensitivity of the loss probability to the shape of the service time distribution, given its first moment, are investigated in a triangle array setting.