Search

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.

Spitzer’s identity describes the position of a reflected random walk over time in terms of a bivariate transform. Among its many applications in probability theory are congestion levels in queues and random walkers in physics. We present a derivation of Spitzer’s identity for random walks with bounded jumps to the left, only using basic properties of analytic functions and contour integration. The main novelty is a reversed approach that recognizes a factored polynomial expression as the outcome of Cauchy’s formula.

Population reference limits are inadequate for personalized analyses of medical laboratory results. Reference change values have been recommended as a valid alternative in assessing individual changes across sequential measurements. In this paper, we investigate the accuracy (type I error) and power (complement of type II error) of reference change values under three different statistical modeling scenarios and show that oversimplified hypotheses lead to misinterpretation of laboratory results. The power is strongly affected by the statistical modeling assumptions: it is shown that positive shifts in the individual average health condition are difficult to detect, while it is much easier to identify negative shifts.

We consider the surplus of an insurance company that employs reinsurance. The reinsurer covers part of the claims, but in return it receives a certain part of the income from premiums of the insurance company. In addition, the reinsurer receives some of the dividends that are withdrawn when a certain surplus level b is reached. A special feature of our model is that both the fraction of the premium that goes to the reinsurer and the fraction of the claims covered by the reinsurer are state-dependent. We focus on five performance measures, viz., time to ruin, deficit at ruin, the dividend withdrawn until ruin, and the amount of money transferred to the reinsurer, respectively covered by the reinsurer.

We show that the asymptotic hazard rate of the sum of discrete random variables is dominated by the smallest asymptotic failure rate of the summands.

We investigate an insurance risk model that consists of two reserves which receive income at fixed rates. Claims are being requested at random epochs from each reserve and the interclaim times are generally distributed. The two reserves are coupled in the sense that at a claim arrival epoch, claims are being requested from both reserves and the amounts requested are correlated. In addition, the claim amounts are correlated with the time elapsed since the previous claim arrival. We focus on the probability that this bivariate reserve process survives indefinitely. The infinite- horizon survival problem is shown to be related to the problem of determining the equilibrium distribution of a random walk with vector-valued increments with reflecting boundary. This reflected random walk is actually the waiting time process in a queueing system dual to the bivariate ruin process. Under assumptions on the arrival process and the claim amounts, and using Wiener-Hopf factor- ization with one parameter, we explicitly determine the Laplace-Stieltjes transform of the survival function, c.q., the two-dimensional equilibrium waiting time distribution. Finally, the bivariate transforms are evaluated for some examples, including for proportional reinsurance, and the bivariate ruin functions are numerically calculated using an efficient inversion scheme., 24 pages, 6 figures

We present a methodology to design appointment systems for outpatient clinics and diagnostic facilities that offer both walk-in and scheduled service. The developed blueprint for the appointment schedule prescribes the number of appointments to plan per day and the moment on the day to schedule the appointments. The method consists of two models; one for the day process that governs scheduled and unscheduled arrivals on the day and one for the access process of scheduled arrivals. Appointment schedules that balance the waiting time at the facility for unscheduled patients and the access time for scheduled patients are calculated iteratively using the outcomes of the two models. Two methods to calculate appointment schedules, complete enumeration and a heuristic procedure, are compared in various numerical experiments. Furthermore, an appointment schedule for the CT-scan facility at the Academic Medical Center Amsterdam, The Netherlands, is developed to demonstrate the practical merits of the methodology. The method is of general nature and can therefore also be applied to scheduling problems in other sectors than health care. (C) 2014 Elsevier B.V. All rights reserved

When a communication network’s capacity increases, it is natural to want the bandwidth allocated to increase to exploit this capacity. But, if the same relative capacity increase occurs throughout the network, it is also natural to want each user to see the same relative benefit, so the bandwidth allocated remains proportional. We will be interested in bandwidth allocations which scale in this iso-elastic manner and, also, maximize a utility function. In this paper, we present results that show, in many settings, the only iso-elastic utility functions are weighted aa-fair utility functions, which have gained wide popularity in the networking literature. Hence, a control protocol that is robust to the relative increases in network capacity and usage ought to allocate bandwidth in order to maximize a weighted a-fair utility function. Keywords: Resource allocation; Capacity scaling; Iso-elasticity; a-fairness

