Search

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.

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.

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

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

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.

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 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.

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 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

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 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.

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.

A key challenge in designing load balancing strategies is to achieve low delay in large-scale systems while only using minimal communication overhead. Motivated by these issues, we introduce a novel scheme in which the dispatcher becomes aware of idle servers without any explicit communication from either side, using absence of messages at predefined time instants. The proposed scheme achieves provably vanishing queueing delays while using strictly less than one message per job on average.

We consider the steady-state distribution of the sojourn time of a job entering an M/GI/1 queue with the foreground–background scheduling policy in heavy traffic. The growth rate of its mean as well as the limiting distribution are derived under broad conditions. Assumptions commonly used in extreme value theory play a key role in both the analysis and the results.

We consider a general class of closed product-form queueing networks, consisting of single-server queues and infinite-server queues. Even if a network is of product-form type, performance evaluation tends to be difficult due to the potentially large state space and the dependence between the individual queues. To remedy this, we analyze the model in a Halfin–Whitt inspired scaling regime, where we jointly blow up the traffic loads of all queues and the number of customers in the network. This leads to a closed-form limiting stationary distribution, which provides intuition on the impact of the dependence between the queues on the network’s behavior. We assess the practical applicability of our results through a series of numerical experiments, which illustrate the convergence and show how the scaling parameters can be chosen to obtain accurate approximations.

We provide a survey of so-called shot-noise queues: queueing models with the special feature that the server speed is proportional to the amount of work it faces. Several results are derived for the workload in an M/G/1 shot-noise queue and some of its variants. Furthermore, we give some attention to queues with general workload-dependent service speed. We also discuss linear stochastic fluid networks, and queues in which the input process is a shot-noise process.

To reduce carbon emission in the transportation sector, there is currently a steady move taking place to an electrified transportation system. This brings about various issues for which a promising solution involves the construction and operation of a battery swapping infrastructure rather than in-vehicle charging of batteries. In this paper, we study a closed Markovian queueing network that allows for spare batteries under a dynamic arrival policy. We propose a provisioning rule for the capacity levels and show that these lead to near-optimal resource utilization, while guaranteeing good quality-of-service levels for electric vehicle users. Key in the derivations is to prove a state-space collapse result, which in turn implies that performance levels are as good as if there would have been a single station with an aggregated number of resources, thus achieving complete resource pooling.

Load balancing plays a critical role in efficiently dispatching jobs in parallel-server systems such as cloud networks and data centers. A fundamental challenge in the design of load balancing algorithms is to achieve an optimal trade-off between delay performance and implementation overhead (e.g. communication or memory usage). This trade-off has primarily been studied so far from the angle of the amount of overhead required to achieve asymptotically optimal performance, particularly vanishing delay in large-scale systems. In contrast, in the present paper, we focus on an arbitrarily sparse communication budget, possibly well below the minimum requirement for vanishing delay, referred to as the hyper-scalable operating region. Furthermore, jobs may only be admitted when a specific limit on the queue position of the job can be guaranteed. The centerpiece of our analysis is a universal upper bound for the achievable throughput of any dispatcher-driven algorithm for a given communication budget and queue limit. We also propose a specific hyper-scalable scheme which can operate at any given message rate and enforce any given queue limit, while allowing the server states to be captured via a closed product-form network, in which servers act as customers traversing various nodes. The product-form distribution is leveraged to prove that the bound is tight and that the proposed hyper-scalable scheme is throughput-optimal in a many-server regime given the communication and queue limit constraints. Extensive simulation experiments are conducted to illustrate the results.

