A service center is a facility with multiple heterogeneous servers providing specialized service to multiple types of customers. An assignment policy specifies which server is enabled to serve which types of customer, and a routing policy specifies which server a customer will be routed to for service. Thus, a server can be enabled to serve many types of customer, and a customer may have many alternate servers who can serve him. This paper aims to provide decision models to determine optimal static assignment and routing policies, explicitly taking into account the stochastic fluctuations of demand along with the autocorrelations and cross-correlations of the different traffic streams. We consider several possible performance measures and formulate the optimization problem as a mixed integer nonlinear programming problem. We also develop an efficient heuristic algorithm to enhance scalability. Finally, we compare the different policies using the heuristic algorithms. We observe numerically that the routing policy tries to combine the negatively correlated traffic streams, and separate the positively correlated traffic streams.

Consider the setting of sparse graphs on N vertices, where the vertices have distinct “names”, which are strings of length O(log N) from a fixed finite alphabet. For many natural probability models, the entropy grows as c N log N for some model-dependent rate constant c. The mathematical content of this paper is the (often easy) calculation of c for a variety of models, in particular for various standard random graph models adapted to this setting. Our broader purpose is to publicize this particular setting as a natural setting for future theoretical study of data compression for graphs, and (more speculatively) for discussion of unorganized versus organized complexity.

This paper investigates extensions to feed-forward queueing networks of an algorithm to set staffing levels (the number of servers) to stabilize performance % at Quality of Service (QoS) targets in an Mt/GI/st+GI multi-server queue with a time-varying arrival rate. The model has a non-homogeneous Poisson process (NHPP), customer abandonment, and non-exponential service and patience distributions. For a single queue, simulation experiments showed that the algorithm successfully stabilizes abandonment probabilities and expected delays over a wide range of Quality-of-Service (QoS) targets. A limit theorem showed that stable performance at fixed QoS targets is achieved asymptotically as the scale increases (by letting the arrival rate grow while holding the service and patience distributions fixed). Here we extend that limit theorem to a feed-forward queueing network. However, these fixed QoS targets provide low QoS as the scale increases. Hence, these limits primarily support the algorithm with a low QoS target. For a high QoS target, effectiveness depends on the NHPP property, but the departure process never is exactly an NHPP. Thus, we investigate when a departure process can be regarded as approximately an NHPP. We show that index of dispersion for counts is effective for determining when a departure process is approximately an NHPP in this setting. In the important common case when all queues have high QoS targets, we show that both: (i) the departure process is approximately an NHPP from this perspective and (ii) the algorithm is effective.

The so called “Israeli Queue” is a single server polling system with batch service of an unlimited size, where the next queue to be visited is the one in which the first customer in line has been waiting for the longest time. The case with finite number of queues (groups) was introduced by Boxma, Van der Wal and Yechiali [3]. In this paper we extend the model to the case with a (possibly) infinite number of queues. We analyze the M/M/1, M/M/c, and M/M/1/N—type queues, as well as a priority model with (at most) M high-priority classes and a single lower priority class. In all models we present an extensive probabilistic analysis and calculate key performance measures.

Bootstrap percolation (BP) has been used effectively to model phenomena as diverse as emergence of magnetism in materials, spread of infection, diffusion of software viruses in computer networks, adoption of new technologies, and emergence of collective action and cultural fads in human societies. It is defined on an (arbitrary) network of interacting agents whose state is determined by the state of their neighbors according to a threshold rule. In a typical setting, BP starts by random and independent “activation” of nodes with a fixed probability p, followed by a deterministic process for additional activations based on the density of active nodes in each neighborhood (θ activated nodes). Here, we study BP on random geometric graphs (RGGs) in the regime when the latter are (almost surely) connected. Random geometric graphs provide an appropriate model in settings where the neighborhood structure of each node is determined by geographical distance, as in wireless ad hoc and sensor networks as well as in contagion. We derive bounds pc′, pc″ on the critical thresholds such that for all p > p″c full percolation takes place, whereas for p < p′c it does not. We conclude with simulations that compare numerical thresholds with those obtained analytically.