We study an overloaded service system with servers of types S={s1,…,sJ}, serving customers of types C={c1,…,cI} under FCFS. Customers arrive in Poisson streams, join the queue and then abandon or get served. Service is skill based, which is described by a compatibility graph G, where (i,j)¿G if server type sj is trained to serve customer type ci. The service duration depends on both server and customer type. This system is motivated by applications in areas as diverse as manufacturing, call centers, housing assignment, health care, data servers and online retailers. At this level of generality, the design in terms of staffing and cross-training decisions is a challenging problem. Based on recent results in and and on some asymptotic assumptions, we propose an algorithm to determine, for given data, the required levels of staffing to meet target levels of service quality and labor division. The algorithm is validated through a systematic simulation study, showing that it is remarkably robust and accurate. As such, we believe that the algorithm will prove to be useful in aiding the design and effective operation of complex systems with skill based routing. Keywords: Service system; First come first served policy; Multi type customers and servers; Infinite bipartite matching; Matching rates; Overloaded queues; Skill-based routing

Random-access networks may exhibit severe unfairness in throughput, in the sense that some nodes receive consistently higher throughput than others. Recent studies show that this unfairness is due to local differences in the neighborhood structure: nodes with fewer neighbors receive better access. We study the unfairness in saturated linear networks, and adapt the random-access CSMA protocol to remove the unfairness completely, by choosing the activation rates of nodes as a specific function of the number of neighbors. We then investigate the consequences of this choice of activation rates on the network-average saturated throughput, and we show that these rates perform well in non-saturated settings.

We study a polling model in which we want to achieve a balance between the fairness of the waiting times and the efficiency of the system. For this purpose, we introduce a novel service discipline: the @k-gated service discipline. It is a hybrid of the classical gated and exhausted disciplines, and consists of using @k"i consecutive gated service phases at queue i before the server switches to the next queue. The advantage of this discipline is that the parameters @k"i can be used to balance fairness and efficiency. We derive the distributions and means of the waiting times, a pseudo conservation law for the weighted sum of the mean waiting times, and the fluid limits of the waiting times. Our goal is to optimize the @k"i so as to minimize the differences in the mean waiting times, i.e. to achieve maximal fairness, without giving up too much on the efficiency of the system. From the fluid limits we derive a heuristic rule for setting the @k"i. In a numerical study, the heuristic is shown to perform well in most cases.

Motivated by a variety of applications in information and communication systems, we consider queueing networks in which the service rate at each of the individual nodes depends on the state of the entire system. The behavior of these types of networks is fundamentally different from classical queueing networks, where the service rate at each queue is usually assumed to be independent of the state of the other nodes. We study the per-queue rate stability and output rates for a class of networks with a general capacity allocation function. More specifically, we derive necessary conditions for per-queue rate stability, and give bounds for the per-node output rate and asymptotic growth rates, under mild assumptions on the allocation function. For a set of parallel queues, we further prove the convergence of the output rates (for almost all input parameters) to easily computable values and we give a sharp characterization of the per-queue rate stability. The results provide new intuition and fundamental insight into the stability and throughput behavior of queueing networks with shared resources. © 2009 Elsevier B.V. All rights reserved.

Packet switches have been studied extensively as part of ATM and LAN networks under the assumption that the number of input ports N tends to infinity. Our study of packet switches is motivated by networks on chips, where N is usually 4 or 5 and asymptotic models lead to inaccurate results. We consider small non-uniform switches and accurately approximate stability conditions and throughput. In addition to this, we approximate the mean waiting time in the switch by that in a ./Geo/1 queue.

The problem of assigning information packets of different services to time slots of a radio frame is addressed. Packet sizes are divisible, and a maximum time slot to which a packet can be assigned is given. We present a polynomial-time scheduling algorithm maximizing the number of scheduled packets.