This paper develops a capacity model for sequential zone picking systems. These systems are popular internal transport and order picking systems, due to their scalability, flexibility, high-throughput ability, and fit-for-use for a wide range of products and order profiles. The major disadvantage of such systems is congestion and blocking under heavy use, leading to long order throughput times. To reduce blocking and congestion, most systems use the block-and-recirculate protocol to dynamically manage workload. In this paper, the various elements of the system, such as conveyor lanes and pick zones, are modeled as a multi-class block-and-recirculate queueing network with capacity constraints on subnetworks. Due to this blocking protocol, the stationary distribution of the queueing network is highly intractable.We propose an approximation method based on jump-over blocking. Multi-class jump-over queueing networks admit a product-form stationary distributionand can be efficiently evaluated by Mean Value Analysis (MVA) and Norton's theorem. This method can be applied during the design phase of sequential zone picking systems to determine the number of segments, number and length of zones, buffer capacities, and storage allocation of products to zones, to meet performance targets.For a wide range of parameters, the results show that the relative error in the system throughput is typically less than 1% compared to simulation.

Combining data from different studies has a long tradition within the scientific community. It requires that the same information is collected from each study to be able to pool individual data. When studies have implemented different methods or used different instruments (e.g., questionnaires) for measuring the same characteristics or constructs, the observed variables need to be harmonized in some way to obtain equivalent content information across studies. This paper formulates the main concepts for harmonizing test scores from different observational studies in terms of latent variable models. The concepts are formulated in terms of calibration, invariance, and exchangeability. Although similar ideas are present in measurement reliability and test equating, harmonization is different from measurement invariance and generalizes test equating. In addition, if a test score needs to be transformed to another test score, harmonization of variables is only possible under specific conditions. Observed test scores that connect all of the different studies, are necessary to be able to test the underlying assumptions of harmonization. The concepts of harmonization are illustrated on multiple memory test scores from three different Canadian studies.

We study the occurrence of large queue lengths in the GI / GI / d queue with heavy-tailed Weibull-type service times. Our analysis hinges on a recently developed sample path large-deviations principle for Lévy processes and random walks, following a continuous mapping approach. Also, we identify and solve a key variational problem which provides physical insight into the way a large queue length occurs. In contrast to the regularly varying case, we observe several subtle features such as a non-trivial trade-off between the number of big jobs and their sizes and a surprising asymmetric structure in asymptotic job sizes leading to congestion.

We present a model of parallel Levy-driven queues that mix their output into a final product; whatever cannot be mixed is sold on the open market for a lower price. The queues incur holding and capacity costs and can choose their processing rates. We solve the ensuing centralized (system optimal) and decentralized (individual station optimal) profit optimization problems. In equilibrium the queues process work faster than desirable from a system point of view. Several model extensions are also discussed.

Motivated by emerging Internet-of-Things (IoT) applications and smart building environments, we analyze the performance of large-scale symmetric polling systems where the number of queues grows large. We consider a scenario in which the total arrival rate is kept fixed and the individual switch-over time and service time distributions remain the same. This asymptotic regime leads to cycles of infinite length and queue lengths with non-trivial distributions. We show that for most traditional service policies the scaled cycle times converge to a deterministic value in the limit, which in turn implies that the queue lengths at the various nodes become asymptotically independent. Using these insights, we find that the behavior of individual queues simplifies to that of a discrete-time bulk service queue in the limit, so that the marginal queue length and waiting-time distributions become considerably easier to analyze. Additionally, we propose a new flexible k -limited service discipline aimed at striking a good balance between short mean queue lengths and predictable cycle times for deadline-critical applications.

We consider a distribution grid used to charge electric vehicles such that voltage drops stay bounded. We model this as a class of resource-sharing networks, known as bandwidth-sharing networks in the communication network literature. We focus on resource-sharing networks that are driven by a class of greedy control rules that can be implemented in a decentralized fashion. For a large number of such control rules, we can characterize the performance of the system by a fluid approximation. This leads to a set of dynamic equations that take into account the stochastic behavior of EVs. We show that the invariant point of these equations is unique and can be computed by solving a specific ACOPF problem, which admits an exact convex relaxation. We illustrate our findings with a case study using the SCE 47-bus network and several special cases that allow for explicit computations., 13 pages, 8 figures

