Search

Downtime of industrial assets such as wind turbines and medical imaging devices comes at a sharp cost. To avoid such downtime costs, companies seek to initiate maintenance just before failure. Unfortunately, this is challenging for the following two reasons: On the one hand, because asset failures are notoriously difficult to predict, even in the presence of real-time monitoring devices which signal early degradation. On the other hand, because the available resources to serve a network of geographically dispersed assets are typically limited. In this paper, we propose a novel model referred to as the dynamic traveling maintainer problem with alerts that incorporates these two challenges and we provide three solution approaches on how to dispatch the limited resources. Namely, we propose: (i) Greedy heuristic approaches that rank assets on urgency, proximity and economic risk; (ii) A novel traveling maintainer heuristic approach that optimizes short-term costs; and (iii) A deep reinforcement learning (DRL) approach that optimizes long-term costs. Each approach has different requirements concerning the available alert information. Experiments with small asset networks show that all methods can approximate the optimal policy when given access to complete condition information. For larger networks, the proposed methods yield competitive policies, with DRL consistently achieving the lowest costs.

International audience; It has been recently advocated that in large communication systems it is beneficial both for the users and for the network as a whole to store content closer to users. One particular implementation of such an approach is to co-locate caches with wireless base stations. In this paper we study geographically distributed caching of a fixed collection of files. We model cache placement with the help of stochastic geometry and optimize the allocation of storage capacity among files in order to minimize the cache miss probability. We consider both per cache capacity constraints as well as an average capacity constraint over all caches. The case of per cache capacity constraints can be efficiently solved using dynamic programming, whereas the case of the average constraint leads to a convex optimization problem. We demonstrate that the average constraint leads to significantly smaller cache miss probability. Finally, we suggest a simple LRU-based policy for geographically distributed caching and show that its performance is close to the optimal.

We investigate the tail asymptotics of the response time distribution for the cancel-on-start (c.o.s.) and cancel-on-completion (c.o.c.) variants of redundancy-d scheduling and the fork–join model with heavy-tailed job sizes. We present bounds, which only differ in the pre-factor, for the tail probability of the response time in the case of the first-come first-served discipline. For the c.o.s. variant, we restrict ourselves to redundancy-d scheduling, which is a special case of the fork–join model. In particular, for regularly varying job sizes with tail index-$$\nu $$ ν the tail index of the response time for the c.o.s. variant of redundancy-d equals -$$\min \{d_{\mathrm {cap}}(\nu -1),\nu \}$$ min { d cap ( ν - 1 ) , ν } , where $$d_{\mathrm {cap}} = \min \{d,N-k\}$$ d cap = min { d , N - k } , N is the number of servers and k is the integer part of the load. This result indicates that for $$d_{\mathrm {cap}} < \frac{\nu }{\nu -1}$$ d cap < ν ν - 1 the waiting time component is dominant, whereas for $$d_{\mathrm {cap}} > \frac{\nu }{\nu -1}$$ d cap > ν ν - 1 the job size component is dominant. Thus, having $$d = \lceil \min \{\frac{\nu }{\nu -1},N-k\} \rceil $$ d = ⌈ min { ν ν - 1 , N - k } ⌉ replicas is sufficient to achieve the optimal asymptotic tail behavior of the response time. For the c.o.c. variant of the fork–join ($$n_{\mathrm {F}},n_{\mathrm {J}}$$ n F , n J ) model, the tail index of the response time, under some assumptions on the load, equals $$1-\nu $$ 1 - ν and $$1-(n_{\mathrm {F}}+1-n_{\mathrm {J}})\nu $$ 1 - ( n F + 1 - n J ) ν , for identical and i.i.d. replicas, respectively; here, the waiting time component is always dominant.

International audience; In the present paper we address two open problems concerning polling systems, viz., queueing systems consisting of multiple queues attended by a single server that visits the queues one at a time. The first open problem deals with a system consisting of two queues, one of which has gated service, while the other receives 1-limited service. The second open problem concerns polling systems with general (renewal) arrivals and deterministic switch-over times that become infinitely large. We discuss related, known results for both problems, and the difficulties encountered when trying to solve them.

We consider a Lévy process Y(t) that is not continuously observed, but rather inspected at Poisson( $\omega$ ) moments only, over an exponentially distributed time $T_\beta$ with parameter $\beta$ . The focus lies on the analysis of the distribution of the running maximum at such inspection moments up to $T_\beta$ , denoted by $Y_{\beta,\omega}$ . Our main result is a decomposition: we derive a remarkable distributional equality that contains $Y_{\beta,\omega}$ as well as the running maximum process $\bar Y(t)$ at the exponentially distributed times $T_\beta$ and $T_{\beta+\omega}$ . Concretely, $\overline{Y}(T_\beta)$ can be written as the sum of two independent random variables that are distributed as $Y_{\beta,\omega}$ and $\overline{Y}(T_{\beta+\omega})$ . The distribution of $Y_{\beta,\omega}$ can be identified more explicitly in the two special cases of a spectrally positive and a spectrally negative Lévy process. As an illustrative example of the potential of our results, we show how to determine the asymptotic behavior of the bankruptcy probability in the Cramér–Lundberg insurance risk model.