We consider a mobile ad hoc network consisting of three types of nodes (source, destination and relay nodes) and using the two-hop relay routing. This type of routing takes advantage of the mobility and the storage capacity of the nodes, called the relay nodes, in order to route packets between a source and a destination. Packets at relay nodes are assumed to have a limited lifetime in the network. Nodes are moving inside a bounded region according to some random mobility model. Closed-form expressions and asymptotic results when the number of nodes is large are provided for the packet delivery delay and for the energy needed to transmit a packet from the source to its destination. We also introduce and evaluate a variant of the two-hop relay protocol that limits the number of generated copies in the network. Our model is validated through simulations for two mobility models (random waypoint and random direction mobility models), and the performance of the two-hop routing and of the epidemic routing protocols are compared.

For a graph G = ( V , E ) with vertex-set V = { 1 , 2 , … , n } , which is allowed to have parallel edges, and for a field F , let S ( G ; F ) be the set of all F -valued symmetric n × n matrices A which represent G . The maximum corank of a graph G is the maximum possible corank over all A ∈ S ( G ; F ) . If ( G 1 , G 2 ) is a ( ⩽ 2 ) -separation, we give a formula which relates the maximum corank of G to the maximum corank of some small variations of G 1 and G 2 .

We introduce a new problem that was motivated by a (more complicated) problem arising in a robotized assembly environment. The bin coloring problem is to pack unit size colored items into bins, such that the maximum number of different colors per bin is minimized. Each bin has size B∈N. The packing process is subject to the constraint that at any moment in time at most q∈N bins are partially filled. Moreover, bins may only be closed if they are filled completely. We settle the computational complexity of the problem and design an approximation algorithm for a natural version which gives a solution whose value is at most one greater than the optimal one.We also investigate the existence of competitive online algorithms, which must pack each item without knowledge of any future items. We prove an upper bound of 3q−1 and a lower bound of 2q for the competitive ratio of a natural greedy-type algorithm, and show that surprisingly a trivial algorithm which uses only one open bin has a strictly better competitive ratio of 2q−1. Moreover, we show that any deterministic algorithm has a competitive ratio Ω(q) and that randomization does not improve this lower bound even when the adversary is oblivious.

Bandwidth-sharing networks as considered by Massoulie and Roberts provide a natural modeling framework for describing the dynamic flow-level interaction among elastic data transfers. Under mild assumptions, it has been established that a wide family of so-called @a-fair bandwidth-sharing strategies achieve stability in such networks provided that no individual link is overloaded. In the present paper we focus on @a-fair bandwidth-sharing networks where the load on one or several of the links exceeds the capacity. Evidently, a well-engineered network should not experience overload, or even approach overload, in normal operating conditions. Yet, even in an adequately provisioned system with a low nominal load, the actual traffic volume may significantly fluctuate over time and exhibit temporary surges. Furthermore, gaining insight into the overload behavior is crucial in analyzing the performance in terms of long delays or low throughputs as caused by large queue build-ups. The way in which such rare events tend to occur, commonly involves a scenario where the system temporarily behaves as if it experiences overload. In order to characterize the overload behavior, we examine the fluid limit, which emerges from a suitably scaled version of the number of flows of the various classes. The convergence of the scaled number of flows to the fluid limit is empirically validated through simulation experiments. Focusing on linear solutions to the fluid-limit equation, we derive a fixed-point equation for the corresponding asymptotic growth rates. It is proved that a fixed-point solution is also a solution to a related strictly concave optimization problem, and hence exists and is unique. We use the fixed-point equation to investigate the impact of the traffic intensities and the variability of the flow sizes on the asymptotic growth rates. The results are illustrated for linear topologies and star networks as two important special cases. Finally, we briefly discuss extensions to models with user impatience.

We derive the limiting waiting-time distribution F"W of a model described by the Lindley-type equation W=max{0,B-A-W}, where B has a polynomial distribution. This exact solution is applied to derive approximations of F"W when B is generally distributed on a finite support. We provide error bounds for these approximations.

We present a simple mean value analysis (MVA) framework for analyzing the effect of scheduling within queues in classical asymmetric polling systems with gated or exhaustive service. Scheduling in polling systems finds many applications in computer and communication systems. Our framework leads not only to unification but also to extension of the literature studying scheduling in polling systems. It illustrates that a large class of scheduling policies behaves similarly in the exhaustive polling model and the standard M/GI/1 model, whereas scheduling policies in the gated polling model behave very differently than in an M/GI/1.