The advent of renewable energy has huge implications for the design and control of power grids. Due to increasing supply-side uncertainty, traditional reliability constraints such as strict bounds on current, voltage and temperature in a transmission line have to be replaced by computationally demanding chance constraints. In this paper we use large deviations techniques to study the probability of current and temperature overloads in power grids with stochastic power injections, and develop corresponding safe capacity regions. In particular, we characterize the set of admissible power injections such that the probability of overloading of any line over a given time interval stays below a fixed target. We show how enforcing (stochastic) constraints on temperature, rather than on current, results in a less conservative approach and can thus lead to capacity gains., Comment: 12 pages (10 pages + 2 pages appendix), 2 figures. Revised version with extended numerical section

Missing data is a problem that may be faced by actuaries when analysing mortality data. In this paper we deal with pension scheme data, where the future lifetime of each member is modelled by means of parametric survival models incorporating covariates, which may be missing for some individuals. Parameters are estimated by likelihood-based techniques. We analyse statistical issues, such as parameter identifiability, and propose an algorithm to handle the estimation task. Finally, we analyse the financial impact of including covariates maximally, compared with excluding parts of the mortality experience where data are missing; in particular we consider annuity factors and mis-estimation risk capital requirements.

We consider a two-node queue modeled as a two-dimensional random walk. In particular, we consider the case that one or both queues have finite buffers. We develop an approximation scheme based on the Markov reward approach to error bounds in order to bound performance measures of such random walks. The approximation scheme is developed in terms of a perturbed random walk in which the transitions along the boundaries are different from those in the original model and the invariant measure of the perturbed random walk is of product-form. We then apply this approximation scheme to a tandem queue and some variants of this model, for the case that both buffers are finite. The modified approximation scheme and the corresponding applications for a two-node queueing system in which only one of the buffers has finite capacity have also been discussed.

Redundancy scheduling has emerged as a powerful strategy for improving response times in parallel-server systems. The key feature in redundancy scheduling is replication of a job upon arrival by dispatching replicas to different servers. Redundant copies are abandoned as soon as the first of these replicas finishes service. By creating multiple service opportunities, redundancy scheduling increases the chance of a fast response from a server that is quick to provide service and mitigates the risk of a long delay incurred when a single selected server turns out to be slow. The diversity enabled by redundant requests has been found to strongly improve the response time performance, especially in the case of highly variable service requirements. Analytical results for redundancy scheduling are unfortunately scarce however, and even the stability condition has largely remained elusive so far, except for exponentially distributed service requirements. In order to gain further insight in the role of the service requirement distribution, we explore the behavior of redundancy scheduling for scaled Bernoulli service requirements. We establish a sufficient stability condition for generally distributed service requirements, and we show that, for scaled Bernoulli service requirements, this condition is also asymptotically nearly necessary. This stability condition differs drastically from the exponential case, indicating that the stability condition depends on the service requirements in a sensitive and intricate manner.

We introduce the random intersection graph with communities, a new model for networks with overlapping communities with arbitrary internal structure. We construct the model from a list of arbitrary community graphs that are the building blocks, and a separate list of individuals, each with a prescribed number of community membership tokens. Randomness is introduced by matching these tokens uniformly at random to vertices of the community graphs. We then identify the community members assigned to the same individual, thus overlaps arise due to individuals having several tokens. This gives a highly flexible model for networks with community structure. We are able to derive a wide range of analytic results on this model. We derive an asymptotic description of the local structure of the graph, which further yields the asymptotic degree distribution, local clustering coefficient, and results on the overlapping structure of the communities. For the global connectivity structure, we identify a phase transition in the size of the largest component. When the largest component constitutes a positive proportion of the graph, we can further characterize its asymptotic local structure. Finally, we study how the connectivity structure changes under a randomized attack, where we remove edges randomly, according to independent coin flips.