We consider an (R, Q) inventory model with two types of orders, normal orders and emergency orders, which are issued at different inventory levels. These orders are delivered after exponentially distributed lead times. In between deliveries, the inventory level decreases in a state-dependent way, according to a release rate function $\alpha({\cdot})$ . This function represents the fluid demand rate; it could be controlled by a system manager via price adaptations. We determine the mean number of downcrossings $\theta(x)$ of any level x in one regenerative cycle, and use it to obtain the steady-state density f (x) of the inventory level. We also derive the rates of occurrence of normal deliveries and of emergency deliveries, and the steady-state probability of having zero inventory.

We consider a stochastic EOQ-type model, with demand operating in a two-state random environment. This environment alternates between exponentially distributed periods of high demand and generally distributed periods of low demand. The inventory level starts at some level q, and decreases according to different compound Poisson processes during the periods of high demand and of low demand. Refilling of the inventory level to level q is required when level 0 is hit or when an expiration date is reached, whichever comes first. If such an event occurs during a high demand period, an order is instantaneously placed; otherwise, ordering is postponed until the beginning of the next high demand period. We determine various performance measures of interest, like the distribution of the inventory level at time t and of the inventory demand up to time t, the distribution of the time until refilling is required, the expected time between two refillings, the expected amount of discarded material and the expected total amount of material held in between two refillings, and the expected values of various kinds of shortages. For a given cost/revenue structure, we can thus determine the long-run average profit.

International audience; Discrete-time discrete-state finite Markov chains are versatile mathematical models for a wide range of real-life stochastic processes. One of most common tasks in studies of Markov chains is computation of the stationary distribution. Without loss of generality, and drawing our motivation from applications to large networks, we interpret this problem as one of computing the stationary distribution of a random walk on a graph. We propose a new controlled, easily distributed algorithm for this task, briefly summarized as follows: at the beginning, each node receives a fixed amount of cash (positive or negative), and at each iteration, some nodes receive 'green light' to distribute their wealth or debt proportionally to the transition probabilities of the Markov chain; the stationary probability of a node is computed as a ratio of the cash distributed by this node to the total cash distributed by all nodes together. Our method includes as special cases a wide range of known, very different, and previously disconnected methods including power iterations, Gauss-Southwell, and online distributed algorithms. We prove exponential convergence of our method, demonstrate its high efficiency, and derive scheduling strategies for the green-light, that achieve convergence rate faster than state-of-the-art algorithms.

This paper analyzes various stochastic recursions that arise in queueing and insurance risk models with a ‘semi-linear’ dependence structure. For example, an interarrival time depends on the workload, or the capital, immediately after the previous arrival; or the service time of a customer depends on her waiting time. In each case, we derive and solve a fixed-point equation for the Laplace–Stieltjes transform of a key performance measure of the model, like waiting time or ruin time.

We present a stochastic growth-collapse model for the capital process of a peer-to-peer lending platform. New lenders arrive according to a compound Poisson-type process with a state-dependent intensity function; the growth of the lending capital is from time to time interrupted by partial collapses whose arrival intensities and sizes are also state-dependent. In our model the capital level administered via the platform is the crucial quantity for the generated profit, because the brokerage fee is a fixed (small) fraction of it. Therefore we study its steady-state probability distribution as a key performance measure. In the case of exponentially distributed upward jumps we derive an explicit expression for its probability density, for quite general arrival rates of upward and downward jumps and for certain collapse mechanisms. In the case of generally distributed upward jumps, we derive an explicit expression for the Laplace transform of the steady-state cash level density in various special cases. An alternative model featuring up and down periods and a shot noise mechanism for the downward evolution is also analyzed in steady state.

We consider caching in cellular networks in which each base station is equipped with a cache that can store a limited number of files. The popularity of the files is known and the goal is to place files in the caches such that the probability that a user at an arbitrary location in the plane will find the file that she requires in one of the covering caches is maximized. We develop distributed asynchronous algorithms for deciding which contents to store in which cache. Such cooperative algorithms require communication only between caches with overlapping coverage areas and can operate in asynchronous manner. The development of the algorithms is principally based on an observation that the problem can be viewed as a potential game. Our basic algorithm is derived from the best response dynamics. We demonstrate that the complexity of each best response step is independent of the number of files, linear in the cache capacity and linear in the maximum number of base stations that cover a certain area. Then, we show that the overall algorithm complexity for a discrete cache placement is polynomial in both network size and catalog size. In practical examples, the algorithm converges in just a few iterations. Also, in most cases of interest, the basic algorithm finds the best Nash equilibrium corresponding to the global optimum. We provide two extensions of our basic algorithm based on stochastic and deterministic simulated annealing which find the global optimum. Finally, we demonstrate the hit probability evolution on real and synthetic networks numerically and show that our distributed caching algorithm performs significantly better than storing the most popular content, probabilistic content placement policy and Multi-LRU caching policies., 24 pages, 9 figures, presented at SIGMETRICS'17

Mass-scale red blood cell genotyping of donors and transfusion recipients increases the availability of extended antigen matched red blood cell units. Therefore, a new mathematical framework is developed that can be applied for general blood groups (i.e., beyond the ABO, RhD blood groups). It determines which red blood cell units should be issued from inventory, such that requests from hospitals can be satisfied with antigen compatible red blood cell units, shortages for future requests are avoided, and outdating is prevented. The optimization model consists of two steps: a binary vector representation for general blood groups and the formulation of the inventory allocation problem as a minimum cost flow problem. The potential practical performance of the optimization model is evaluated by iterative simulations, based on historical data on supply and demand of red blood cell units in the Netherlands. When including the fourteen clinically most relevant antigens, more than 90% of all requests can be satisfied with antigen identical red blood cell units. Shortages and outdating can be kept restricted and could even be reduced to virtually zero, when only the ABO, RhD blood groups are considered.

