Capacity improvement,penalties, and the fixed charge transportation problem

Capacity improvement and conditional penalties are two computational aides for fathoming subproblems in a branch‐and‐bound procedure. In this paper, we apply these techniques to the fixed charge transportation problem (FCTP) and show how relaxations of the FCTP subproblems can be posed as concave minimization problems (rather than LP relaxations). Using the concave relaxations, we propose a new conditional penalty and three new types of capacity improvement techniques for the FCTP. Based on computational experiments using a standard set of FCTP test problems, the new capacity improvement and penalty techniques are responsible for a three‐fold reduction in the CPU time for the branch‐and‐bound algorithm and nearly a tenfold reduction in the number of subproblems that need to be evaluated in the branch‐and‐bound enumeration tree. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 341–355, 1999     

Response surface analysis of two‐stage stochastic linear programming with recourse

We apply the techniques of response surface methodology (RSM) to approximate the objective function of a two‐stage stochastic linear program with recourse. In particular, the objective function is estimated, in the region of optimality, by a quadratic function of the first‐stage decision variables. The resulting response surface can provide valuable modeling insight, such as directions of minimum and maximum sensitivity to changes in the first‐stage variables. Latin hypercube (LH) sampling is applied to reduce the variance of the recourse function point estimates that are used to construct the response surface. Empirical results show the value of the LH method by comparing it with strategies based on independent random numbers, common random numbers, and the Schruben‐Margolin assignment rule. In addition, variance reduction with LH sampling can be guaranteed for an important class of two‐stage problems which includes the classical capacity expansion model. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 753–776, 1999     

Openshop scheduling under linear resources constraints

Consider n jobs (J₁, …, J_n), m working stations (M₁, …, M_m) and λ linear resources (R₁, …, R_λ). Job J_i consists of m operations (O_i1, …, O_im). Operation O_ij requires P_k(i, j) units of resource R_k to be realized in an M_j. The availability of resource R_k and the ability of the working station M_h to consume resource R_k, vary over time. An operation involving more than one resource consumes them in constant proportions equal to those in which they are required. The order in which operations are realized is immaterial. We seek an allocation of the resources such that the schedule length is minimized. In this paper, polynomial algorithms are developed for several problems, while NP-hardness is demonstrated for several others. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 51–66, 1998     

The open shop scheduling problem with a given sequence of jobs on one machine

The paper considers the open shop scheduling problem to minimize the make-span, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not allowed, the problem is NP-hard in the strong sense if the number of machines is variable, and is NP-hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5/4 times the optimal value. We also show that the two-machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 705–731, 1998     

Inventory management under random supply disruptions and partial backorders

We explore the management of inventory for stochastic-demand systems, where the product's supply is randomly disrupted for periods of random duration, and demands that arrive when the inventory system is temporarily out of stock become a mix of backorders and lost sales. The stock is managed according to the following modified (s, S) policy: If the inventory level is at or below s and the supply is available, place an order to bring the inventory level up to S. Our analysis yields the optimal values of the policy parameters, and provides insight into the optimal inventory strategy when there are changes in the severity of supply disruptions or in the behavior of unfilled demands. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 687–703, 1998     

Minimizing weighted mean absolute deviation of flow times in single machine systems

We discuss the problem of scheduling several jobs on a single machine with the objective of minimizing the weighted mean absolute deviation of flow times around the weighted mean flow time. We first show that the optimal schedule is W-shaped. For the unweighted case, we show that all optimal schedules are V-shaped. This characterization enables us to show that the problem is NP-hard. We then provide a pseudopolynomial algorithm for the unweighted problem. Finally, we consider three heuristic algorithms for the unweighted problem and report computational experience with these algorithms. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 297–311, 1998     

Forecast horizons for the discounted dynamic lot-size problem allowing speculative motive

This article considers the dynamic lot-size problem under discounting, allowing speculative motive for holding inventory. A variable rolling-horizon procedure is presented, which, under certain regularity conditions, is guaranteed to generate an infinite-horizon optimal-production plan. We also discuss a fixed rolling-horizon procedure which provides a production plan that achieves an infinite-horizon cost within a user-specified tolerance ϵ of optimality. The fixed-horizon length T* needed in this procedure is given in terms of a closed-form formula that is independent of specific forecasted demands. We also present computational results for problems with a range of cost parameters and demand characteristics.     

The validity of assumptions underlying current uses of Lanchester attrition rates

This study examines critically the various assumptions, results, and concepts that exist to date in the literature and scientific community concerning the relationships among the Lanchester, stochastic Lanchester, and the general renewal models of combat. Many of the prevailing understandings are shown to be erroneous.     

Facility location when demand is time dependent

In this article we investigate the problem of locating a facility among a given set of demand points when the weights associated with each demand point change in time in a known way. It is assumed that the location of the facility can be changed one or more times during the time horizon. We need to find the time “breaks” when the location of the facility is to be changed, and the location of the facility during each time segment between breaks. We investigate the minisum Weber problem and also minimax facility location. For the former we show how to calculate the objective function for given time breaks and optimally solve the rectilinear distance problem with one time break and linear change of weights over time. Location of multiple time breaks is also discussed. For minimax location problems we devise two algorithms that solve the problem optimally for any number of time breaks and any distance metric. These algorithms are also applicable to network location problems.