This paper contributes to the modeling and analysis of unsignalized intersections. In classical gap acceptance models vehicles on the minor road accept any gap greater than the critical gap, and reject gaps below this threshold, where the gap is the time between two subsequent vehicles on the major road. The main contribution of this paper is to develop a series of generalizations of existing models, thus increasing the model’s practical applicability significantly. First, we incorporate driver impatience behavior while allowing for a realistic merging behavior; we do so by distinguishing between the critical gap and the merging time, thus allowing multiple vehicles to use a sufficiently large gap. Incorporating this feature is particularly challenging in models with driver impatience. Secondly, we allow for multiple classes of gap acceptance behavior, enabling us to distinguish between different driver types and/or different vehicle types. Thirdly, we use the novel M $$^X$$ /SM2/1 queueing model, which has batch arrivals, dependent service times, and a different service-time distribution for vehicles arriving in an empty queue on the minor road (where ‘service time’ refers to the time required to find a sufficiently large gap). This setup facilitates the analysis of the service-time distribution of an arbitrary vehicle on the minor road and of the queue length on the minor road. In particular, we can compute the mean service time, thus enabling the evaluation of the capacity for the minor road vehicles.

The reliability of the transmission grid is challenged by the integration of intermittent renewable energy sources into the grid. For model-based reliability studies, it is important to have suitable models available of renewable energy sources like wind and solar power. In this study, we investigate to what extent the power output of wind farms can be modeled with discrete Hidden Markov Models (HMMs). The parameters of the HMMs are inferred from measurement data from multiple turbines in a wind farm. We use these models both for individual turbine output and for total aggregated power output of multiple turbines. When modeling individual turbine output, the hidden process in the HMM is instrumental in capturing the dependencies between the output of the different turbines. It is important to account for these dependencies in order to correctly capture the upper quantiles (90%, 95%, 99%) of the distribution of the wind farm aggregated power output. We show that despite their simple structure, HMMs are able to reproduce important features of the power output of wind farms. This opens up possibilities to model and analyze these features with methods and techniques stemming from the field of Markov models and stochastic processes.

In this paper, we introduce partially observable agent-intruder games (POAIGs). These games model dynamic search games on graphs between security forces (an agent) and an intruder given possible (border) entry points and high value assets that require protection. The agent faces situations with dynamically changing, partially observable information about the state of the intruder and vice versa. The agent may place sensors at selected locations, while the intruder may recruit partners to observe the agent's movement. We formulate the problem as a two-person zero-sum game, and develop efficient algorithms to compute each player's optimal strategy. The solution to the game will help the agent choose sensor locations and design patrol routes that can handle imperfect information. First, we prove the existence of ϵ-optimal strategies for POAIGs with an infinite time horizon. Second, we introduce a Bayesian approximation algorithm to identify these ϵ-optimal strategies using belief functions that incorporate the imperfect information that becomes available during the game. For the solutions of large POAIGs with a finite time horizon, we use a solution method common to extensive form games, namely, the sequence form representation. To illustrate the POAIGs, we present several examples and numerical results. © 2019 Wiley Periodicals, Inc.

This paper investigates large fluctuations of Locational Marginal Prices (LMPs) in wholesale energy markets caused by volatile renewable generation profiles. Specifically, we study events of the form $\mathbb{P} \Big ( \mathbf{LMP} \notin \prod_{i=1}^n [\alpha_i^-, \alpha_i^+] \Big),$ where $\mathbf{LMP}$ is the vector of LMPs at the $n$ power grid nodes, and $\boldsymbol{\alpha}^-,\boldsymbol{\alpha}^+\in\mathbb{R}^n$ are vectors of price thresholds specifying undesirable price occurrences. By exploiting the structure of the supply-demand matching mechanism in power grids, we look at LMPs as deterministic piecewise affine, possibly discontinuous functions of the stochastic input process, modeling uncontrollable renewable generation. We utilize techniques from large deviations theory to identify the most likely ways for extreme price spikes to happen, and to rank the nodes of the power grid in terms of their likelihood of experiencing a price spike. Our results are derived in the case of Gaussian fluctuations and are validated numerically on the IEEE 14-bus test case., Comment: 16 pages, 10 figures

Bitcoin payments require a random amount of time to get confirmed (i.e. to be grouped by the miners into a block and to be added to the Bitcoin blockchain). In [8, 11], the authors propose the modelling of the Bitcoin confirmation time by the so-called time to ruin of the Cramer-Lundberg (CL) model. This provides off-the-shelf results directly aimed at predicting the confirmation time. However, analyses suggest that the data may not fully conform with the CL model assumptions. In this manuscript, we show by means of a robustness analysis that the time to ruin of a CL model is near insensitive to small changes in the model assumptions and illustrate that the proposed heuristic model can be used to accurately predict the confirmation times even when the data deviate (to a small degree) from the model assumptions.

