Some order relations in closed networks of queues with multiserver stations

Consider a closed network of queues of the “product-form” type, where each station has s servers (s ≥ 1 is identical for all stations). We show that the throughput function of the network is Schur concave with respect to the loading of the stations and arrangement increasing with respect to the assignment of server groups. Consequently, different loading/assignment policies can be compared under majorization/arrangement orderings and their relative merits decided according to the yields of throughput. The results can be used to support planning decisions in computer and production systems which are modeled as closed networks of queues.     

A periodic maintenance model with used equipment and random minimal repair

The maintenance strategy considered in this article is in the class of block replacement policies. The working unit is replaced by new ones at instants T,2T,3T,… independently of the age and state of the unit. If a failure occurs between these instants, the random repair cost is evaluated. If it is smaller than a predetermined control limit then a minimal repair is carried out. Otherwise the unit is replaced by a used unit. The performance of this maintenance strategy is evaluated in terms of average total cost per time unit over an infinite time span. The mathematical model is defined and several analytical results are obtained. A computer program has been written, which solves the mathematical problem, and some examples are given for the cases where the underlying life distribution is gamma, Weibull or truncated normal.     

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     

An index policy for a stochastic scheduling model with improving/deteriorating jobs

We consider stochastic scheduling models which have the natural character that jobs improve while being processed, but deteriorate (and may possibly leave the system altogether) while processing is diverted elsewhere. Such restless bandit problems are shown to be indexable in the sense of Whittle. A numerical study which elucidates the strong performance of the resulting index policy is complemented by a theoretical study which demonstrates the optimality of the index policy under given conditions and which develops performance guarantees for the index heuristic more generally. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 706–721, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10036