This paper determines the mean waiting times for a single server multi-class queueing model with Poisson arrivals and relative priorities. If the server becomes idle, the probability that the next job is from class-i is proportional to the product between the number of class-i jobs present and their priority parameter.

The Hierarchical Chinese Postman Problem (HCPP) is a Chinese Postman Problem with the arcs partitioned into priority classes ordered by a precedence relation. The problem under the sum criterion is polynomially solvable if the ordering is linear and each class is connected. For a known HCPP algorithm we give an O(n) improvement (n the number of nodes) leading to O(kn4) with k the number of classes. The same complexity appears to hold for the lexicographic criterion which minimises the costs of the first priority class, then the costs of the second class, etc. The notions of servicing and traversing related to arcs, allow for more real life models of arc routing problems. We show how to incorporate these notions in known algorithms, without increasing the complexity. Keywords: Routing; Chinese postman problem; Lexicographic objective; Matching; Post-optimality

In this article we focus on approximation algorithms for facility location problems with subadditive costs. As examples of such problems, we present three facility location problems with stochastic demand and exponential servers, respectively inventory. We present a $(1+\varepsilon, 1)$-reduction of the facility location problem with subadditive costs to the soft capacitated facility location problem, which implies the existence of a $2(1 + \varepsilon)$-approximation algorithm. For a special subclass of subadditive functions, we obtain a 2-approximation algorithm by reduction to the linear cost facility location problem.

We consider a fluid model fed by two Gaussian processes. We obtain necessary and sufficient conditions for the workload asymptotics to be completely determined by one of the two processes, and apply these results to the case of two fractional Brownian motions.

This paper contributes to the development of models for capacity constrained Supply Chain Operations Planning (SCOP). We focus on production environments with arbitrary supply chain structures. The demand for the end items is assumed to be exogenously determined. We solve the SCOP problem with Linear Programming models using planned lead times with multi-period capacity consumption. Using planned lead times increases the reliability of the communication between SCOP and Scheduling with regard to the feasibility of the planning. Planned lead times also reduce the nervousness in the system. We model capacity constraints on the quantity of items that can be assembled within a time interval. In particular, items can be assigned to multiple resources. We discuss two LP approaches which plan the production of items so that a sum of inventory costs and costs due to backordering is minimized.

We present a unified approach to the analysis of several popular models in collective risk theory. Based on the analysis of the discounted penalty function in a semi-Markovian risk model by means of Laplace–Stieltjes transforms, we rederive and extend some recent results in the field. In particular, the classical compound Poisson model, Sparre Andersen models with phase-type interclaim times and models with causal dependence of a certain Markovian type between claim sizes and interclaim times are contained as special cases.

Consider a sample of size n ⩾2 from a normal distribution with mean μ . In the average equivalence test the hypothesis | μ |> Δ is tested versus | μ |⩽ Δ . In this paper the critical value 0 t ( α ; s , n ) Δ of the average equivalence test is discussed, i.e. the hypothesis | μ |> Δ is rejected if the observed sample mean x satisfies | x | t ( α ; s , n ). Here s is the observed sample standard deviation and 0.5 α

Breast cancer screening is a topic of hot debate, and currently no general consensus has been reached on starting and ending ages and screening intervals, in part because of a lack of precise estimations of the benefit–harm ratio. Simulation models are often applied to account for the expected benefits and harms of regular screening; however, the degree to which the model outcomes are reliable is not clear. In a recent systematic review, we therefore aimed to assess the quality of published simulation models for breast cancer screening of the general population. The models were scored according to a framework for qualitative assessment. We distinguished seven original models that utilized a common model type, modelling approach, and input parameters. The models predicted the benefit of regular screening in terms of mortality reduction; and overall, their estimates compared well to estimates of mortality reduction from randomized controlled trials. However, the models did not report on the expected harms associated with regular screening. We found that current simulation models for population breast cancer screening are prone to many pitfalls; their outcomes bear a high overall risk of bias, mainly because of a lack of systematic evaluation of evidence to calibrate the input parameters and a lack of external validation. Our recommendations concerning future modelling are therefore to use systematically evaluated data for the calibration of input parameters, to perform external validation of model outcomes, and to account for both the expected benefits and the expected harms so as to provide a clear balance and cost-effectiveness estimation and to adequately inform decision-makers.

