Mostrando recursos 1 - 20 de 72

  1. Heavy-traffic limits for a fork-join networkin the Halfin-Whitt regime

    Lu, Hongyuan; Pang, Guodong
    We study a fork-join network with a single class of jobs, which are forked into a fixed number of parallel tasks upon arrival to be processed at the corresponding multi-server stations. After service completion, each task will join a buffer associated with the service station waiting for synchronization, called “unsynchronized queue”. The synchronization rule requires that all tasks from the same job must be completed, referred to as “non-exchangeable synchronization”. Once synchronized, jobs will leave the system immediately. Service times of the parallel tasks of each job can be correlated and form a sequence of i.i.d. random vectors with a...

  2. Construction of asymptotically optimal control for crisscross network from a free boundary problem

    Budhiraja, Amarjit; Liu, Xin; Saha, Subhamay
    An asymptotic framework for optimal control of multiclass stochastic processing networks, using formal diffusion approximations under suitable temporal and spatial scaling, by Brownian control problems (BCP) and their equivalent workload formulations (EWF), has been developed by Harrison (1988). This framework has been implemented in many works for constructing asymptotically optimal control policies for a broad range of stochastic network models. To date all asymptotic optimality results for such networks correspond to settings where the solution of the EWF is a reflected Brownian motion in $\mathbb{R} _{+}$ or a wedge in $\mathbb{R} _{+}^{2}$. In this work we consider a well studied...

  3. Clearing analysis on phases: Exact limiting probabilities for skip-free, unidirectional, quasi-birth-death processes

    Doroudi, Sherwin; Fralix, Brian; Harchol-Balter, Mor
    A variety of problems in computing, service, and manufacturing systems can be modeled via infinite repeating Markov chains with an infinite number of levels and a finite number of phases. Many such chains are quasi-birth-death processes with transitions that are skip-free in level, in that one can only transition between consecutive levels, and unidirectional in phase, in that one can only transition from lower-numbered phases to higher-numbered phases. We present a procedure, which we call Clearing Analysis on Phases (CAP), for determining the limiting probabilities of such Markov chains exactly. The CAP method yields the limiting probability of each state...

  4. Convergence properties of weighted particle islands with application to the double bootstrap algorithm

    Del Moral, Pierre; Moulines, Eric; Olsson, Jimmy; Vergé, Christelle
    Particle island models [31] provide a means of parallelization of sequential Monte Carlo methods, and in this paper we present novel convergence results for algorithms of this sort. In particular we establish a central limit theorem—as the number of islands and the common size of the islands tend jointly to infinity—of the double bootstrap algorithm with possibly adaptive selection on the island level. For this purpose we introduce a notion of archipelagos of weighted islands and find conditions under which a set of convergence properties are preserved by different operations on such archipelagos. This theory allows arbitrary compositions of these...

  5. Stein’s method for steady-state diffusion approximations: An introduction through the Erlang-A and Erlang-C models

    Braverman, Anton; Dai, J. G.; Feng, Jiekun
    This paper provides an introduction to the Stein method framework in the context of steady-state diffusion approximations. The framework consists of three components: the Poisson equation and gradient bounds, generator coupling, and moment bounds. Working in the setting of the Erlang-A and Erlang-C models, we prove that both Wasserstein and Kolmogorov distances between the stationary distribution of a normalized customer count process, and that of an appropriately defined diffusion process decrease at a rate of $1/\sqrt{R}$, where $R$ is the offered load. Futhermore, these error bounds are universal, valid in any load condition from lightly loaded to heavily loaded.

  6. Asymptotic behavior of a critical fluid model for a processor sharing queue via relative entropy

    Puha, Amber L.; Williams, Ruth J.
    In this paper, we develop a new approach to studying the asymptotic behavior of fluid model solutions for critically loaded processor sharing queues. For this, we introduce a notion of relative entropy associated with measure-valued fluid model solutions. In contrast to the approach used in [12], which does not readily generalize to networks of processor sharing queues, we expect the approach developed in this paper to be more robust. Indeed, we anticipate that similar notions involving relative entropy may be helpful for understanding the asymptotic behavior of critical fluid model solutions for stochastic networks operating under various resource sharing protocols...

  7. Heavy traffic queue length behavior in a switch under the MaxWeight algorithm

    Maguluri, Siva Theja; Srikant, R.
    We consider a switch operating under the MaxWeight scheduling algorithm, under any traffic pattern such that all the ports are loaded. This system is interesting to study since the queue lengths exhibit a multi-dimensional state-space collapse in the heavy-traffic regime. We use a Lyapunov-type drift technique to characterize the heavy-traffic behavior of the expectation of the sum queue lengths in steady-state, under the assumption that all ports are saturated and all queues receive non-zero traffic. Under these conditions, we show that the heavy-traffic scaled queue length is given by $(1-\frac{1}{2n})||\sigma||^{2}$, where $\sigma$ is the vector of the standard deviations of...

  8. Chattering and congestion collapse in an overload switching control

    Perry, Ohad; Whitt, Ward
    Routing mechanisms for stochastic networks are often designed to produce state space collapse (SSC) in a heavy-traffic limit, i.e., to confine the limiting process to a lower-dimensional subset of its full state space. In a fluid limit, a control producing asymptotic SSC corresponds to an ideal sliding mode control that forces the fluid trajectories to a lower-dimensional sliding manifold. Within deterministic dynamical systems theory, it is well known that sliding-mode controls can cause the system to chatter back and forth along the sliding manifold due to delays in activation of the control. For the prelimit stochastic system, chattering implies fluid-scaled...

  9. Randomized assignment of jobs to servers in heterogeneous clusters of shared servers for low delay

    Mukhopadhyay, Arpan; Karthik, A.; Mazumdar, Ravi R.
    We consider the problem of assignning jobs to servers in a multi-server system consisting of $N$ parallel processor sharing servers, categorized into $M$ ($\ll N$) different types according to their processing capacities or speeds. Jobs of random sizes arrive at the system according to a Poisson process with rate $N\lambda$. Upon each arrival, some servers of each type are sampled uniformly at random. The job is then assigned to one of the sampled servers based on their states. We propose two schemes, which differ in the metric for choosing the destination server for each arriving job. Our aim is to...

  10. Dynamic scheduling for parallel server systems in heavy traffic: Graphical structure, decoupled workload matrix and some sufficient conditions for solvability of the Brownian control problem

    Pesic, V.; Williams, R. J.
    We consider a dynamic scheduling problem for parallel server systems. J. M. Harrison has proposed a scheme for using diffusion control problems to approximately solve such control problems for heavily loaded systems. This approach has been very successfully used in the special case when the diffusion control problem can be reduced to an equivalent one for a one-dimensional workload process. However, it remains a challenging open problem to make substantial progress on using Harrison’s scheme when the workload process is more than one-dimensional. Here we present some new structural results concerning the diffusion control problem for parallel server systems with...

  11. On queue-size scaling for input-queued switches

    Shah, D.; Tsitsiklis, J. N.; Zhong, Y.
    We study the optimal scaling of the expected total queue size in an $n\times n$ input-queued switch, as a function of the number of ports $n$ and the load factor $\rho$, which has been conjectured to be $\Theta(n/{(}1-\rho{)})$ (cf. [15]). In a recent work [16], the validity of this conjecture has been established for the regime where $1-\rho=O(1/n^{2})$. In this paper, we make further progress in the direction of this conjecture. We provide a new class of scheduling policies under which the expected total queue size scales as $O\big(n^{1.5}(1-\rho)^{-1}\log\big(1/(1-\rho)\big)\big)$ when $1-\rho=O(1/n)$. This is an improvement over the state of the...

  12. Giant component in random multipartite graphs with given degree sequences

    Gamarnik, David; Misra, Sidhant
    We study the problem of the existence of a giant component in a random multipartite graph. We consider a random multipartite graph with $p$ parts generated according to a given degree sequence $n_{i}^{\mathbf{d}}(n),n\ge1$ which denotes the number of vertices in part $i$ of the multipartite graph with degree given by the vector $\mathbf{d}$ in an $n$-node graph. We assume that the empirical distribution of the degree sequence converges to a limiting probability distribution. Under certain mild regularity assumptions, we characterize the conditions under which, with high probability, there exists a component of linear size. The characterization involves checking whether the...

  13. Solving the drift control problem

    Ormeci Matoglu, Melda; Vande Vate, John; Wang, Huizhu
    We model the problem of managing capacity in a build-to-order environment as a Brownian drift control problem. We formulate a structured linear program that models a practical discretization of the problem and exploit a strong relationship between relative value functions and dual solutions to develop a functional lower bound for the continuous problem from a dual solution to the discrete problem. Refining the discretization proves a functional strong duality for the continuous problem. The linear programming formulation is so badly scaled, however, that solving it is beyond the capabilities of standard solvers. By demonstrating the equivalence between strongly feasible bases...

  14. On bid-price controls for network revenue management

    Ata, Barış; Akan, Mustafa
    We consider a network revenue management problem and advance its dual formulation. The dual formulation reveals that the (optimal) shadow price of capacity forms a nonnegative martingale. This result is proved under minimal assumptions on network topology and stochastic nature of demand, allowing an arbitrary statistical dependence structure across time and products. Next, we consider a quadratic perturbation of the network revenue management problem and show that a simple (perturbed) bid-price control is optimal for the perturbed problem; and it is $\varepsilon$-optimal for the original network revenue management problem. Finally, we consider a predictable version of this control, where the...

  15. Tightness of stationary distributions of a flexible-server system in the Halfin-Whitt asymptotic regime

    Stolyar, Alexander L.
    A large-scale flexible service system with two large server pools and two types of customers is considered. Servers in pool 1 can only serve type 1 customers, while server in pool 2 are flexible – they can serve both types 1 and 2. (This is a so-called “N-system.”) The customer arrival processes are Poisson and customer service requirements are independent exponentially distributed. The service rate of a customer depends both on its type and the pool where it is served. A priority service discipline, where type 2 has priority in pool 2, and type 1 prefers pool 1, is considered....

  16. Models with hidden regular variation: Generation and detection

    Das, Bikramjit; Resnick, Sidney I.
    We review the notions of multivariate regular variation (MRV) and hidden regular variation (HRV) for distributions of random vectors and then discuss methods for generating models exhibiting both properties concentrating on the non-negative orthant in dimension two. Furthermore we suggest diagnostic techniques that detect these properties in multivariate data and indicate when models exhibiting both MRV and HRV are plausible fits for the data. We illustrate our techniques on simulated data, as well as two real Internet data sets.

  17. On patient flow in hospitals: A data-based queueing-science perspective

    Armony, Mor; Israelit, Shlomo; Mandelbaum, Avishai; Marmor, Yariv N.; Tseytlin, Yulia; Yom-Tov, Galit B.
    Hospitals are complex systems with essential societal benefits and huge mounting costs. These costs are exacerbated by inefficiencies in hospital processes, which are often manifested by congestion and long delays in patient care. Thus, a queueing-network view of patient flow in hospitals is natural for studying and improving its performance. The goal of our research is to explore patient flow data through the lens of a queueing scientist. The means is exploratory data analysis (EDA) in a large Israeli hospital, which reveals important features that are not readily explainable by existing models. ¶ Questions raised by our EDA include: Can a simple...

  18. Control of parallel non-observable queues: Asymptotic equivalence and optimality of periodic policies

    Anselmi, Jonatha; Gaujal, Bruno; Nesti, Tommaso
    We consider a queueing system composed of a dispatcher that routes jobs to a set of non-observable queues working in parallel. In this setting, the fundamental problem is which policy should the dispatcher implement to minimize the stationary mean waiting time of the incoming jobs. We present a structural property that holds in the classic scaling of the system where the network demand (arrival rate of jobs) grows proportionally with the number of queues. Assuming that each queue of type $r$ is replicated $k$ times, we consider a set of policies that are periodic with period $k\sum_{r}p_{r}$ and such that...

  19. Moderate deviations for recursive stochastic algorithms

    Dupuis, Paul; Johnson, Dane
    We prove a moderate deviation principle for the continuous time interpolation of discrete time recursive stochastic processes. The methods of proof are somewhat different from the corresponding large deviation result, and in particular the proof of the upper bound is more complicated.

  20. The morphing of fluid queues into Markov-modulated Brownian motion

    Latouche, Guy; Nguyen, Giang T.
    Ramaswami showed recently that standard Brownian motion arises as the limit of a family of Markov-modulated linear fluid processes. We pursue this analysis with a fluid approximation for Markov-modulated Brownian motion. We follow a Markov-renewal approach and we prove that the stationary distribution of a Markov-modulated Brownian motion reflected at zero is the limit from the well-analyzed stationary distribution of approximating linear fluid processes. Thus, we provide a new approach for obtaining the stationary distribution of a reflected MMBM without time-reversal or solving partial differential equations. Our results open the way to the analysis of more complex Markov-modulated processes. ¶ Key matrices...

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.