We study the performance of a M/DK/1 queue under Fair Sojourn Protocol (FSP). We use a Markov process with mixed real- and measure-valued states to characterize the queuing process of system and its related processor sharing queue. The infinitesimal generator of the Markov process is derived. Classifying customers according to their service time, using techniques in multiclass queuing system, and borrowing recently developed heavy traffic results for processor-sharing queues, we are able to derive approximations for average waiting time for the jobs.

In this article we study the commute and hitting times of simple random walks on spherically symmetric random trees in which every vertex of level n has outdegree 1 with probability 1−qn and outdegree 2 with probability qn. Our argument relies on the link between the commute times and the effective resistances of the associated electric networks when 1 unit of resistance is assigned to each edge of the tree.

In this article we study the joint optimization of finished goods inventory and pricing in a make-to-stock production system with long-run average profit criterion. The production time is random with controllable rate and the demand is Markovian with rate depending on the sale price. The objective is to dynamically adjust the production rate and the sale price to maximize the long-run average profit. We obtain the optimal dynamic pricing and production control policy and present an efficient bisection algorithm for computing the policy parameters.

As a model for streaming multimedia applications, we study an unreliable retrial queue with infinite-capacity orbit and normal queue for which the retrial rate and the server repair rate are controllable. Customers join the retrial orbit if and only if their service is interrupted by a server failure. Interrupted customers do not rejoin the normal queue but repeatedly attempt to access the server at independent and identically distributed intervals until it is found functioning and idle. We provide stability conditions, queue length distributions, stochastic decomposition results, and performance measures. The joint optimization of the retrial and server repair rates is also studied.

A random intersection graph is constructed by assigning independently to each vertex a subset of a given set and drawing an edge between two vertices if and only if their respective subsets intersect. In this article a model is developed in which each vertex is given a random weight and vertices with larger weights are more likely to be assigned large subsets. The distribution of the degree of a given vertex is characterized and is shown to depend on the weight of the vertex. In particular, if the weight distribution is a power law, the degree distribution will be as well. Furthermore, an asymptotic expression for the clustering in the graph is derived. By tuning the parameters of the model, it is possible to generate a graph with arbitrary clustering, expected degree, and—in the power-law case—tail exponent.

We consider a single-server Markovian queue with synchronized services and setup times. The customers arrive according to a Poisson process and are served simultaneously. The service times are independent and exponentially distributed. At a service completion epoch, every customer remains satisfied with probability p (independently of the others) and departs from the system; otherwise, he stays for a new service. Moreover, the server takes multiple vacations whenever the system is empty.

Some of the transition rates of the underlying two-dimensional Markov chain involve binomial coefficients dependent on the number of customers. Indeed, at each service completion epoch, the number of customers n is reduced according to a binomial (n, p) distribution. We show that the model can be efficiently studied using the framework of q-hypergeometric series and we carry out an extensive analysis including the stationary, the busy period, and the sojourn time distributions. Exact formulas and numerical results show the effect of the level of synchronization to the performance of such systems.

We study the value of multistage advance demand information (MADI) in a production system in which customers place an order in advance of their actual need, and each order goes through multiple stages before it becomes due. Any order that is not immediately filled at its due date will be backordered. The producer must decide whether or not to produce based on real-time information regarding current and future orders. We formulate the problem as a Markov decision process and analyze the impact of the demand information on the production policy and the cost. We show that the optimal production policy is a state-dependent base-stock policy, and we show that it has certain monotonicity properties. We also introduce a simple heuristic policy that is significantly easier to compute and that inherits the structural properties of the optimal policy. In addition, we show that its base-stock levels bound those of the socially optimal policy. Numerical study identifies the conditions under which MADI is most beneficial and shows that the heuristic performs almost as well as the optimal policy when MADI is most beneficial.

We investigate the presence and impact of forecast errors in the arrival rate of customers to a service system. Analysis of a large dataset shows that forecast errors can be large relative to the fluctuations naturally expected in a Poisson process. We show that ignoring forecast errors typically leads to overestimates of performance and that forecast errors of the magnitude seen in our dataset can have a practically significant impact on predictions of long-run performance. We also define short-run performance as the random percentage of calls received in a particular period that are answered in a timely fashion. We prove a central limit theorem that yields a normal-mixture approximation for its distribution for Markovian queues and we sketch an argument that shows that a normal-mixture approximation should be valid in great generality. Our results provide motivation for studying staffing strategies that are more flexible than the fixed-level staffing rules traditionally studied in the literature.

