Explore the vast range of titles available.

The curse of dimensionality gives rise to prohibitive computational requirements that render infeasible the exact solution of large-scale stochastic control problems. We study an efficient method based on linear programming for approximating solutions to such problems. The approach \"fits\" a linear combination of pre-selected basis functions to the dynamic programming cost-to-go function. We develop error bounds that offer performance guarantees and also guide the selection of both basis functions and \"state-relevance weights\" that influence quality of the approximation. Experimental results in the domain of queueing network control provide empirical support for the methodology.

This paper considers a tandem queueing network with a Poisson arrival process of incoming calls, two servers, and two infinite orbits by the method of asymptotic analysis. The servers provide services for incoming calls for exponentially distributed random times. Blocked customers at each server join the orbit of that server and retry to enter the server again after an exponentially distributed time. Under the condition of low retrial rates, we prove that the joint stationary distribution of scaled numbers of calls in the orbits weakly converges to a two-variable Normal distribution.

We address the procurement of new components for recyclable products in the context of Kodak's single-use camera. The objective is to find an ordering policy that minimizes the total expected procurement, inventory holding, and lost sales cost. Distinguishing characteristics of the system are the uncertainty and unobservability associated with return flows of used cameras. We model the system as a closed queueing network, develop a heuristic procedure for adaptive estimation and control, and illustrate our methods with disguised data from Kodak. Using this framework, we investigate the effects of various system characteristics such as informational structure, procurement delay, demand rate, and length of the product's life cycle.

Importance sampling is a technique that is commonly used to speed up Monte Carlo simulation of rare events. However, little is known regarding the design of efficient importance sampling algorithms in the context of queueing networks. The standard approach, which simulates the system using an a priori fixed change of measure suggested by large deviation analysis, has been shown to fail in even the simplest network setting (e.g., a two-node tandem network). Exploiting connections between importance sampling, differential games, and classical subsolutions of the corresponding Isaacs equation, we show how to design and analyze simple and efficient dynamic importance sampling schemes for general classes of networks. The models used to illustrate the approach include d-node tandem Jackson networks and a two-node network with feedback, and the rare events studied are those of large queueing backlogs, including total population overflow and the overflow of individual buffers.

We consider the stability of robust scheduling policies for multiclass queueing networks. These are open networks with arbitrary routeing matrix and several disjoint groups of queues in which at most one queue can be served at a time. The arrival and potential service processes and routeing decisions at the queues are independent, stationary, and ergodic. A scheduling policy is called robust if it does not depend on the arrival and service rates nor on the routeing probabilities. A policy is called throughput-optimal if it makes the system stable whenever the parameters are such that the system can be stable. We propose two robust policies: longest-queue scheduling and a new policy called longest-dominating-queue scheduling. We show that longest-queue scheduling is throughput-optimal for two groups of two queues. We also prove the throughput-optimality of longest-dominating-queue scheduling when the network topology is acyclic, for an arbitrary number of groups and queues.

We propose a class of models of random walks in a random environment where an exact solution can be given for a stationary distribution. The environment is cast in terms of a Jackson/Gordon–Newell network although alternative interpretations are possible. The main tool is the detailed balance equations. The difference compared to earlier works is that the position of the random walk influences the transition intensities of the network environment and vice versa, creating strong correlations. The form of the stationary distribution is closely related to the well-known product formula.

This article presents an asset management-oriented multi-criteria methodology for the joint estimation of a mobile equipment fleet size, and the maintenance capacity to be allocated in a productive system. Using a business-centred life-cycle perspective, we propose an integrated analytical model and evaluate it using global cost rate, availability and throughput as performance indicators. The global cost components include: (i) opportunity costs associated with lost production, (ii) vehicle idle time costs, and (iii) maintenance resources idle time costs. This multi-criteria approach allows a balanced scorecard to be built that identifies the main trade-offs in the system. The methodology uses an improved closed network queueing model approach to describe the production and maintenance areas. We test the proposed methodology using an underground mining operation case study. The decision variables are the size of a load-haul-dump fleet and specialized maintenance crew levels. Our model achieves savings of 20.6% in global cost terms with respect to a benchmark case. We also optimize the system to achieve desired targets of vehicle availability and system throughput (based on system utilization). The results show increments of 7.1% in vehicle availability and 13.5% in system throughput with respect to baseline case. For the case studied, these criteria also have a maximum, which allows for further improvement if desired. The results also show the importance of using balanced performance measures in the decision process. A multi-criteria optimization was also performed, showing the Pareto front of considered indicators. We discuss the trade-offs among different criteria, and the implications in finding balanced solutions. The proposed analytical approach is easy to implement and requires low computational effort. It also allows for an easy re-evaluation of resources when the business cycle changes and relevant exogenous factors vary.