The robustness of the t linear mixed model (tLMM) has been proved and exploited in many applications. Various publications emerged with the aim of proving superiority with respect to traditional linear mixed models, extending to more general settings and proposing more efficient estimation methods. However, little attention has been paid to the mathematical properties of the model itself and to the evaluation of the proposed estimation methods. In this paper we perform an in-depth analysis of the tLMM, evaluating a direct maximum likelihood estimation method via an intensive simulation study and investigating some identifiability properties. The theoretical findings are illustrated through an application to a dataset collected from a sleep trial.

We consider a large-scale service system where incoming tasks have to be instantaneously dispatched to one out of many parallel server pools. The user-perceived performance degrades with the number of concurrent tasks and the dispatcher aims at maximizing the overall quality-of-service by balancing the load through a simple threshold policy. We demonstrate that such a policy is optimal on the fluid and diffusion scales, while only involving a small communication overhead, which is crucial for large-scale deployments. In order to set the threshold optimally, it is important, however, to learn the load of the system, which may be unknown. For that purpose, we design a control rule for tuning the threshold in an online manner. We derive conditions which guarantee that this adaptive threshold settles at the optimal value, along with estimates for the time until this happens. In addition, we provide numerical experiments which support the theoretical results and further indicate that our policy copes effectively with time-varying demand patterns., Comment: 51 pages, 6 figures

Random intersection graphs model networks with communities, assuming an underlying bipartite structure of groups and individuals, where these groups may overlap. Group memberships are generated through the bipartite configuration model. Conditionally on the group memberships, the classical random intersection graph is obtained by connecting individuals when they are together in at least one group. We generalize this definition, allowing for arbitrary community structures within the groups. In our new model, groups might overlap and they have their own internal structure described by a graph, the classical setting corresponding to groups being complete graphs. Our model turns out to be tractable. We analyze the overlapping structure of the communities, derive the asymptotic degree distribution and the local clustering coefficient. These proofs rely on local weak convergence, which also implies that subgraph counts converge. We further exploit the connection to the bipartite configuration model, for which we also prove local weak convergence, and which is interesting in its own right., Comment: 34 pages, 12 figures

In this publication, the modelisation of an air bubble as inclusion in a droplet is treated from scalar theory point of view (Fresnel’s theory). The elaborated model is compared with Lorenz–Mie scattering theory and with an experimental results. Circle polynomials and scaled pupil function are the background of this work to take into account the critical angle effect that arises at a transition from a higher index to a lower index medium. Keywords: Digital in-line holography, bubble inclusions, nanoparticles

International audience; We consider storage devices located in the plane according to a general point process and specialize the results for the homogeneous Poisson process. A large data file is stored at the storage devices, which have limited storage capabilities. Hence, they can only store parts of the data. Clients can contact the storage devices to retrieve the data.We compare the expected cost of obtaining the complete data under uncoded as well as coded data allocation strategies. It is shown that for the general class of cost measures where the cost of retrieving data is increasing with the distance between client and storage devices, coded allocation outperforms uncoded allocation. The improvement offered by coding is quantified for two more specific classes of performance measures. Finally, our results are validated by computing the costs of the allocation strategies for the case that storage devices coincide with currently deployed mobile base stations.

The aim of this paper is to analyze a general class of storage processes, in which the rate at which the storage level increases or decreases is assumed to be an affine function of the current storage level, and, in addition, both upward and downward jumps are allowed. To do so, we first focus on a related insurance risk model, for which we determine the ruin probability at an exponentially distributed epoch jointly with the corresponding undershoot and overshoot, given that the capital level at time 0 is exponentially distributed as well. The obtained results for this insurance risk model can be translated in terms of two types of storage models, in one of those two cases by exploiting a duality relation. Many well-studied models are shown to be special cases of our insurance risk and storage models. We conclude by showing how the exponentiality assumptions can be greatly relaxed.

International audience; Motivated by dynamic speed scaling, which enables a balance between performance and energy consumption, we got interested in queues in which the server can work at different service speeds and in which the speed of the server can only be changed at arrival instants of an external observer. In the past several works dealt with models in which these type of service speed adaptations occurred. Bekker, Boxma and Resing (2008) studied an M/M/1 queue with a two-stage service rule. Whenever the amount of work in the system is below a threshold the server wants to work at low service speed, otherwise the server wants to work at high service speed. However, speed adaptations can only occur at Poisson instants.The amount of work in the system could either be measured by the number of customers or by the total workload in the system.Later on, the work was extended to the $M/G/1$ workload process, and to Levy processes in Bekker, Boxma and Resing (2009).Here we look at the model in which the server can not only work at two different service speeds but at infinitely many server speeds. When there are $j$ customers in the system, the server wants to work at speed $j$.

In this paper, we study the maximum waiting time $\max_{i\leq N}W_i(\cdot)$ in an $N$-server fork-join queue with heavy-tailed services as $N\to\infty$. The service times are the product of two random variables. One random variable has a regularly varying tail probability and is the same among all $N$ servers, and one random variable is Weibull distributed and is independent and identically distributed among all servers. This setup has the physical interpretation that if a job has a large size, then all the subtasks have large sizes, with some variability described by the Weibull-distributed part. We prove that after a temporal and spatial scaling, the maximum waiting time process converges in $D[0,T]$ to the supremum of an extremal process with negative drift. The temporal and spatial scaling are of order $\tilde{L}(b_N)b_N^{\frac{\beta}{(\beta-1)}}$, where $\beta$ is the shape parameter in the regularly varying distribution, $\tilde{L}(x)$ is a slowly varying function, and $(b_N,N\geq 1)$ is a sequence for which holds that $\max_{i\leq N}A_i/b_N\overset{\mathbb{P}}{\longrightarrow}1$, as $N\to\infty$, where $A_i$ are i.i.d.\ Weibull-distributed random variables. Finally, we prove steady-state convergence.