We consider a production–inventory control model with two reflecting boundaries, representing the finite storage capacity and the finite maximum backlog. Demands arrive at the inventory according to a Poisson process, their i.i.d. sizes having a common phase-type distribution. The inventory is filled by a production process, which alternates between two prespecified production rates ρ1 and ρ2: as long as the content level is positive, ρ1 is applied while the production follows ρ2 during time intervals of backlog (i.e., negative content). We derive in closed form the various cost functionals of this model for the discounted case as well as under the long-run-average criterion. The analysis is based on a martingale of the Kella–Whitt type and results for fluid flow models due to Ahn and Ramaswami.

In this paper, we study a two-queue polling model with zero switchover times and k-limited service (serve at most ki customers during one visit period to queue i, i=1, 2) in each queue. The arrival processes at the two queues are Poisson, and the service times are exponentially distributed. By increasing the arrival intensities until one of the queues becomes critically loaded, we derive exact heavy-traffic limits for the joint queue-length distribution using a singular-perturbation technique. It turns out that the number of customers in the stable queue has the same distribution as the number of customers in a vacation system with Erlang-k2 distributed vacations. The queue-length distribution of the critically loaded queue, after applying an appropriate scaling, is exponentially distributed. Finally, we show that the two queue-length processes are independent in heavy traffic.

In this paper we show how the permutation Monte Carlo method, originally developed for reliability networks, can be successfully adapted for stochastic flow networks, and in particular for estimation of the probability that the maximal flow in such a network is above some fixed level, called the threshold. A stochastic flow network is defined as one, where the edges are subject to random failures. A failed edge is assumed to be erased (broken) and, thus, not able to deliver any flow. We consider two models; one where the edges fail with the same failure probability and another where they fail with different failure probabilities. For each model we construct a different algorithm for estimation of the desired probability; in the former case it is based on the well known notion of the D-spectrum and in the later one—on the permutational Monte Carlo. We discuss the convergence properties of our estimators and present supportive numerical results.

We consider an optimal stopping problem for a general discrete-time process X1, X2, …, Xn, … on a common measurable space. Stopping at time n (n = 1, 2, …) yields a reward Rn(X1, …, Xn) ≥ 0, while if we do not stop, we pay cn(X1, …, Xn) ≥ 0 and keep observing the process. The problem is to characterize all the optimal stopping times τ, i.e., such that maximize the mean net gain:

$$E(R_\tau(X_1,\dots,X_\tau)-\sum_{n=1}^{\tau-1}c_n(X_1,\dots,X_n)).$$

In the particular case of Markov sequence X1, X2, … we estimate the stability of the optimal stopping problem under perturbations of transition probabilities.

We prove that several extensions of the classic Erlang loss function to non-integral numbers of servers are scalable: the blocking probability as described by the extension decreases when the offered load and the number of servers s are increased with the same relative amount, even when scaling up from integral s to non-integral s. We use this to prove that when several Erlang loss systems pool their resources for efficiency, various corresponding cooperative games have a non-empty core.

We introduce a level-crossing analysis of the finite time-t probability distributions of the excess life, age, total life, and related quantities of renewal processes. The technique embeds the renewal process as one cycle of a regenerative process with a barrier at level t, whose limiting probability density function leads directly to the time-t quantities. The new method connects the analysis of renewal processes with the analysis of a large class of stochastic models of Operations Research. Examples are given.

This paper carries out stochastic comparisons of series and parallel systems with independent and heterogeneous components in the sense of the hazard rate order, the reversed hazard rate order, and the likelihood ratio order. The main results extend and strengthen the corresponding ones by Misra and Misra [18] and by Ding, Zhang, and Zhao [8]. Meanwhile, the results on the hazard rate order of parallel systems and the reversed hazard order of series systems serve as nice supplements to Theorem 16.B.1 of Boland and Proschan [4] and Theorem 3.2 of Nanda and Shaked [20], respectively.

