Queues with group arrivals and exhaustive service discipline

Queues with compound Poisson arrivals, phase-type service and exhaustive service discipline are studied. An algorithmic method is developed to compute the steady-state probability distribution of the number of customers in the system with unlimited or limited queue capacities. Examples with different model parameters are given to show the computational efficiency of the method. In the Appendix, the stochastic decomposition property for the queues with single arrivals and with exhaustive service discipline is extended to queues with group arrivals.     

Admission control with batch arrivals

We consider the problem of dynamic admission control in a multi-class Markovian loss system receiving random batches, where each admitted class-i job demands an exponential service with rate μ, and brings a reward r_i. We show that the optimal admission policy is a sequential threshold policy with monotone thresholds.     

Product form in networks of queues with batch arrivals and batch services

A product form equilibrium distribution is derived for a class of queueing networks in either discrete or continuous time, in which multiple customers arrive simultaneously and batches of customers complete service simultaneously.     

A single-server queue with batch arrivals and semi-Markov services

We investigate the transient and stationary queue length distributions of a class of service systems with correlated service times. The classical \(M^X/G/1\) queue with semi-Markov service times is the most prominent example in this class and serves as a vehicle to display our results. The sequence of service times is governed by a modulating process J(t). The state of \(J(\cdot )\) at a service initiation time determines the joint distribution of the subsequent service duration and the state of \(J(\cdot )\) at the next service initiation. Several earlier works have imposed technical conditions, on the zeros of a matrix determinant arising in the analysis, that are required in the computation of the stationary queue length probabilities. The imposed conditions in several of these articles are difficult or impossible to verify. Without such assumptions, we determine both the transient and the steady-state joint distribution of the number of customers immediately after a departure and the state of the process J(t) at the start of the next service. We numerically investigate how the mean queue length is affected by variability in the number of customers that arrive during a single service time. Our main observations here are that increasing variability may reduce the mean queue length, and that the Markovian dependence of service times can lead to large queue lengths, even if the system is not in heavy traffic.     

Analysis of job assignment with batch arrivals among heterogeneous servers

We revisit the problem of job assignment to multiple heterogeneous servers in parallel. The system under consideration, however, has a few unique features. Specifically, repair jobs arrive to the queueing system in batches according to a Poisson process. In addition, servers are heterogeneous and the service time distributions of the individual servers are general. The objective is to optimally assign each job within a batch arrival to minimize the long-run average number of jobs in the entire system. We focus on the class of static assignment policies where jobs are routed to servers upon arrival according to pre-determined probabilities. We solve the model analytically and derive the structural properties of the optimal static assignment. We show that when the traffic is below a certain threshold, it is better to not assign any jobs to slower servers. As traffic increases (either due to an increase in job arrival rate or batch size), more slower servers will be utilized. We give an explicit formula for computing the threshold. Finally we compare and evaluate the performance of the static assignment policy to two dynamic policies, specifically the shortest expected completion policy and the shortest queue policy.     

On the distributions of infinite server queues with batch arrivals

Queues that feature multiple entities arriving simultaneously are among the oldest models in queueing theory, and are often referred to as “batch” (or, in some cases, “bulk”) arrival queueing systems. In this work, we study the effect of batch arrivals on infinite server queues. We assume that the arrival epochs occur according to a Poisson process, with treatment of both stationary and non-stationary arrival rates. We consider both exponentially and generally distributed service durations, and we analyze both fixed and random arrival batch sizes. In addition to deriving the transient mean, variance, and moment-generating function for time-varying arrival rates, we also find that the steady-state distribution of the queue is equivalent to the sum of scaled Poisson random variables with rates proportional to the order statistics of its service distribution. We do so through viewing the batch arrival system as a collection of correlated sub-queues. Furthermore, we investigate the limiting behavior of the process through a batch scaling of the queue and through fluid and diffusion limits of the arrival rate. In the course of our analysis, we make important connections between our model and the harmonic numbers, generalized Hermite distributions, and truncated polylogarithms.

     