This note discusses the multiple wordlength assignment problem for the design of custom digital signal processing (DSP) parallel processors. It is demonstrated that this assignment problem is NP-hard.

We define the class of the so-called monotone constraint satisfaction problems (MON-CSP). MON-CSP forms a subclass of the class of min-closed (respectively, max-closed) constraint satisfaction problems of Jeavons and Cooper (Artificial Intelligence 79 (1995) 327). We prove that for all problems in the class MON-CSP there exists a very fast and very simple algorithm for testing feasibility. We then show that a number of well-known results from the literature are special cases of MON-CSP: (1) Satisfiability of Horn formulae; (2) graph homomorphisms to directed graphs with an [email protected]?-numbering; (3) monotone integer programming with two variables per inequality; (4) project scheduling under AND/OR precedence constraints. Our results provide a unified algorithmic approach to all these problems.

We consider a tandem fluid model with multiple consecutive buffers. The input of buffer j+1 is the output from buffer j, while the first buffer is fed by a, possibly infinite, number of independent homogeneous on-off sources. The sources have exponentially distributed silent periods and generally distributed active periods. Under the assumption that the input rate of one source is larger than the maximum output rate of the first buffer, we are able to characterize the output from each buffer. Due to this fact we find (i) an equation for the Laplace-Stieltjes transform of the marginal content distribution of any buffer j>=2, (ii) explicit expressions for corresponding moments, and (iii) an explicit expression for the correlation between two buffer contents, again from the second buffer on. These results make use of a key observation concerning the aggregate contents of several consecutive buffers. For the case in which the active periods of the sources are exponential, the Laplace-Stieltjes transform is inverted. If there is only one source, all results are also valid for the first buffer.

The confidence level of an inference table is defined as a weighted truth probability of the inference when sampling the reference set. The reference set is recognized by conditioning on the values of maximal partially ancillary statistics. In the sampling experiment values of incidental parameters are sampled from fiducial distributions. The concepts in this paper generalize ideas of Fisher's ‘Sampling the reference set’ (1961).

We consider multiple-server polling systems, in which each of the servers visits the queues according to its own cyclic schedule. Such systems appear to completely defy the derivation of exact waiting-time results, which motivates the search for accurate approximations. In the present paper, we derive waiting-time approximations for asymmetric systems with the exhaustive and gated service discipline. The approximations are tested for a wide range of parameter combinations.

In this paper we analyze stock allocation policies in general N-echelon distribution systems, where it is allowed to hold stock at all levels in the network. The goal is to achieve differentiated target customer service levels (fill rates). Various allocation rules and accompanying numerical methods that have already been developed for smaller networks are extended and compared in an extensive numerical experiment. We conclude that the extension of Balanced Stock rationing (see Van der Heijden (1996)) is the most accurate method, in particular in cases of relatively high imbalance. If the imbalance is not too high, the extension of Consistent Appropriate Share rationing (see De Kok et al., 1994; Verrijdt and De Kok, 1996) performs good as well.

In 1954, Johnson gave an efficient algorithm for minimizing makespan in a two-machine flow shop; there is no advantage to preemption in this case. McNaughton's wrap-around rule of 1959 finds a shortest preemptive schedule on identical parallel machines in linear time. A similarly efficient algorithm is unlikely to exist for the simplest common generalization of these problems. We show that preemptive scheduling in a two-stage flow shop with at least two identical parallel machines in one of the stages so as to minimize makespan is NP-hard in the strong sense.

We analyse the problem of executing periodic operations on a minimum number of identical processors under different constraints. The analysis is based on a reformulation of the problem in terms of graph colouring. It is shown that different constraints result in colouring problems defined on different classes of graphs, viz. interval graphs, circular-arc graphs and periodic-interval graphs. We discuss the complexity of these colouring problems in detail.

Local search has proven to be an effective solution approach for the traveling salesman problem. We consider variants of the TSP in which each city is to be visited within one or more given time windows. The travel times are symmetric and satisfy the triangle inequality; the objective is to minimize the tour duration. We develop efficient sequential and parallel algorithms for the verification of local optimality of a tour with respect to k-exchanges.

