Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLarge fork-join queues with nearly deterministic arrival and service times
82
0
0.0
(
0
)
Added by
Dennis Schol
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper, we study an $N$ server fork-join queue with nearly deterministic arrival and service times. Specifically, we present a fluid limit for the maximum queue length as $Ntoinfty$. This fluid limit depends on the initial number of tasks. In order to prove these results, we develop extreme value theory and diffusion approximations for the queue lengths.
rate research
Read More
We study extreme values in certain fork-join queueing networks: consider $N$ identical queues with a common arrival process and independent service processes. All arrival and service processes are deterministic with random perturbations following Brownian motions. We prove that as $Nrightarrow infty$, the scaled maximum of $N$ steady-state queue lengths converges in distribution to a normally distributed random variable. We also explore repercussions of this result for original equipment manufacturers (OEMs) that assemble a large number of components, each produced using specialized equipment, into complex systems. Component production capacity is subject to fluctuations, causing a high risk of shortages of at least one component, which in turn results in costly system production delays. OEMs hedge this risk by investing in a combination of excess production capacity and component inventories. We formulate a stylized model of the OEM that enables us to study the resulting trade-off between shortage risk, inventory costs, and capacity costs. Our asymptotic extreme value results translate into various asymptotically exact methods for cost-optimal inventory and capacity decisions, some of which are in closed form. Numerical results indicate that our results are asymptotically exact, while for transient times they depend on model parameters.
We consider a service system with two Poisson arrival queues. A server chooses which queue to serve at each moment. Once a queue is served, all the customers will be served within a fixed amount of time. This model is useful in studying airport shuttling or certain online computing systems. We propose a simple yet optimal state-independent policy for this problem which is not only easy to implement, but also performs very well.
It is interesting and challenging to study double-ended queues with First-Come-First-Match discipline under customers impatient behavior and non-Poisson inputs. Note that the system stability can be guaranteed by the customers impatient behavior, but the existence of impatient customers makes analysis of such double-ended queues more difficult or even impossible to find any explicitly analytic solution due to having to deal with more complicated level-dependent Markov processes. Thus it becomes more and more important to develop effective algorithms in a variety of practical matching problems. This paper studies a block-structured double-ended queue, whose block structure comes from two independent Markovian arrival processes (MAPs), which are non-Poisson inputs. We first show that such a queue can be expressed as a new bilateral quasi birth-and-death (QBD) process which has its own interest. Based on this, we provide a detailed analysis for the bilateral QBD process and the double-ended queue, including the system stability, the stationary queue length distributions, the average stationary queue lengths, and the sojourn time of any arriving customers. Then we develop three effective algorithms for computing the performance measures (e.g., the stationary queue length distributions, the average stationary queue lengths, and the average sojourn time) of the double-ended queue. Finally, we use some numerical examples in tabular and graphical to illustrate how the performance measures are influenced by some key system parameters. We believe that the methodology and results given in this paper can be applicable to deal with more general double-ended queues in practice, and develop effective algorithms for the purpose of many actual uses.
We study a token-based central queue with multiple customer types. Customers of each type arrive according to a Poisson process and have an associated set of compatible tokens. Customers may only receive service when they have claimed a compatible token. If upon arrival, more than one compatible token is available, an assignment rule determines which token will be claimed. The service rate obtained by a customer is state-dependent, i.e., it depends on the set of claimed tokens and on the number of customers in the system. Our first main result shows that, provided the assignment rule and the service rates satisfy certain conditions, the steady-state distribution has a product form. We show that our model subsumes known families of models that have product-form steady-state distributions including the order-independent queue of Krzesinski (2011) and the model of Visschers et al. (2012). Our second main contribution involves the derivation of expressions for relevant performance measures such as the sojourn time and the number of customers present in the system. We apply our framework to relevant models, including an M/M/K queue with heterogeneous service rates, the MSCCC queue, multi-server models with redundancy and matching models. For some of these models, we present expressions for performance measures that have not been derived before.
We study infinite-server queues in which the arrival process is a Cox process (or doubly stochastic Poisson process), of which the arrival rate is given by shot noise. A shot-noise rate emerges as a natural model, if the arrival rate tends to display sudden increases (or: shots) at random epochs, after which the rate is inclined to revert to lower values. Exponential decay of the shot noise is assumed, so that the queueing systems are amenable for analysis. In particular, we perform transient analysis on the number of customers in the queue jointly with the value of the driving shot-noise process. Additionally, we derive heavy-traffic asymptotics for the number of customers in the system by using a linear scaling of the shot intensity. First we focus on a one dimensional setting in which there is a single infinite-server queue, which we then extend to a network setting.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
