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     

Open shop scheduling to minimize the number of late jobs

We develop polynomial algorithms for several cases of the NP-hard open shop scheduling problem of minimizing the number of late jobs by utilizing some recent results for the open shop makespan problem. For the two machine common due date problem, we assume that either the machines or the jobs are ordered. For the m machine common due date problem, we assume that one machine is maximal and impose a restriction on its load. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 525–532, 1998     

Optimal control policies for a periodic review inventory system with emergency orders

We describe a periodic review inventory system where emergency orders, which have a shorter supply lead time but are subject to higher ordering cost compared to regular orders, can be placed on a continuous basis. We consider the periodic review system in which the order cycles are relatively long so that they are possibly larger than the supply lead times. Study of such systems is important since they are often found in practice. We assume that the difference between the regular and emergency supply lead times is less than the order-cycle length. We develop a dynamic programming model and derive a stopping rule to end the computation and obtain optimal operation parameters. Computational results are included that support the contention that easily implemented policies can be computed with reasonable effort. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 187–204, 1998     

An optimal structured policy for maintenance of partially observable aircraft engine components

This paper considers the maintenance of aircraft engine components that are subject to stress. We model the deterioration process by means of the cumulative jump process representation of crack growth. However, because in many cases cracks are not easily observable, maintenance decisions must be made on the basis of other information. We incorporate stress information collected via sensors into the scheduling decision process by means of a partially observable Markov decision process model. Using this model, we demonstrate the optimality of structured maintenance policies, which support practical maintenance schedules. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 335–352, 1998     

Variance of the number of units produced on a transfer line with buffer inventories during a period of length T

The transfer-line models in the literature are planning models rather than operational models. That is, they are very useful for planning or designing the transfer line, but are less useful for controlling the daily operation of the line. The performance measure used in these models is the efficiency of the line A. The expected number of units produced during a period of length T cycles is AT. In this article a procedure is presented for calculating the variance of the number of units produced by the transfer line during a period of length T cycles. These two performance measures can be used to construct an interval estimate for, say, the number of units produced during a shift. This interval estimate is an operational guide for the production manager.     

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.     

Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date

We consider a single-machine scheduling problem in which all jobs have the same due date and penalties are assessed for both early and late completion of jobs. However, earliness and tardiness are penalized at different rates. The scheduling objective is to minimize either the weighted sum of absolute deviations (WSAD) or the weighted sum of squared deviations (WSSD). For each objective we consider two versions of the problem. In the unconstrained version an increase in the due date does not yield any further decrease in the objective function. We present a constructive algorithm for the unconstrained WSAD problem and show that this problem is equivalent to the two-parallel, nonidentical machine, mean flow-time problem. For the unconstrained WSSD and the constrained WSAD and WSSD problems we propose implicit enumeration procedures based on several dominance conditions. We also report on our computational experience with the enumeration procedures.     

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.     

On the use of lexicographic min cost flows in evacuation modeling

Building evacuation problems can be represented as dynamic network-flow problems [3]. The underlying network structure of a building evolves through time yielding a time-expanded network (a dynamic network). Usually in such evacuation problems involving time, more than one objective function is appropriate. For example, minimizing the total evacuation time and evacuating a portion of the building as early as possible are two such objectives. In this article we show that lexicographical optimization is applicable in handling such multiple objectives. Minimizing the total evacuation time while avoiding cyclic movements in a building and “priority evacuation” are treated as lexicographical min cost flow problems.     

An approach to modeling electric utility capacity expansion planning

This article describes an algorithm for solving the static electric utility capacity expansion problem. The advantages of this algorithm are twofold. First, it is simpler and yet more efficient than previous algorithms for the same problem. Second, by making simplifying but realistic assumptions on plant sizes it is possible to use this algorithm for the case where one does not allow fractional plant additions. While the model has n variables, it has a clear two-dimensional geometric representation for understanding its properties, developing an algorithm, and interpreting the optimal solution. This algorithm has been implemented in the Intermediate Future Forecasting (IFFS) capacity expansion model at the Department of Energy.