We consider a sequence of age-replacement problems with a general lifetime distribution parametrized by an a-priori unknown parameter. There is a trade-off: Preventive replacements are censored but cheap, whereas corrective replacements are uncensored but costly observations of the lifetime distribution. We first analyze the optimal policy for a finite sequence and establish some properties. We then propose a myopic Bayesian policy that almost surely learns the unknown parameter and converges to the optimal policy with full knowledge of the parameter.

We develop a non-parametric procedure for ranking transmission lines in a power system according to the probability that they will overload due to stochastic renewable generation or demand-side load fluctuations, and compare this procedure to several benchmark approaches. Using the IEEE 39-bus test network we provide evidence that our approach, which statistically estimates the rate function for each line, is highly promising relative to alternative methods which count overload events or use incorrect parametric assumptions., Comment: Accepted to PMAPS 2020 (the 16th International Conference on Probabilistic Methods Applied to Power Systems)

Network densification has emerged as a powerful paradigm to boost spectral efficiency and accommodate the continual rise in demand for wireless capacity. In dense cell deployments however, overlapping coverage areas may cause highly varying interference conditions among different cells. Moreover, denser networks experience more temporal load fluctuations due to daily and hourly changing usage patterns. The currently applied universal reuse frequency allocation is not suitable to deal with these issues, and needs to be tailored to dense cell deployments to ensure adequate performance in such scenarios. In this paper we present a dynamic, load aware and self-adapting frequency allocation scheme designed for dense cellular networks: the DyCRA scheme (Dynamic Cost/Reward based Allocation). The scheme makes decisions based on cost-reward trade-offs: rewards arise in the form of capacity, and costs arise in the form of interference (under spatial reuse). We quantify these costs and rewards based on SINR, and use periodic load estimates to determine if access points are in need of extra frequencies, or can spare them, and the cost/reward structure is used to determine which frequencies are allocated or released. Extensive simulation results show that the DyCRA scheme provides efficient resource allocations that adapt to changing traffic conditions and yields significant performance gains in scenarios with nonstationary traffic demands.

We study an online capacity planning problem in which arriving patients require a series of appointments at several departments, within a certain access time target.This research is motivated by a study of rehabilitation planning practices at the Sint Maartenskliniek hospital (the Netherlands). In practice, the prescribed treatments and activities are typically booked starting in the first available week, leaving no space for urgent patients who require a series of appointments at a short notice. This leads to the rescheduling of appointments or long access times for urgent patients, which has a negative effect on the quality of care and on patient satisfaction.We propose an approach for allocating capacity to patients at the moment of their arrival, in such a way that the total number of requests booked within their corresponding access time targets is maximized. The model considers online decision making regarding multi-priority, multi-appointment, and multi-resource capacity allocation. We formulate this problem as a Markov decision process (MDP) that takes into account the current patient schedule, and future arrivals. We develop an approximate dynamic programming (ADP) algorithm to obtain approximate optimal capacity allocation policies. We provide insights into the characteristics of the optimal policies and evaluate the performance of the resulting policies using simulation.

In this paper, a few models for optical router nodes are considered. The stations (ports) of such a node try to transmit packets. Successful transmission of a packet of type j at station i gives a profit γ i j , but there is also a positive probability that such a packet is dropped, causing a penalty θ i j . Consider one fixed cycle (frame), in which each station is assigned some visit time. The goal is to choose the visit times in such a way that the revenue is maximized. In our first model there is only one wavelength, and we take the finiteness of buffers into account. The revenue maximization problem is shown to be separable concave, thus allowing application of a very efficient algorithm. In our second model we allow multiple wavelengths. We aim to maximize the revenue by optimally assigning stations to wavelengths and, for each wavelength, by optimally choosing the visit times of the allocated stations within the cycle. This gives rise to a mixed integer linear programming problem (MILP) which is NP-hard. To solve this problem fast and efficiently we provide a three-step heuristic. It consists of (i) solving a separable concave optimization problem, then (ii) allocating the stations to wavelengths using a simple bin packing algorithm, and finally (iii) solving another set of separable concave optimization problems. We present numerical results to investigate the effectiveness of the heuristic and the advantages of having multiple wavelengths. Finally, some model variants are briefly discussed.