In this paper, we study a functional equation for generating functions of the form $$f(z) = g(z) \sum _{i=1}^M p_i f(\alpha _i(z)) + K(z)$$ f ( z ) = g ( z ) ∑ i = 1 M p i f ( α i ( z ) ) + K ( z ) , viz. a recursion with multiple recursive terms. We derive and analyze the solution of this equation for the case that the $$\alpha _i(z)$$ α i ( z ) are commutative contraction mappings. The results are applied to a wide range of queueing, autoregressive and branching processes.

We develop power series approximations for a discrete-time queueing system with two parallel queues and one processor. If both queues are nonempty, a customer of queue 1 is served with probability ß, and a customer of queue 2 is served with probability 1-ß. If one of the queues is empty, a customer of the other queue is served with probability 1. We first describe the generating function U(z_1,z_2) of the stationary queue lengths in terms of a functional equation, and show how to solve this using the theory of boundary value problems. Then, we propose to use the same functional equation to obtain a power series for U(z_1,z_2) in ß. The first coefficient of this power series corresponds to the priority case ß=0, which allows for an explicit solution. All higher coefficients are expressed in terms of the priority case. Accurate approximations for the mean stationary queue lengths are obtained from combining truncated power series and Padé approximation. Keywords: Generalized processor sharing - Power series approximation - Discrete time - Two-dimensional random walk.

This paper presents an analysis of the stochastic recursion $$W_{i+1} = [V_iW_i+Y_i]^+$$ W i + 1 = [ V i W i + Y i ] + that can be interpreted as an autoregressive process of order 1, reflected at 0. We start our exposition by a discussion of the model’s stability condition. Writing $$Y_i=B_i-A_i$$ Y i = B i - A i , for independent sequences of nonnegative i.i.d. random variables $$\{A_i\}_{i\in {\mathbb N}_0}$$ { A i } i ∈ N 0 and $$\{B_i\}_{i\in {\mathbb N}_0}$$ { B i } i ∈ N 0 , and assuming $$\{V_i\}_{i\in {\mathbb N}_0}$$ { V i } i ∈ N 0 is an i.i.d. sequence as well (independent of $$\{A_i\}_{i\in {\mathbb N}_0}$$ { A i } i ∈ N 0 and $$\{B_i\}_{i\in {\mathbb N}_0}$$ { B i } i ∈ N 0 ), we then consider three special cases (i) $$V_i$$ V i equals a positive value a with certain probability $$p\in (0,1)$$ p ∈ ( 0 , 1 ) and is negative otherwise, and both $$A_i$$ A i and $$B_i$$ B i have a rational LST, (ii) $$V_i$$ V i attains negative values only and $$B_i$$ B i has a rational LST, (iii) $$V_i$$ V i is uniformly distributed on [0, 1], and $$A_i$$ A i is exponentially distributed. In all three cases, we derive transient and stationary results, where the transient results are in terms of the transform at a geometrically distributed epoch.

Order-independent (OI) queues, introduced by Berezner, Kriel, and Krzesinski in 1995, expanded the family of multi-class queues that are known to have a product-form stationary distribution by allowing for intricate class-dependent service rates. This paper further broadens this family by introducing pass-and-swap (P&S) queues, an extension of OI queues where, upon a service completion, the customer that completes service is not necessarily the one that leaves the system. More precisely, we supplement the OI queue model with an undirected graph on the customer classes, which we call a swapping graph, such that there is an edge between two classes if customers of these classes can be swapped with one another. When a customer completes service, it passes over customers in the remainder of the queue until it finds a customer it can swap positions with, that is, a customer whose class is a neighbor in the graph. In its turn, the customer that is ejected from its position takes the position of the next customer it can be swapped with, and so on. This is repeated until a customer can no longer find another customer to be swapped with; this customer is the one that leaves the queue. After proving that P&S queues have a product-form stationary distribution, we derive a necessary and sufficient stability condition for (open networks of) P&S queues that also applies to OI queues. We then study irreducibility properties of closed networks of P&S queues and derive the corresponding product-form stationary distribution. Lastly, we demonstrate that closed networks of P&S queues can be applied to describe the dynamics of new and existing load-distribution and scheduling protocols in clusters of machines in which jobs have assignment constraints., 44 pages, 15 figures

Motivated by the trade-off issue between delay performance and energy consumption in modern computer and communication systems, we consider a single-server queue with phase-type service requirements and with the following two special features: Firstly, the service speed is a piecewise constant function of the workload. Secondly, the server switches off when the system becomes empty, only to be activated again when the workload reaches a certain threshold. For this system, we obtain the steady-state workload distribution and its moments of any order. We use this result to choose the activation threshold such that a certain cost function, involving processing costs, activation costs and mean workload, is minimized.