Understanding the Fundamentals of Empty-Car Routing in Ridesharing Systems How to efficiently route empty-cars in ridesharing systems? In this paper “Empty-car Routing in Ridesharing Systems,” A. Braverman, J.G. Dai, X. Liu, and L. Ying introduce a novel model based on closed queueing networks and propose an optimization framework to optimize empty-car routing for maximizing system-wide utility functions. We propose a fluid-based optimal routing policy by solving the optimization problem in a large market regime. We establish both process-level and steady-state convergence of the closed queueing network to the fluid-limit and prove the optimal network utility obtained from the fluid-based optimization is an upper bound on the utility in the finite car system for any routing policy under which the closed queueing network has a stationary distribution. This upper bound is achieved asymptotically under the fluid-based optimal routing policy. This paper considers a closed queueing network model of ridesharing systems, such as Didi Chuxing, Lyft, and Uber. We focus on empty-car routing, a mechanism by which we control car flow in the network to optimize system-wide utility functions, for example, the availability of empty cars when a passenger arrives. We establish both process-level and steady-state convergence of the queueing network to a fluid limit in a large market regime where demand for rides and supply of cars tend to infinity and use this limit to study a fluid-based optimization problem. We prove that the optimal network utility obtained from the fluid-based optimization is an upper bound on the utility in the finite car system for any routing policy, both static and dynamic, under which the closed queueing network has a stationary distribution. This upper bound is achieved asymptotically under the fluid-based optimal routing policy. Simulation results with real-world data released by Didi Chuxing demonstrate the benefit of using the fluid-based optimal routing policy compared with various other policies.

We consider a two-dimensional reflecting random walk on the nonnegative integer quadrant. This random walk is assumed to be skip free in the direction to the boundary of the quadrant, but may have unbounded jumps in the opposite direction, which are referred to as upward jumps. We are interested in the tail asymptotic behavior of its stationary distribution, provided it exists. Assuming that the upward jump size distributions have light tails, we find the rough tail asymptotics of the marginal stationary distributions in all directions. This generalizes the corresponding results for the skip-free reflecting random walk in Miyazawa (2009). We exemplify these results for a two-node queueing network with exogenous batch arrivals.