Admission control and pricing in a queue with batch arrivals

We investigate a problem of admission control in a queue with batch arrivals. We consider a single server with exponential service times and a compound Poisson arrival process. Each arriving batch computes its expected benefit and decides whether or not to enter the system. The controller’s problem is to set state dependent prices for arriving batches. Once prices have been set we formulate the admission control problem, derive properties of the value function, and obtain the optimal admission policy.     

The secretary problem with multiple job vacancies and batch candidate arrivals

We extend the secretary problem with multiple vacancies to allow batch arrival of candidates. We establish structural properties of the optimal policies. We show that the optimal reward is convex and submodular in the values of candidates, which means that there is benefit for having a candidate pool with more variable or less interdependent values. Similar properties continue to hold when there are multiple classes of vacancies. Our model is applicable to recruitment, dynamic auctions and sequential investment.     

Queuing system with state-dependent controlled batch arrivals and server under maintenance

This paper deals with a single server Markovian queue subject to maintenance of the server. A batch of customers is allowed whenever the server is idle such that each individual customer in the batch is subject to a control admission policy upon arrival. Explicit expressions are obtained for the time dependent probabilities of the system size in terms of the modified Bessel functions. The steady state analysis and key performance measures of the system are also studied. Finally, some numerical illustrations are presented.     

Complete characterisation of the customer delay in a queueing system with batch arrivals and batch service

Whereas the buffer content of batch-service queueing systems has been studied extensively, the customer delay has only occasionally been studied. The few papers concerning the customer delay share the common feature that only the moments are calculated explicitly. In addition, none of these surveys consider models including the combination of batch arrivals and a server operating under the full-batch service policy (the server waits to initiate service until he can serve at full capacity). In this paper, we aim for a complete characterisation—i.e., moments and tail probabilities - of the customer delay in a discrete-time queueing system with batch arrivals and a batch server adopting the full-batch service policy. In addition, we demonstrate that the distribution of the number of customer arrivals in an arbitrary slot has a significant impact on the moments and the tail probabilities of the customer delay.     

A retrial queue with structured batch arrivals,priorities and server vacations

A retrial queue accepting two types of customers with correlated batch arrivals and preemptive resume priorities is studied. The service times are arbitrarily distributed with a different distribution for each type of customer and the server takes a single vacation each time he becomes free. For such a model the state probabilities are obtained both in a transient and in a steady state. Finally, the virtual waiting time of an arbitrary ordinary customer in a steady state is analysed.     

Time-dependent analysis of a queue with batch arrivals andn levels of nonpreemptive priority

A queueing system with batch arrivals andn classes of customers with nonpreemptive priorities between them is considered. Each batch arrives according to the Poisson distribution and contains customers of all classes while the service times follow arbitrary distributions with different probability density functions for each class. For such a model the system states probabilities both in the transient and in the steady state are analysed and also expressions for the Laplace transforms of the busy period densities for each class and for the general busy period are obtained.     

Performance analysis for assemble-to-order systems with general renewal arrivals and random batch demands

We study multi-product and multi-item assemble-to-order systems under general assumptions on demand patterns and replenish leadtime distributions. We only assume that the demand process of each product being a renewal process, and the replenish leadtimes follow general distributions. Based upon techniques from renewal theory, we developed procedures for approximating key performance measures of these inventory systems, such as average inventory and immediate order fill rate. We also obtain qualitative results that reveal the impacts of changes in demand patterns and leadtime variability upon the performance of the systems.     

Threshold control by a single-server retrial queue with batch arrivals and group services

A controlled single-server retrial queueing system is investigated. Customers arrive according to batch Markovian arrival process. The system has several operation modes which are controlled by means of a threshold strategy. The stationary distribution is calculated. Optimization problem is considered and a numerical example is presented.