We consider an acyclic network of single-server queues with heterogeneous processing rates. It is assumed that each queue is fed by the superposition of a large number of i.i.d. Gaussian processes with stationary increments and positive drifts, which can be correlated across different queues. The flow of work departing from each server is split deterministically and routed to its neighbors according to a fixed routing matrix, with a fraction of it leaving the network altogether. We study the exponential decay rate of the probability that the steady-state queue length at any given node in the network is above any fixed threshold, also referred to as the ‘overflow probability’. In particular, we first leverage Schilder’s sample-path large deviations theorem to obtain a general lower bound for the limit of this exponential decay rate, as the number of Gaussian processes goes to infinity. Then, we show that this lower bound is tight under additional technical conditions. Finally, we show that if the input processes to the different queues are nonnegatively correlated, non-short-range dependent fractional Brownian motions, and if the processing rates are large enough, then the asymptotic exponential decay rates of the queues coincide with the ones of isolated queues with appropriate Gaussian inputs.

We prove the strong Feller property and exponential mixing for 3D stochastic Navier-Stokes equation driven by mildly degenerate noises (i.e. all but finitely many Fourier modes are forced) via Kolmogorov equation approach., Comment: 31 pp. Corrected several errors in the original version

We study the distribution of confirmation times of Bitcoin transactions, conditional on the size of the current memory pool. We argue that the time until a Bitcoin transaction is confirmed resembles the time to ruin in a corresponding Cramer-Lundberg process. This well-studied model gives mathematical insights in the mempool behaviour over time. Specifically, for situations where one chooses a fee, such that the total size of incoming transactions with higher fee is close to the total size of transactions leaving the mempool (heavy traffic), a diffusion approximation leads to an inverse Gaussian distribution for the confirmation times. The results of this paper are particularly interesting for users that want to make a Bitcoin transaction during heavy-traffic situations, as evaluation of the well-known inverse Gaussian distribution is computationally straightforward.

In this paper, we present a method to forecast the spread of SARS-CoV-2 across regions with a focus on the role of mobility. Mobility has previously been shown to play a significant role in the spread of the virus, particularly between regions. Here, we investigate under which epidemiological circumstances incorporating mobility into transmission models yields improvements in the accuracy of forecasting, where we take the situation in the Netherlands during and after the first wave of transmission in 2020 as a case study. We assess the quality of forecasting on the detailed level of municipalities, instead of on a nation-wide level. To model transmissions, we use a simple mobility-enhanced SEIR compartmental model with subpopulations corresponding to the Dutch municipalities. We use commuter information to quantify mobility, and develop a method based on maximum likelihood estimation to determine the other relevant parameters. We show that taking inter-regional mobility into account generally leads to an improvement in forecast quality. However, at times when policies are in place that aim to reduce contacts or travel, this improvement is very small., 22 pages, 13 figures

We consider a heterogeneous distributed service system, consisting of $n$ servers with unknown and possibly different processing rates. Jobs with unit mean and independent processing times arrive as a renewal process of rate $\lambda n$, with $0, Comment: arXiv admin note: text overlap with arXiv:1807.02882

Emden-Fowler type equations are nonlinear differential equations that appear in many fields such as mathematical physics, astrophysics and chemistry. In this paper, we perform an asymptotic analysis of a specific Emden-Fowler type equation that emerges in a queuing theory context as an approximation of voltages under a well-known power flow model. Thus, we place Emden-Fowler type equations in the context of electrical engineering. We derive properties of the continuous solution of this specific Emden-Fowler type equation and study the asymptotic behavior of its discrete analog. We conclude that the discrete analog has the same asymptotic behavior as the classical continuous Emden-Fowler type equation that we consider., 33 pages, 3 figures

We characterize the impact of scheduling policies on the mean response time in nested systems with cancel-on-complete redundancy. We consider not only redundancy-oblivious policies, such as FCFS and ROS, but also redundancy-aware policies of the form $\Pi_1-\Pi_2$, where $\Pi_1$ discriminates among job classes (e.g., least-redundant-first (LRF), most-redundant-first (MRF)) and $\Pi_2$ discriminates among jobs of the same class. Assuming that jobs have independent and identically distributed (i.i.d.) copies, we prove the following: (i) When jobs have exponential service times, LRF policies outperform any other policy. (ii) When service times are New-Worse-than-Used, MRF-FCFS outperforms LRF-FCFS as the variability of the service time grows infinitely large. (iii) When service times are New-Better-than-Used, LRF-ROS (resp. MRF-ROS) outperforms LRF-FCFS (resp. MRF-FCFS) in a two-server system. Statement (iii) also holds when job sizes follow a general distribution and have identical copies (all the copies of a job have the same size). Moreover, we show via simulation that, for a large class of redundancy systems, redundancy-aware policies can considerably improve the mean response time compared to redundancy-oblivious policies. We also explore the effect of redundancy on the stability region.

We develop and analyze a measure-valued fluid model keeping track of parking and charging requirements of electric vehicles in a local distribution grid. We show how this model arises as an accumulation point of an appropriately scaled sequence of stochastic network models. The invariant point of the fluid model encodes the electrical characteristics of the network and the stochastic behavior of its users, and it is characterized, when it exists, by the solution of a so-called Alternating Current Optimal Power Flow (ACOPF) problem., 33 pages

