Evaluating the effects of machine breakdowns in stochastic scheduling problems

In most of the stochastic resource-allocation problems discussed in the literature it is supposed that the key resource, herein called the machine, is continuously available until all tasks are completed. Plainly, this will often be an unrealistic assumption. This paper supposes that intermittent availability of the machine is due to a breakdown proces, and describes various approaches to the evaluation of the effect of breakdowns. Firstly, for the case of geometric up times, conditions are given under which breakdowns have no effect on optimal allocation strategies. Secondly, two different procedures are given which yield an upper bound on the loss incurred when a processing strategy is adopted under the assumption of no breakdowns, when in fact breakdowns do occur. The first of these is based on Gittins's indices and is described for the case of geometric up times, and the second uses a bounding argument on the breakdown process.     

Probabilistic partial set covering problems

In this article, we consider a situation in which a group of facilities need to be constructed in order to serve a given set of customers. However, the facilities cannot guarantee an absolute coverage to any of the customers. Hence, we formulate this problem as one of maximizing the total service reliability of the system subject to a budgetary constraint. For this problem, we develop and test suitable branch-and-bound algorithms and study the effect of problem parameters on solution difficulty. Some generalizations of this problem are also mentioned as possible extensions.     

Linear search with bounded resources

A point is placed at random on the real line according to some known distribution F, and a search is made for this point, beginning at some starting points s on the line, and moving along the line according to some function x(t). The objective of this article is to maximize the probability of finding the point while traveling at most d units. Characterizations of simple optimal searches are found for arbitrary distributions, for continuous distributions with continuous density everywhere (e.g., normal, Cauchy, triangular), and for continuous distributions with density which is continuous on its support (e.g., exponential, uniform). These optimal searches are also shown to be optimal for maximization of the expected number of points found if the points are placed on the line independently from a known distribution F.     

A note on optimal pricing for finite capacity queueing systems with multiple customer classes

This article investigates optimal static prices for a finite capacity queueing system serving customers from different classes. We first show that the original multi‐class formulation in which the price for each class is a decision variable can be reformulated as a single dimensional problem with the total load as the decision variable. Using this alternative formulation, we prove an upper bound for the optimal arrival rates for a fairly large class of queueing systems and provide sufficient conditions that ensure the existence of a unique optimal arrival rate vector. We show that these conditions hold for M/M/1/m and M/G/s/s systems and prove structural results on the relationships between the optimal arrival rates and system capacity. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

DEA models for two‐stage processes: Game approach and efficiency decomposition

Data envelopment analysis (DEA) is a method for measuring the efficiency of peer decision making units (DMUs). This tool has been utilized by a number of authors to examine two‐stage processes, where all the outputs from the first stage are the only inputs to the second stage. The current article examines and extends these models using game theory concepts. The resulting models are linear, and imply an efficiency decomposition where the overall efficiency of the two‐stage process is a product of the efficiencies of the two individual stages. When there is only one intermediate measure connecting the two stages, both the noncooperative and centralized models yield the same results as applying the standard DEA model to the two stages separately. As a result, the efficiency decomposition is unique. While the noncooperative approach yields a unique efficiency decomposition under multiple intermediate measures, the centralized approach is likely to yield multiple decompositions. Models are developed to test whether the efficiency decomposition arising from the centralized approach is unique. The relations among the noncooperative, centralized, and standard DEA approaches are investigated. Two real world data sets and a randomly generated data set are used to demonstrate the models and verify our findings. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008