The robotic mobile fulfillment system (MFS) is widely used for automatingstorage pick and pack activities in e-commerce distribution centers. In this system, the items are stored on movable storage shelves, also known as inventory pods, and brought to the order pick stations by robotic drive units. We develop stylized performance evaluation models to analyze both order picking and replenishment processes in a mobile fulfillment system storage zone, based on multi-class closed queueing network models. To analyze robot assignment strategies for multiple storage zones, we develop a two-stage stochasticmodel. For a single storage zone, we compare dedicated and pooled robot systems for pod retrieval and replenishment. For multiple storage zones, we also analyze the effect of assigning robots to least congested zones on system throughput in comparison to random zone assignment. The models are validated using detailed simulations. For single zones, the expected throughput time for order picking reduces to one-third of its initial value by using pooled robots instead of dedicated robots; however, the expected replenishment timeestimate increases up to three times. For multiple zones, we find that robots that are assigned to storage zones with dedicated and shortest queues provide a greater throughput than robots assigned at random to the zones.

We consider a large distributed service system consisting of $n$ homogeneous servers with infinite capacity FIFO queues. Jobs arrive as a Poisson process of rate $\lambda n/k_n$ (for some positive constant $\lambda$ and integer $k_n$). Each incoming job consists of $k_n$ identical tasks that can be executed in parallel, and that can be encoded into at least $k_n$ "replicas" of the same size (by introducing redundancy) so that the job is considered to be completed when any $k_n$ replicas associated with it finish their service. Moreover, we assume that servers can experience random slowdowns in their processing rate so that the service time of a replica is the product of its size and a random slowdown. First, we assume that the server slowdowns are shifted exponential and independent of the replica sizes. In this setting we show that the delay of a typical job is asymptotically minimized (as $n\to\infty$) when the number of replicas per task is a constant that only depends on the arrival rate $\lambda$, and on the expected slowdown of servers. Second, we introduce a new model for the server slowdowns in which larger tasks experience less variable slowdowns than smaller tasks. In this setting we show that, under the class of policies where all replicas start their service at the same time, the delay of a typical job is asymptotically minimized (as $n\to\infty$) when the number of replicas per task is made to depend on the actual size of the tasks being replicated, with smaller tasks being replicated more than larger tasks., Comment: 69 pages

We consider a variation of the processor-sharing (PS) queue, inspired by freelance job websites where multiple freelancers compete for a single job. We develop fluid limit approximations for the overloaded PS-model with multiple (possibly infinitely many) service stages. Based on this approximation, we estimate what proportion of freelancers get the job they apply for. In addition, the PS model studied here is an instance of PS with routing and impatience, for which no Lyapunov function is known, and we suggest some partial solutions.

In this paper, we present a numerical framework for constructing bounds on stationary performance measures of random walks in the positive orthant using the Markov reward approach. These bounds are established in terms of stationary performance measures of a perturbed random walk whose stationary distribution is known explicitly. We consider random walks in an arbitrary number of dimensions and with a transition probability structure that is defined on an arbitrary partition of the positive orthant. Within each component of this partition the transition probabilities are homogeneous. This enables us to model queueing networks with, for instance, break-downs and finite buffers. The main contribution of this paper is that we generalize the linear programming approach of [10] to this class of models.