In this paper, we study the critical behavior of percolation on a configuration model with degree distribution satisfying an infinite second-moment condition, which includes power-law degrees with exponent $\tau \in (2,3)$. It is well known that, in this regime, many canonical random graph models, such as the configuration model, are robust in the sense that the giant component is not destroyed when the percolation probability stays bounded away from zero. Thus, the critical behavior is observed when the percolation probability tends to zero with the network size, despite of the fact that the average degree remains bounded. In this paper, we initiate the study of critical random graphs in the infinite second-moment regime by identifying the critical window for the configuration model. We prove scaling limits for component sizes and surplus edges, and show that the maximum diameter the critical components is of order $\log n$, which contrasts with the previous universality classes arising in the literature. This introduces a third and novel universality class for the critical behavior of percolation on random networks, that is not covered by the multiplicative coalescent framework due to Aldous and Limic (1998). We also prove concentration of the component sizes outside the critical window, and that a unique, complex giant component emerges after the critical window. This completes the picture for the percolation phase transition on the configuration model., Comment: 43 pages, Proof of continuity of the largest excursion is updated

This paper introduces non-cooperative games on a network of single server queues with fixed routes. A player has a set of routes available and has to decide which route(s) to use for its customers. Each player’s goal is to minimize the expected sojourn time of its customers. We consider two cases: a continuous strategy space, where each player is allowed to divide its customers over multiple routes, and a discrete strategy space, where each player selects a single route for all its customers. For the continuous strategy space, we show that a unique pure-strategy Nash equilibrium exists that can be found using a best-response algorithm. For the discrete strategy space, we show that the game has a Nash equilibrium in mixed strategies, but need not have a pure-strategy Nash equilibrium. We show the existence of pure-strategy Nash equilibria for four subclasses: (i) N-player games with equal arrival rates for the players, (ii) 2-player games with identical service rates for all nodes, (iii) 2-player games on a $$2\times 2$$ 2 × 2 -grid, and (iv) 2-player games on an $$A\times B$$ A × B -grid with small differences in the service rates.

We consider a Markov Chain in which the state space is partitioned into sets where both transitions within sets and between sets have a special structure. Transitions within each set constitute a finite level dependent quasi-birth-and-death-process (LDQBD), and transitions between sets are restricted to six types of transitions. These latter types are needed to preserve the sets structure in the reduction step of our algorithm. Specifically, we present a successive censoring algorithm, based on matrix analytic methods, to obtain the stationary distribution of this system of connected LDQBD-processes.

Light enables us to see and perceive our environment but it also initiates effects beyond vision, such as alertness. Literature describes that at least six factors are relevant for initiating effects beyond vision. The exact relationship between these factors and alertness is not yet fully understood. In the current field study, personal lighting conditions of 62 Dutch office workers (aged 49.7 ± 11.4 years) were continuously measured and simultaneously self-reported activities and locations during the day were gathered via diaries. Each office worker participated 10 working days in spring 2017. Personal lighting conditions were interpreted based on four of the six factors (light quantity, spectrum, timing, and duration of light exposure). Large individual differences were found for the daily luminous exposures, illuminances, correlated colour temperatures, and irradiances measured with the blue sensor area of the dosimeter. The average illuminance (over all participants and all days) over the course of the day peaked three times. The analysis of the duration of light exposure demonstrated that the participants were on average only exposed to an illuminance above 1000 lx for 72 minutes per day. The interpretation of personal lighting conditions based on the four factors provides essential information since all of these factors may be relevant for initiating effects beyond vision. The findings in the current paper give first in-depth insight in the possibilities to interpret personal lighting conditions of office workers.

We consider a queue to which only a finite pool of $n$ customers can arrive, at times depending on their service requirement. A customer with stochastic service requirement $S$ arrives to the queue after an exponentially distributed time with mean $S^{-\alpha}$ for some $\alpha\in[0,1]$; so larger service requirements trigger customers to join earlier. This finite-pool queue interpolates between two previously studied cases: $\alpha = 0$ gives the so-called $\Delta_{(i)}/G/1$ queue and $\alpha = 1$ is closely related to the exploration process for inhomogeneous random graphs. We consider the asymptotic regime in which the pool size $n$ grows to infinity and establish that the scaled queue-length process converges to a diffusion process with a negative quadratic drift. We leverage this asymptotic result to characterize the head start that is needed to create a long period of activity. We also describe how this first busy period of the queue gives rise to a critically connected random forest., Comment: 30 pages, 2 figures

This paper considers cluster detection in Block Markov Chains (BMCs). These Markov chains are characterized by a block structure in their transition matrix. More precisely, the $n$ possible states are divided into a finite number of $K$ groups or clusters, such that states in the same cluster exhibit the same transition rates to other states. One observes a trajectory of the Markov chain, and the objective is to recover, from this observation only, the (initially unknown) clusters. In this paper we devise a clustering procedure that accurately, efficiently, and provably detects the clusters. We first derive a fundamental information-theoretical lower bound on the detection error rate satisfied under any clustering algorithm. This bound identifies the parameters of the BMC, and trajectory lengths, for which it is possible to accurately detect the clusters. We next develop two clustering algorithms that can together accurately recover the cluster structure from the shortest possible trajectories, whenever the parameters allow detection. These algorithms thus reach the fundamental detectability limit, and are optimal in that sense., 73 pages, 18 plots, second revision

We consider networks where each node represents a server with a queue. An active node deactivates at unit rate. An inactive node activates at a rate that depends on its queue length, provided none of its neighbors is active. For complete bipartite networks, in the limit as the queues become large, we compute the average transition time between the two states where one half of the network is active and the other half is inactive. We show that the law of the transition time divided by its mean exhibits a trichotomy, depending on the activation rate functions., 32 pages

