Discrete‐time analysis of MAP/PH/1 multiclass general preemptive priority queue

We use the matrix‐geometric method to study the MAP/PH/1 general preemptive priority queue with a multiple class of jobs. A procedure for obtaining the block matrices representing the transition matrix P is presented. We show that the special upper triangular structure of the matrix R obtained by Miller [Computation of steady‐state probabilities for M/M/1 priority queues, Oper Res 29(5) (1981), 945–958] can be extended to an upper triangular block structure. Moreover, the subblock matrices of matrix R also have such a structure. With this special structure, we develop a procedure to compute the matrix R. After obtaining the stationary distribution of the system, we study two primary performance indices, namely, the distributions of the number of jobs of each type in the system and their waiting times. Although most of our analysis is carried out for the case of K = 3, the developed approach is general enough to study the other cases (K ≥ 4). © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 662–682, 2003.     

Scheduling patients in an ambulatory surgical center

This paper presents a deterministic approach to schedule patients in an ambulatory surgical center (ASC) such that the number of postanesthesia care unit nurses at the center is minimized. We formulate the patient scheduling problem as new variants of the no‐wait, two‐stage process shop scheduling problem and present computational complexity results for the new scheduling models. Also, we develop a tabu search‐based heuristic algorithm to solve the patient scheduling problem. Our algorithm is shown to be very effective in finding near optimal schedules on a set of real data from a university hospital's ASC. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Optimal empty vehicle redistribution for hub‐and‐spoke transportation systems

This article considers the empty vehicle redistribution problem in a hub‐and‐spoke transportation system, with random demands and stochastic transportation times. An event‐driven model is formulated, which yields the implicit optimal control policy. Based on the analytical results for two‐depot systems, a dynamic decomposition procedure is presented which produces a near‐optimal policy with linear computational complexity in terms of the number of spokes. The resulting policy has the same asymptotic behavior as that of the optimal policy. It is found that the threshold‐type control policy is not usually optimal in such systems. The results are illustrated through small‐scale numerical examples. Through simulation the robustness of the dynamic decomposition policy is tested using a variety of scenarios: more spokes, more vehicles, different combinations of distribution types for the empty vehicle travel times and loaded vehicle arrivals. This shows that the dynamic decomposition policy is significantly better than a heuristics policy in all scenarios and appears to be robust to the assumptions of the distribution types. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Dynamic evacuation routes for personnel on a naval ship

We propose a dynamic escape route system for emergency evacuation of a naval ship. The system employs signals that adapt to the causative contingency and the crew's physical distribution about the ship. A mixed‐integer nonlinear programming model, with underlying network structure, optimizes the evacuation process. The network's nodes represent compartments, closures (e.g., doors and hatches) and intersections, while arcs represent various types of passageways. The objective function integrates two potentially conflicting factors: average evacuation time and the watertight and airtight integrity of the ship after evacuation. A heuristic solves the model approximately using a sequence of mixed‐integer linear approximating problems. Using data for a Spanish frigate, with standard static routes specified by the ship's designers, computational tests show that the dynamic system can reduce average evacuation times, nearly 23%, and can improve a combined measure of ship integrity by up to 50%. In addition, plausible design changes to the frigate yield further, substantial improvements. Published 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008     

Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work

We consider the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. We first discuss the approximability of the problem. We then develop two pseudo‐polynomial dynamic programming algorithms and a fully polynomial‐time approximation scheme for the problem. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 172–183, 2016     

Algorithm to solve a chance‐constrained network capacity design problem with stochastic demands and finite support

We consider the problem of determining the capacity to assign to each arc in a given network, subject to uncertainty in the supply and/or demand of each node. This design problem underlies many real‐world applications, such as the design of power transmission and telecommunications networks. We first consider the case where a set of supply/demand scenarios are provided, and we must determine the minimum‐cost set of arc capacities such that a feasible flow exists for each scenario. We briefly review existing theoretical approaches to solving this problem and explore implementation strategies to reduce run times. With this as a foundation, our primary focus is on a chance‐constrained version of the problem in which α% of the scenarios must be feasible under the chosen capacity, where α is a user‐defined parameter and the specific scenarios to be satisfied are not predetermined. We describe an algorithm which utilizes a separation routine for identifying violated cut‐sets which can solve the problem to optimality, and we present computational results. We also present a novel greedy algorithm, our primary contribution, which can be used to solve for a high quality heuristic solution. We present computational analysis to evaluate the performance of our proposed approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 236–246, 2016     

Capacity expansion and cost efficiency improvement in the warehouse problem

The warehouse problem with deterministic production cost, selling prices, and demand was introduced in the 1950s and there is a renewed interest recently due to its applications in energy storage and arbitrage. In this paper, we consider two extensions of the warehouse problem and develop efficient computational algorithms for finding their optimal solutions. First, we consider a model where the firm can invest in capacity expansion projects for the warehouse while simultaneously making production and sales decisions in each period. We show that this problem can be solved with a computational complexity that is linear in the product of the length of the planning horizon and the number of capacity expansion projects. We then consider a problem in which the firm can invest to improve production cost efficiency while simultaneously making production and sales decisions in each period. The resulting optimization problem is non‐convex with integer decision variables. We show that, under some mild conditions on the cost data, the problem can be solved in linear computational time. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 367–373, 2016     

Degeneracy in inventory models

In order‐quantity reorder‐point formulations for inventory items where backordering is allowed, some of the more common ways to prevent excessive stockouts in an optimal solution are to impose either a cost per unit short, a cost per stockout occasion, or a target fill rate. We show that these popular formulations, both exact and approximate, can become “degenerate” even with quite plausible parameters. By degeneracy we mean any situation in which the formulation either cannot be solved, leads to nonsensical “optimal” solutions, or becomes equivalent to something substantially simpler. We explain the reasons for the degeneracies, yielding new insight into these models, and we provide practical advice for inventory managers. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 686–705, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10037     

Rare‐event component importance for the consecutive‐k system

Various indices of component importance with respect to system reliability have been proposed. The most popular one is the Birnbaum importance. In particular, a special case called uniform Birnbaum importance in which all components have the same reliability p has been widely studied for the consecutive‐k system. Since it is not easy to compare uniform Birnbaum importance, the literature has looked into the case p = ½, p → 1, or p ≥ ½. In this paper, we look into the case p → 0 to complete the spectrum of examining Birnbaum importance over the whole range of p. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 159–166, 2002; DOI 10.1002/nav.10001     

Warranty reserves for nonstationary sales processes

Estimation of warranty costs, in the event of product failure within the warranty period, is of importance to the manufacturer. Costs associated with replacement or repair of the product are usually drawn from a warranty reserve fund created by the manufacturer. Considering a stochastic sales process, first and second moments (and thereby the variance) are derived for the manufacturer's total discounted warranty cost of a single sale for single‐component items under four different warranty policies from a manufacturer's point of view. These servicing strategies represent a renewable free‐replacement, nonrenewable free‐replacement, renewable pro‐rata, and a nonrenewable minimal‐repair warranty plans. The results are extended to determine the mean and variance of total discounted warranty costs for the total sales over the life cycle of the product. Furthermore, using a normal approximation, warranty reserves necessary for a certain protection level, so that reserves are not completely depleted, are found. Results and their managerial implications are studied through an extensive example. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 499–513, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10023