In this paper we consider a network with interactions by two users. Each of them repeatedly issues download requests on the network. These requests may be unsuccessful due to congestion or non-congestion-related errors. A user decides when to cancel a request (that is, what his impatience threshold is) and how long to wait before reissuing his request after cancellation of the previous request (that is, what his waiting time will be). This pair of impatience threshold and waiting time is his strategy. If a customer decides not to wait but to reissue his request immediately, that is, he sets his waiting time to zero, then he is said to use a so-called restart strategy. The goal of the user is to maximize the number of successful requests over a given time span.We study optimal strategies for the users in a game-theoretic framework. We find that in case congestion is the only cause of unsuccessful requests then each of the users will be very patient and any waiting time is optimal. Hence, restart strategies are among the optimal strategies. Second, in case non-congestion-related errors may occur, users will also set large impatience times, but now they will set waiting times to zero; in other words: they immediately reissue an unsuccessful download. In this case all optimal strategies are restart strategies. Hence, in both cases restart strategies are among the optimal strategies. Finally, implementing socially optimal strategies instead of individual optimal ones cannot improve the efficiency of the network usage.

We consider codes C for which the decoding regions for codewords c are balls B ρ ( c ), where ρ = r 1 or ρ = r 2 . These are called ( r 1 , r 2 )-error-correcting codes. If these balls are not only disjoint but also partition the space of all words, then C is called perfect. We are especially interested in codes with the property that centers of balls with the same radius r i are at least 2 r i + 2 apart ( i = 1, 2). These are called bipartite codes. Our main theorem states that a bipartite perfect ( r , 1)-error-correcting code with r ⩾ 2 must have r = 2 and in fact is obtained from a code with the parameters of a Preparata code.

We present an integrated packet/flow level model for WLAN performance analysis. It captures the statistical characteristics of the transmission of individual packets at the MAC layer, and includes the system dynamics due to the initiation and completion of data flow transfers. The processor sharing-based model is analytically tractable and yields a simple approximation for the expected flow transfer time. Extensive simulations show that the approximation is very accurate for a wide range of parameter settings.

We focus on a (two-node) tandem queue, fed by a large number of Gaussian inputs. With service rates and buffer sizes at both modes scaled appropriately, Schilder's sample-path large deviations theorem can be applied to calculate the asymptotics of the overflow probability of the second queue. More specifically, we derive a lower bound on the exponential decay rate of this overflow probability and present an explicit condition for the lower bound to match the exact decay rate. Examples show that this condition holds for a broad range of frequently used Gaussian inputs.

In the literature it is quite common to model TCP sources as Additive-Increase Multiplicative-Decrease sources. Within this framework we develop a Markov chain model that captures the interaction between the source and buffer processes. This approach permits to investigate a number of TCP related phenomena that are inherently stochastic. In the first place we evaluate two popular loss models: one in which sources react in a synchronized manner to loss, the other in which just one source reduces its window after loss epochs with a probability that is proportional to the source window. A comparison with a simulation in ns2 shows that the real loss process is somewhere in between the two loss models. Secondly, we show that the celebrated 'root p' law is still valid when the loss process is strictly dependent on the source state instead of an autonomous process, and the roundtrip times are stochastic instead of constant. Finally, we analyze the impact of source on/off behavior when the source on-times depend on momentary source transmission rates, as is the case in practice.

Processor sharing (PS) models for TCP behavior nicely capture the bandwidth sharing and statistical multiplexing effect of TCP flows on the flow level. However, these ‘rough’ models do not provide insight into the impact of packet-level parameters (such as round trip time and buffer size) on, e.g., throughput and flow transfer times. This paper proposes an integrated packet/flow-level model: it exploits the advantages of PS approach on the flow level and, at the same time, it incorporates the most significant packet-level effects.

We outline a system for supporting the modeling of physical distribution situations and the selection or construction of algorithms for their solution. The system will incorporate the current knowledge and expertise in vehicle routing. Its main contribution will be in the design and implementation of techniques for representing and manipulating this knowledge.

No abstract