Respiratory tract infection with pneumoviruses (PVs) and paramyxoviruses (PMVs) are increasingly associated with chronic lung allograft dysfunction (CLAD) in lung transplant recipients (LTRs). Ribavirin may be a treatment option but its effectiveness is unclear, especially with respect to infection severity. We retrospectively analyzed 10 years of PV/PMV infections in LTRs. The main end points were forced expiratory volume in 1 second (FEV1) at 3 and 6 months postinfection, expressed as a percentage of pre‐infection FEV1 and incidence of new or progressed CLAD 6 months postinfection. A total of 139 infections were included: 88 severe infections (63%) (defined as >10% FEV1 loss at infection) and 51 mild infections (37%) (≤10% FEV1 loss). Overall postinfection CLAD incidence was 20%. Associations were estimated on postinfection FEV1 for ribavirin vs no ribavirin (+13.2% [95% CI: 7.79; 18.67]) and severe vs mild infection (−11.1% [95% CI: −14.76; −7.37]). Factors associated with CLAD incidence at 6 months were ribavirin treatment (odds ratio (OR [95% CI]) 0.24 [0.10; 0.59]), severe infection (OR [95% CI] 4.63 [1.66; 12.88]), and mycophenolate mofetil use (OR [95% CI] 0.38 [0.14; 0.97]). These data provide valuable information about the outcomes of lung transplant recipients with these infections and suggests possible associations of ribavirin use and infection severity with long‐term outcomes. Well‐designed prospective trials are needed to confirm these findings., Respiratory syncytial virus, parainfluenza virus, and human metapneumovirus infections in lung transplant recipients are often accompanied by severe and acute decline in lung function and a future risk of postinfection chronic lung allograft dysfunction, which appears increased with severe infection but decreased with ribavirin treatment.

An increasing number of applications in the chemical industry involve measuring nonconforming items, particularly in high-purity processes or high-yield processes. Dedicated monitoring tools such as the time-between-events (TBE) control charts have been developed for both discrete time (CCC-charts) and continuous time (tr-charts) for detecting any shifts in the process defect rate. However, most common performance metrics used in literature are not always appropriate and may not suffice to describe the efficiency of a monitoring system. The definition of conditional performance measures described in the literature is extended to TBE charts. These metrics are computed for Shewhart-type TBE charts with run rules and used to compare these charts at different aggregation levels.

We study sample-path large deviations for Levy processes and random walks with heavy-tailed jump-size distributions that are of Weibull type. Our main results include an extended form of an LDP (large deviations principle) in the J1 topology, and a full LDP in the M′1 topology. The rate function can be represented as the solution of a quasi-variational problem. The sharpness and applicability of these results are illustrated by a counterexample proving non-existence of a full LDP in the J1 topology, and an application to the buildup of a large queue length in a queue with multiple servers.

We consider a system of $N$ identical server pools and a single dispatcher where tasks arrive as a Poisson process of rate $\lambda(N)$. Arriving tasks cannot be queued, and must immediately be assigned to one of the server pools to start execution, or discarded. The execution times are assumed to be exponentially distributed with unit mean, and do not depend on the number of other tasks receiving service. However, the experienced performance (e.g. in terms of received throughput) does degrade with an increasing number of concurrent tasks at the same server pool. The dispatcher therefore aims to evenly distribute the tasks across the various server pools. Specifically, when a task arrives, the dispatcher assigns it to the server pool with the minimum number of tasks among $d(N)$ randomly selected server pools. This assignment strategy is called the JSQ$(d(N))$ scheme, as it resembles the power-of-$d$ version of the Join-the-Shortest-Queue (JSQ) policy, and will also be referred to as such in the special case $d(N) = N$. We construct a stochastic coupling to bound the difference in the system occupancy processes between the JSQ policy and a scheme with an arbitrary value of $d(N)$. We use the coupling to derive the fluid limit in case $d(N) \to \infty$ and $\lambda(N)/N \to \lambda$ as $N \to \infty$, along with the associated fixed point. The fluid limit turns out to be insensitive to the exact growth rate of $d(N)$, and coincides with that for the JSQ policy. We further leverage the coupling to establish that the diffusion limit corresponds to that for the JSQ policy as well, as long as $d(N)/\sqrt{N} \log(N) \to \infty$, and characterize the common limiting diffusion process. These results indicate that the JSQ optimality can be preserved at the fluid-level and diffusion-level while reducing the overhead by nearly a factor O($N$) and O($\sqrt{N}/\log(N)$), respectively., Comment: 48 pages, 3 figures, companion paper of arXiv:1612.00723

AIM: To address alarm fatigue, a new alarm management system which ensures a quicker delivery of alarms together with waveform information on nurses' handheld devices was implemented and settings optimised. The effects of this clinical implementation on alarm rates and nurses' responsiveness were measured in an 18-bed single family rooms neonatal intensive care unit (NICU).METHODS: The technical implementation of the alarm management system was followed by clinical workflow optimisation. Alarms and vital parameters from October 2017 to December 2019 were analysed. Measures included monitoring alarms, nurses' response to alarms and time spent by patients in different saturation ranges. A survey among nurses was performed to evaluate changes in alarm rate and use of protocols.RESULTS: A significant reduction of monitoring alarms per patient days was detected after the optimisation phase (in particular for SpO2 ≤ 80%, P < .001). More time was spent by infants within the optimal peripheral oxygen saturation range (88% < SpO2 < 95%, P < .001). Results from the surveys showed that false alarms are less likely to cause an inappropriate response after the optimisation phase.CONCLUSION: The implementation of an alarm management solution and an optimisation programme can safely reduce the alarm burden inside of the NICU environment.