In Dynamic Programing, mixed strategies consist of randomizing the choice of actions. In some problems, such as portfolio management, it makes sense to diversify actions rather than choosing among them purely or randomly. Optimal betting in casinos and roulette by a gambler with fixed goal was studied by Dubins and Savage [9] and their school without the element of diversification (betting simultaneously on different holes of the roulette), once it was proved (Smith's theorem - Smith [16], Dubins [8] and Gilat and Weiss [10]) that diversification does not increase the probability of reaching the goal. We question the scope of this finding, that was based on the assumption that the holes on which gamblers can bet are disjoint, such as 1 and BLACK in regular roulette. A counter example is provided in which holes are nested, such as 1 and RED. Thus, it may be rational for gamblers with a fixed goal to place chips on more than one hole at the table.

This note is related to a joint work with Michèle Cohen on the preference for safety in the Choquet Expected Utility model.

Named after the French–Belgian mathematician Eugène Charles Catalan, Catalan's numbers arise in various combinatorial problems [12]. Catalan's triangle, a triangular array of numbers somewhat similar to Pascal's triangle, extends the combinatorial meaning of Catalan's numbers and generalizes them [1,5,11]. A need for a generalization of Catalan's triangle itself arose while conducting a probabilistic analysis of the Asymmetric Simple Inclusion Process (ASIP) — a model for a tandem array of queues with unlimited batch service [7–10]. In this paper, we introduce Catalan's trapezoids, a countable set of trapezoids whose first element is Catalan's triangle. An iterative scheme for the construction of these trapezoids is presented, and a closed-form formula for the calculation of their entries is derived. We further discuss the combinatorial interpretations and applications of Catalan's trapezoids.

Consider an absolutely continuous distribution on [0, ∞) with known mean μ, and hazard rate function, h satisfying, 0<a≤h(t)≤b<∞, for almost all t≥0. We derive the sharp range for σ2, under these constraints.

We consider the problem of controlling a two-server Markovian queueing system with heterogeneous servers. The servers are differentiated by their service rates and reliability attributes (i.e., the slower server is perfectly reliable, whereas the faster server is subject to random failures). The aim is to dynamically route customers at arrival, service completion, server failure, and server repair epochs to minimize the long-run average number of customers in the system. Using a Markov decision process model, we prove that it is always optimal to route customers to the faster server when it is available, irrespective of its failure and repair rates, if the system is stable. For the slower server, there exists an optimal threshold policy that depends on the queue length and the state of the faster server. Additionally, we analyze a variant of the main model in which there are multiple unreliable servers with identical service rates, but distinct reliability characteristics. For that case it is always optimal to route customers to idle servers, and the optimal policy is insensitive to the servers’ reliability characteristics.

This paper addresses a joint pricing and inventory control problem for a batch production system with random leadtimes. Assume that demand arrives according to a Poisson process with a price-dependent arrival rate. Each replenishment order contains a single batch of a fixed lot size. The replenishment leadtime follows an Erlang distribution, with the number of completed phases recording the delivery state of outstanding orders. The objective is to determine an optimal inventory-pricing policy that maximizes total expected discounted profit or long-run average profit. We first show that when there is at most one order outstanding at any point in time and that excess demand is lost, the optimal reorder policy can be characterized by a critical stock level and the optimal pricing decision is decreasing in the inventory level and delivery state. We then extend the analysis to mixed-Erlang leadtime distribution which can be used to approximate any random leadtime to any degree of accuracy. We further extend the analysis to allowing three outstanding orders where the optimal reorder point becomes state-dependent: the closer an outstanding order is to its arrival or the more orders are outstanding, the lower selling price is charged and the lower reorder point is chosen. Finally, we address the backlog case and show that the monotone pricing structure may not be true when the optimal reorder point is negative.

Let X1, …, Xn be non-negative, independent and identically distributed random variables with a common distribution function F, and denote by X1:n ≤ ··· ≤ Xn:n the corresponding order statistics. In this paper, we investigate the second-order regular variation (2RV) of the tail probabilities of Xk:n and Xj:n − Xi:n under the assumption that $\bar {F}$ is of the 2RV, where 1 ≤ k ≤ n and 1 ≤ i < j ≤ n.

Many modern networks grow from blocks. We study the probabilistic behavior of parameters of a blocks tree, which models several kinds of networks. It grows from building blocks that are themselves rooted trees. We investigate the number of leaves, depth of nodes, total path length, and height of such trees. We use methods from the theory of Pólya urns and martingales.

In this paper, we analyze the end-to-end delay performance of a tandem queueing system with mobile queues. Due to state-space explosion, there is no hope for a numerical exact analysis for the joint-queue-length distribution. For this reason, we present an analytical approximation that is based on queue-length analysis. Through extensive numerical validation, we find that the queue-length approximation exhibits excellent performance for light traffic load.