In this article, we develop a simple method to approximate the transient behavior of queueing systems. In particular, it is shown how singularity analysis of a known generating function of a transient sequence of some performance measure leads to an approximation of this sequence. To illustrate our approach, several specific transient sequences are investigated in detail. By means of some numerical examples, we validate our approximations and demonstrate the usefulness of the technique.

Recent advances in the mathematical analysis of flow control have prompted the creation of the Scalable TCP (STCP) and Exponential RED (E-RED) algorithms. These are designed to be scalable under the popular deterministic delay stability modeling framework. In this article, we analyze stochastic models of STCP and STCP combined with E-RED link behavior. We find that under certain plausible network conditions, these probabilistic models also exhibit scalable behavior. In particular, we derive parameter choice schemes for which the equilibrium coefficients of variation of flow rates are bounded, however large, fast, or complex the network. Our model is shown to exhibit behavior similar to the mean field convergence that has recently been observed in TCP.

We consider the problem of routing calls dynamically in a multiskill call center. Calls from different skill classes are offered to the call center according to a Poisson process. The agents in the center are grouped according to their heterogeneous skill sets that determine the classes of calls they can serve. Each agent group serves calls with independent exponentially distributed service times. We consider two scenarios. The first scenario deals with a call center with no buffers in the system, so that every arriving call either has to be routed immediately or has to be blocked and is lost. The objective in the system is to minimize the average number of blocked calls. The second scenario deals with call centers consisting of only agents that have one skill and fully cross-trained agents, where calls are pooled in common queues. The objective in this system is to minimize the average number of calls in the system. We obtain nearly optimal dynamic routing policies that are scalable with the problem instance and can be computed online. The algorithm is based on one-step policy improvement using the relative value functions of simpler queuing systems. Numerical experiments demonstrate the good performance of the routing policies. Finally, we discuss how the algorithm can be used to handle more general cases with the techniques described in this article.

Numerous examples of real-time services arise in the service industry that can be modeled as loss systems. These include agent staffing for call centers, provisioning bandwidth for private line services, making rooms available for hotel reservations, and congestion pricing for parking spaces. Given that arriving customers make their decision to join the system based on the current service price, the manager can use price as a mechanism to control the utilization of the system. A major objective for the manager is then to find a pricing policy that maximizes total revenue while meeting the quality of service targets desired by the customers. For systems with growing demand and service capacity, we provide a dynamic pricing algorithm. A key feature of our solution is congestion pricing. We use demand forecasts to anticipate future service congestion and set the present price accordingly.

We consider a Markovian stochastic fluid flow model in which the fluid level has a lower bound zero and a positive upper bound. The behavior of the process at the boundaries is modeled by parameters that are different than those in the interior and allow for modeling a range of desired behaviors at the boundaries. We illustrate this with examples. We establish formulas for several time-dependent performance measures of significance to a number of applied probability models. These results are achieved with techniques applied within the fluid flow model directly. This leads to useful physical interpretations, which are presented.

We consider a two-queue model with state-dependent setups, in which a single server alternately serves the two queues. The high-priority queue is served exhaustively, whereas the low-priority queue is served according to the k-limited strategy. A setup at a queue is incurred only if there are customers waiting at the polled queue. We obtain the transforms of the queue length and sojourn time distributions under the assumption of Poisson arrivals, generally distributed service times, and generally distributed setup times. The interest for this model is fueled by an application in the field of logistics. It is shown how the results of this analysis can be applied in the evaluation of a stochastic two-item single-capacity production system. From these results we can conclude that significant cost reductions are possible by bounding the production runs of the low-priority item, which indicates the potential of the k-limited service discipline as priority rule in production environments.

Digital-to-analog converters (DAC) transform signals from the abstract digital domain to the real analog world. In many applications, DACs play a crucial role. Due to variability in the production, various errors arise that influence the performance of the DAC. We focus on the current errors, which describe the fluctuations in the currents of the various unit current elements in the DAC. A key performance measure of the DAC is the Integrated Nonlinearity (INL), which we study in this article. There are several DAC architectures. The most widely used architectures are the thermometer and the binary and the segmented architectures. We study the two extreme architectures, namely the thermometer and the binary architectures. We assume that the current errors are independent and identically normally distributed and reformulate the INL as a functional of a Brownian bridge. We then proceed by investigating these functionals. For the thermometer case, the functional is the maximal absolute value of the Brownian bridge, which has been investigated in the literature. For the binary case, we investigate properties of the functional, such as its mean, variance, and density.