Rationale The mechanisms underlying impaired sleep quality in insomnia are not fully known, but an important role for sleep fragmentation has been proposed. Objectives The aim of this study is to explore potential mechanisms of sleep fragmentation influencing alterations of perceived sleep quality. Methods We analyzed polysomnography (PSG) recordings from a double-blind crossover study with zopiclone 7.5 mg and placebo, in elderly participants with insomnia complaints and age-matched healthy controls. We compared survival dynamics of sleep and wake across group and treatment. Subsequently, we used a previously proposed model to estimate the amount of sleep onset latency (SOL) misperception from PSG-defined sleep fragmentation. Self-reported and model-estimated amount of SOL misperception were compared across group and treatment, as well as model prediction errors. Results In the zopiclone night, the average segment length of NREM sleep was increased (group F = 1.16, p = 0.32; treatment F = 8.89, p< 0.01; group x treatment F = 0.44, p = 0.65), while the segment length of wake was decreased (group F = 1.48, p = 0.23; treatment F = 11.49, p< 0.01; group x treatment F = 0.36, p = 0.70). The self-reported and model-estimated amount of SOL misperception were lower during the zopiclone night (self-reported group F = 6.08, p< 0.01, treatment F = 10.8, p< 0.01, group x treatment F = 2.49, p = 0.09; model-estimated F = 1.70, p = 0.19, treatment F = 16.1, p< 0.001, group x treatment F = 0.60, p = 0.55). The prediction error was not altered (group F = 1.62, p = 0.20; treatment F = 0.20, p = 0.65; group x treatment F = 1.01, p = 0.37). Conclusions Impaired subjective sleep quality is associated with decreased NREM stability, together with increased stability of wake. Furthermore, we conclude that zopiclone-induced changes in SOL misperception can be largely attributed to predictable changes of sleep architecture.

We address the problem of dispatching and pro-actively repositioning service resources in service networks such that fast responses to service requests are realized in a cost-efficient way. By formulating this problem as a Markov decision process, we are able to investigate the structure of the optimal policy in the application domain of service logistics. Using these insights, we then propose scalable dynamic heuristics for both the dispatching and repositioning sub-problem, based on the minimum weighted bipartite matching problem and the maximum expected covering location problem, respectively. The dynamic dispatching heuristic takes into account real-time information about both the state of equipment and the fleet of service engineers, while the dynamic repositioning heuristic maximizes the expected weighted coverage of future service requests. In a test bed with a small network, we show that our most advanced heuristic performs well with an average optimality gap of 4.3% for symmetric instances and 5.8% for asymmetric instances. To show the practical value of our proposed heuristics, extensive numerical experiments are conducted on a large test bed with service logistics networks of real-life size where significant savings of up to 56% compared to a state-of-the-art benchmark policy are attained.

We sharpen the bound n 2 k on the maximum modulus of the k th radial derivative of the Zernike circle polynomials (disk polynomials) of degree n to n 2 ( n 2 − 1 2 ) ⋅ . . . ⋅ ( n 2 − ( k − 1 ) 2 ) ∕ 2 k ( 1 ∕ 2 ) k . This bound is obtained from a result of Koornwinder on the non-negativity of connection coefficients of the radial parts of the circle polynomials when expanded into a series of Chebyshev polynomials of the first kind. The new bound is shown to be attained within a factor O ( 1 ∕ n ) for Zernike circle polynomials of degree n and azimuthal order m when m = O ( n ) by using an explicit expression for the connection coefficients in terms of squares of Jacobi polynomials evaluated at 0.

We study the critical behavior of the component sizes for the configuration model when the tail of the degree distribution of a randomly chosen vertex is a regularly-varying function with exponent $\tau-1$, where $\tau\in (3,4)$. The component sizes are shown to be of the order $n^{(\tau-2)/(\tau-1)}L(n)^{-1}$ for some slowly-varying function $L(\cdot)$. We show that the re-scaled ordered component sizes converge in distribution to the ordered excursions of a thinned L\'evy process. This proves that the scaling limits for the component sizes for these heavy-tailed configuration models are in a different universality class compared to the Erd\H{o}s-R\'enyi random graphs. Also the joint re-scaled vector of ordered component sizes and their surplus edges is shown to have a distributional limit under a strong topology. Our proof resolves a conjecture by Joseph, Ann. Appl. Probab. (2014) about the scaling limits of uniform simple graphs with i.i.d degrees in the critical window, and sheds light on the relation between the scaling limits obtained by Joseph and in this paper, which appear to be quite different. Further, we use percolation to study the evolution of the component sizes and the surplus edges within the critical scaling window, which is shown to converge in finite dimension to the augmented multiplicative coalescent process introduced by Bhamidi et. al., Probab. Theory Related Fields (2014). The main results of this paper are proved under rather general assumptions on the vertex degrees. We also discuss how these assumptions are satisfied by some of the frameworks that have been studied previously., Comment: 43 pages, revision of the paper

Bulk-service multi-server queues with heterogeneous server capacity and thresholds are commonly seen in several situations such as passenger transport or package delivery services. In this paper, we develop a novel decomposition-based solution approach for such queues using arguments from renewal theory. We then obtain the distribution of the waiting time measure for multi-type server systems. We also obtain other useful performance measures such as utilization, expected throughput time, and expected queue lengths.