Given an oblique reflection map Γ and functions \\documentclass{aastex} \\usepackage{amsbsy} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{bm} \\usepackage{mathrsfs} \\usepackage{pifont} \\usepackage{stmaryrd} \\usepackage{textcomp} \\usepackage{portland,xspace} \\usepackage{amsmath,amsxtra} \\pagestyle{empty} \\DeclareMathSizes{10}{9}{7}{6} \\begin{document} $\\psi, \\chi \\in \\mathcal{D}_{\\lim}$ \\end{document} (the space of K -valued functions that have finite left and right limits at every point), the directional derivative \\documentclass{aastex} \\usepackage{amsbsy} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{bm} \\usepackage{mathrsfs} \\usepackage{pifont} \\usepackage{stmaryrd} \\usepackage{textcomp} \\usepackage{portland,xspace} \\usepackage{amsmath,amsxtra} \\pagestyle{empty} \\DeclareMathSizes{10}{9}{7}{6} \\begin{document} $\\nabla_\\chi \\Gamma(\\psi)$ \\end{document} of Γ along χ, evaluated at ψ, is defined to be the pointwise limit, as \\documentclass{aastex} \\usepackage{amsbsy} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{bm} \\usepackage{mathrsfs} \\usepackage{pifont} \\usepackage{stmaryrd} \\usepackage{textcomp} \\usepackage{portland,xspace} \\usepackage{amsmath,amsxtra} \\pagestyle{empty} \\DeclareMathSizes{10}{9}{7}{6} \\begin{document} $\\varepsilon \\downarrow 0$ \\end{document} , of the family of functions \\documentclass{aastex} \\usepackage{amsbsy} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{bm} \\usepackage{mathrsfs} \\usepackage{pifont} \\usepackage{stmaryrd} \\usepackage{textcomp} \\usepackage{portland,xspace} \\usepackage{amsmath,amsxtra} \\pagestyle{empty} \\DeclareMathSizes{10}{9}{7}{6} \\begin{document} $\\nabla_\\chi^\\epsilon \\Gamma (\\psi) \\doteq \\epsilon^{-1} [\\Gamma (\\psi + \\epsilon\\chi) - \\Gamma (\\psi)]$ \\end{document} . Directional derivatives are shown to exist and lie in \\documentclass{aastex} \\usepackage{amsbsy} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{bm} \\usepackage{mathrsfs} \\usepackage{pifont} \\usepackage{stmaryrd} \\usepackage{textcomp} \\usepackage{portland,xspace} \\usepackage{amsmath,amsxtra} \\pagestyle{empty} \\DeclareMathSizes{10}{9}{7}{6} \\begin{document} $\\mathcal{D}_{\\lim}$ \\end{document} for oblique reflection maps associated with reflection matrices of the so-called Harrison-Reiman class. When ψ and χ are continuous, the convergence of \\documentclass{aastex} \\usepackage{amsbsy} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{bm} \\usepackage{mathrsfs} \\usepackage{pifont} \\usepackage{stmaryrd} \\usepackage{textcomp} \\usepackage{portland,xspace} \\usepackage{amsmath,amsxtra} \\pagestyle{empty} \\DeclareMathSizes{10}{9}{7}{6} \\begin{document} $\\nabla_\\chi^{\\epsilon} \\Gamma (\\psi)$ \\end{document} to \\documentclass{aastex} \\usepackage{amsbsy} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{bm} \\usepackage{mathrsfs} \\usepackage{pifont} \\usepackage{stmaryrd} \\usepackage{textcomp} \\usepackage{portland,xspace} \\usepackage{amsmath,amsxtra} \\pagestyle{empty} \\DeclareMathSizes{10}{9}{7}{6} \\begin{document} $\\nabla_\\chi \\Gamma (\\psi)$ \\end{document} is shown to be uniform on compact subsets of continuity points of the limit \\documentclass{aastex} \\usepackage{amsbsy} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{bm} \\usepackage{mathrsfs} \\usepackage{pifont} \\usepackage{stmaryrd} \\usepackage{textcomp} \\usepackage{portland,xspace} \\usepackage{amsmath,amsxtra} \\pagestyle{empty} \\DeclareMathSizes{10}{9}{7}{6} \\begin{document} $\\nabla_\\chi \\Gamma (\\psi)$ \\end{document} , and the derivative \\documentclass{aastex} \\usepackage{amsbsy} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{bm} \\usepackage{mathrsfs} \\usepackage{pifont} \\usepackage{stmaryrd} \\usepackage{textcomp} \\usepackage{portland,xspace} \\usepackage{amsmath,amsxtra} \\pagestyle{empty} \\DeclareMathSizes{10}{9}{7}{6} \\begin{document} $\\nabla_\\chi \\Gamma (\\psi)$ \\end{document} is shown to have an autonomous characterization as the unique fixed point of an associated map. Directional derivatives arise as functional central limit approximations to time-inhomogeneous queueing networks. In this case ψ and χ correspond, respectively, to the functional strong law of large numbers and functional central limits of the so-called netput process. In this work it is also shown how the various types of discontinuities of the derivative \\documentclass{aastex} \\usepackage{amsbsy} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{bm} \\usepackage{mathrsfs} \\usepackage{pifont} \\usepackage{stmaryrd} \\usepackage{textcomp} \\usepackage{portland,xspace} \\usepackage{amsmath,amsxtra} \\pagestyle{empty} \\DeclareMathSizes{10}{9}{7}{6} \\begin{document} $\\nabla_\\chi \\Gamma (\\psi)$ \\end{document} are related to the reflection matrix and properties of the function Γ(ψ). In the queueing network context, this describes the influence of the topology of the network and the states (of underloading, overloading, or criticality) of the various queues in the network on the discontinuities of the directional derivative. Directional derivatives have also been found useful for identifying optimal controls for fluid approximations of time-inhomogoeneous queueing networks and are also of relevance to the study of differentiability of stochastic flows of obliquely reflected Brownian motions.