In modern industrial systems, sensor data reflecting the system health state are commonly used for the remaining useful lifetime (RUL) prediction, which are increasingly processed by modern deep learning based approaches recently. But these deep learning models do not automatically provide uncertainty information for the RUL prediction, hence this paper is motivated to introduce a novel approach that allows to control trade-off between prediction performance and knowledge about the uncertainty of the RUL prediction. The key aspect of our approach is to use a long short-term memory (LSTM) network as an expressive black-box predictor and the Wiener process as a surrogate to model the propagation of prediction uncertainty. The uncertainty propagation model is used to interactively train the RUL predictor. Our empirical results in a turbofan engine degradation simulation use case show that the surrogate Wiener propagation model can improve the near-failure prediction accuracy by sacrificing the far-to-failure prediction accuracy.

Owing to their capability of summarising interactions between elements of a system, networks have become a common type of data in many fields. As networks can be inhomogeneous, in that different regions of the network may exhibit different topologies, an important topic concerns their local properties. This paper focuses on the estimation of the local degree distribution of a vertex in an inhomogeneous network. The contributions are twofold: we propose an estimator based on local weighted averaging, and we set up a Monte Carlo cross-validation procedure to pick the parameters of this estimator. Under a specific modelling assumption we derive an oracle inequality that shows how the model parameters affect the precision of the estimator. We illustrate our method by several numerical experiments, on both real and synthetic data, showing in particular that the approach considerably improves upon the natural, empirical estimator.

A hierarchical model is developed for the joint mortality analysis of pension scheme datasets. The proposed model allows for a rigorous statistical treatment of missing data. While our approach works for any missing data pattern, we are particularly interested in a scenario where some covariates are observed for members of one pension scheme but not the other. Therefore, our approach allows for the joint modelling of datasets which contain different information about individual lives. The proposed model generalizes the specification of parametric models when accounting for covariates. We consider parameter uncertainty using Bayesian techniques. Model parametrization is analysed in order to obtain an efficient MCMC sampler, and address model selection. The inferential framework described here accommodates any missing-data pattern, and turns out to be useful to analyse statistical relationships among covariates. Finally, we assess the financial impact of using the covariates, and of the optimal use of the whole available sample when combining data from different mortality experiences.

Motivated by practices and issues at the British Columbia Cancer Agency (BCCA), we develop queuing network models to determine the appropriate number of patients to be managed by a single physician. This is often referred to as a physician’s panel size. The key features that distinguish our study of oncology practices from other panel size models are high patient turnover rates, multiple patient and appointment types, and follow-up care. The paper develops stationary and non-stationary queuing network models corresponding to stabilized and developing practices, respectively. These models are used to determine new patient arrival rates that ensure practices operate within certain performance thresholds. Data from the BCCA are used to calibrate and illustrate the implications of these models.

We consider job dispatching in systems with N parallel servers. In redundancy- d policies, replicas of an arriving job are assigned to d ≤ N servers selected uniformly at random (without replacement) with the objective to reduce the delay. We introduce a quite general workload model, in which job sizes have some probability distribution while the speeds (slowdown factors) of the various servers for a given job are allowed to be inter-dependent and non-identically distributed. This allows not only for inherent speed differences among different servers, but also for affinity relations. We further propose two novel redundancy policies, so-called delta-probe- d policies, where d probes of a fixed, small, size Δ are created for each incoming job, and assigned to d servers selected uniformly at random. As soon as the first of these d probe tasks finishes, the actual job is assigned for execution – with the same speed – to the corresponding server and the other probe tasks are abandoned. We also consider a delta-probe- d policy in which the probes receive preemptive-resume priority over regular jobs. The aim of these policies is to retain the benefits of redundancy- d policies while accounting for systematic speed differences and mitigating the risks of running replicas of the full job simultaneously for long periods of time. Analytical and numerical results are presented to evaluate the effect of both probing policies on the job latency, and to illustrate the potential performance improvements.

We analyse a mean-field model of Personalized PageRank on the Erdos-Renyi random graph containing a denser planted Erdos-Renyi subgraph. We investigate the regimes where the values of Personalized PageRank concentrate around the mean-field value. We also study the optimization of the damping factor, the only parameter in Personalized PageRank. Our theoretical results help to understand the applicability of Personalized PageRank and its limitations for local graph clustering., Comment: 22 pages, 6 figures