We study the variational problem that arises from consideration of large deviations for semimartingale reflected Brownian motion (SRBM) in the positive octant. Due to the difficulty of the general problem, we consider the case in which the SRBM has rotationally symmetric parameters. In this case, we are able to obtain conditions under which the optimal solutions to the variational problem are paths that are gradual (moving through faces of strictly increasing dimension) or that spiral around the boundary of the octant. Furthermore, these results allow us to provide an example for which it can be verified that a spiral path is optimal. For rotationally symmetric SRBM’s, our results facilitate the simplification of computational methods for determining optimal solutions to variational problems and give insight into large deviations behavior of these processes.
This paper studies a multiple-recipe predictive maintenance problem with M/G/1 queueing effects. The server degrades according to a discrete-time Markov chain and we assume that the controller knows both the machine status and the current number of jobs in the system. The controller’s objective is to minimize total discounted costs or long-run average costs which include preventative and corrective maintenance costs, holdings costs, and possibly production costs. An optimal policy determines both when to perform maintenance and which type of job to process. Since the policy takes into account the machine’s degradation status, such control decisions are known as predictive maintenance policies. In the single-recipe case, we prove that the optimal policy is monotone in the machine status, but not in the number of jobs in the system. A similar monotonicity result holds in the two-recipe case. Finally, we provide computational results indicating that significant savings can be realized when implementing a predictive maintenance policies instead of a traditional job-based threshold policy for PMs.
We consider the problem of staffing large-scale service systems with multiple customer classes and multiple dedicated server pools under joint quality-of-service (QoS) constraints. We first analyze the case in which arrival rates are deterministic and the QoS metric is the probability a customer is queued, given by the Erlang-C formula. We use the Janssen-Van Leeuwaarden-Zwart bounds to obtain asymptotically optimal solutions to this problem. The second model considered is one in which the arrival rates are not completely known in advance (before the server staffing levels are chosen), but rather are known via a probability distribution. In this case, we provide asymptotically optimal solutions to the resulting stochastic integer program, leveraging results obtained for the deterministic arrivals case.
With increasing worldwide competition, high technology manufacturing companies have to pay great attention to lower their production costs and guarantee high quality at the same time. Advanced process control (APC) is widely used in semiconductor manufacturing to adjust machine parameters so as to achieve satisfactory product quality. When there is a conflict between quality and scheduling objectives, quality usually has to be satisfied. This paper studies the interaction between scheduling and APC. A single-machine multiplejob- types makespan problem with APC constraints is proved to be NP-hard. For some special cases, optimal solutions are obtained analytically. In more general cases, the structure of optimal solutions is explored. An efficient heuristic algorithm based on these structural results is proposed and compared to an integer programming approach.
We develop a class of models to represent the dynamics of a virus spreading in a cellphone network, employing a taxonomy that includes five key characteristics. Based on the resulting dynamics governing the spread, we present optimization models to rapidly detect the virus, subject to resource limitations. We consider two goals, maximizing the probability of detecting a virus by a time threshold and minimizing the expected time to detection, which can be applied to all spread models we consider. We establish a submodularity result for these two objective functions that ensures that a greedy algorithm yields a well-known constant-factor (63%) approximation. We relate the latter optimization problem, under a specific virus-spread mechanism from our class of models, to a classic facility-location model. And, for the former objective function, we provide a sample-path optimization model that yields an asymptotically-optimal design for locating the detection devices, as the number of samples grows large. Finally, using call data from a large carrier, we estimate the degree distribution in a contact network, which is central to building random networks to study our models and solution methods.
We study a tandem queueing network with two stations, M heterogeneous flexible servers, and a finite intermediate buffer. The objective is to dynamically assign the servers to the stations in order to maximize the throughput of the system. The form of the optimal policy for M <= 3 was derived in two previous papers. In one of those papers, Andradottir and Ayhan (Operations Research, Vol. 53, pp. 516-531, 2005) provide a conjecture on the form of the optimal policy for M >= 4. We prove their conjecture in this paper, showing that the optimal policy is defined by monotone thresholds and the ratios of the service rates among the servers. For M > 1, we also prove that the optimal policy always uses the entire intermediate buffer.
We investigate a problem of admission control and pricing in a firm which dominates the market. In the model, there is a single server with exponential service times and arrivals follow a compound Poisson process where the number of customers in a group is an arbitrary discrete random variable. Each arriving group calculates the expected return for the whole group using the waiting cost per unit time, the current queue length, the price provided by the firm and the substitute product reward. It is assumed the firm is a monopoly and price maker per se. The firm’s problem is to set state dependent prices for arriving batches. Once the prices have been set we formulate the admission control problem for the firm, which is a Markov decision process. Properties of the pricing and value functions are characterized, as are the optimal admission policies for a revenue maximizing firm and a social optimizer.
This paper investigates a queueing system in which the controller can perform admission and service rate control. In particular, we examine a single server queueing system with Poisson arrivals and exponentially distributed services with adjustable rates. At each decision epoch the controller may adjust the service rate. Also, the controller can reject incoming customers as they arrive. The objective is to minimize long-run average costs which include: a holding cost, which is a non-decreasing function of the number of jobs in the system; a service rate cost c(x), representing the cost per unit time for servicing jobs at rate x; and a rejection cost for rejecting a single job. From basic principles, we derive a simple, efficient algorithm for computing the optimal policy. Our algorithm also provides an easily computable bound on the optimality gap at every step. Finally, we demonstrate that, in the class of stationary policies, deterministic stationary policies are optimal for this problem.
We introduce and investigate a new type of decision problem related to multiclass fluid networks. Optimization problems arising from fluid networks with known parameters have been studied extensively in the queueing, scheduling, and optimization literature. In this paper, we explore the makespan problem in fluid networks, with the assumption that the parameters are known only through a probability distribution. Thus the decision maker does not have complete knowledge of the parameters in advance. This problem can be formulated as stochastic nonlinear program. We provide necessary and sufficient feasibility conditions for this class of problems. We also derive a number of other structural results which can be used in developing effective computational procedures for solving stochastic fluid makespan problems.
Let Z be a two-dimensional Brownian motion confined to the non-negative quadrant by oblique reflection at the boundary. Such processes arise in applied probability as diffusion approximations for two-station queueing networks. The parameters of Z are a drift vector, a covariance matrix, and a ‘‘direction of reflection’’ for each of the quadrant’s two boundary rays. Necessary and sufficient conditions are known for Z to be a positive recurrent semimartingale, and those conditions are restated here in a novel form; they are the only restrictions imposed on the process data in our study. Under those minimal assumptions, a large deviations principle (LDP) is known to be valid for the stationary distribution of Z. For sufficiently regular sets B, the LDP says that the stationary probability of xB decays exponentially as x tends to infinity, and the asymptotic decay rate is the minimum value achieved by a certain function I(. ) over the set B. Avram, Dai and Hasenbein (2001) provided a complete and explicit solution for the large deviations rate function I(.). In this paper we re-express their solution in a simplified form, showing along the way that the computation of I(.) reduces to a relatively simple problem of least-cost travel between a point and a line.
Determination of the stability behavior of a queueing network is an important part of analyzing such systems. In Gamarnik and Hasenbein (2005) it is shown if a fluid network has the finite decomposition property (FDP) and is not weakly stable, then any queueing network associated with the fluid network is not rate stable. In that paper the FDP was demonstrated for two station queueing networks only. In this paper, we show that the property holds for certain classes of queueing networks with any number of stations, thus allowing one to completely analyze the global stability of such queueing networks via the fluid model.
This paper investigates stability behavior in a variant of a generalized Jackson queueing network. In our network, some customers use a join-the-shortest-queue policy when entering the network or moving to the next station. Furthermore, we allow interarrival and service times to have general distributions. For networks with two stations we derive necessary and sufficient conditions for positive Harris recurrence of the network process. These conditions involve only the mean values of the network primitives. We also provide counterexamples showing that more information on distributions and tie-breaking probabilities is needed for networks with more than two stations, in order to characterize the stability of such systems. However, if the routing probabilities in the network satisfy a certain homogeneity condition, then we show that the stability behavior can be explicitly determined, again using the mean value parameters of the network. A byproduct of our analysis is a new method for using the fluid model of a queueing network to show non-positive recurrence of a process. In previous work, the fluid model was only used to show either positive Harris recurrence or transience of a network process.
The fluid model has proven to be one of the most effective tools for the analysis of stochastic queueing networks, specifically for the analysis of stability. It is known that stability of a fluid model implies positive (Harris) recurrence (stability) of a corresponding stochastic queueing network, and weak stability implies rate stability of a corresponding stochastic network. These results have been established both for cases of specific scheduling policies and for the class of all work conserving policies. However, only partial converse results have been established and in certain cases converse statements do not hold. In this paper we close one of the existing gaps. For the case of networks with two stations we prove that if the fluid model is not weakly stable under the class of all work conserving policies, then a corresponding queueing network is not rate stable under the class of all work conserving policies. We establish the result by building a particular work conserving scheduling policy which makes the associated stochastic process transient. An important corollary of our result is that the condition rho* < 1, which was proven in a paper by Dai and VandeVate to be the exact condition for global weak stability of the fluid model, is also the exact global rate stability condition for an associated queueing network. Here rho* is a certain computable parameter of the network involving virtual station and push start conditions.
This paper proves that the stability region of a 2-station, 5-class reentrant queueing network, operating under a non-preemptive static buffer priority service policy, depends on the distributions of the interarrival and service times. In particular, our result shows that conditions on the mean interarrival and service times are not enough to determine the stability of a queueing network, under a particular policy. We prove that when all distributions are exponential, the works goes to infinity with time. We show that the same network with all interarrival and service times being deterministic is stable. When all distributions are uniform with a given range, our simulation studies show that the stability of the network depends on the width of the uniform distribution. Finally, we show that the same network, with deterministic interarrival and service times, is unstable when it is operated under the preemptive version of the static buffer priority service policy. Thus, our examples also demonstrate that the stability region depends on the preemption mechanism used. Keywords: multiclass, queueing network, reentrant line, stability, fluid model, virtual station, push start, large deviations estimate