Optimal ordering policies for a product that perishes in two periods subject to stochastic demand

This paper considers the problem of computing optimal ordering policies for a product that has a life of exactly two periods when demand is random. Initially costs are charged against runouts (stockouts) and outdating (perishing). By charging outdating costs according to the expected amount of outdating one period into the future, a feasible one period model is constructed. The central theorem deals with the n-stage dynamic problem and demonstrates the appropriate cost functions are convex in the decision variable and also provides bounds on certain derivatives. The model is then generalized to include ordering and holding costs. The paper is concluded with a discussion of the infinite horizon problem.     

Optimal location of a single service center of certain types

Hakimi has considered the problem of finding an optimal location for a single service center, such as a hospital or a police station. He used a graph theoretic model to represent the region being serviced. The communities are represented by the nodes while the road network is represented by the ares of the graph. In his work, the objective is one of minimizing the maximum of the shortest distances between the vertices and the service center. In the present work, the region being serviced is represented by a convex polygon and communities are spread over the entire region. The objective is to minimize the maximum of Euclidian distances between the service center and any point in the polygon. Two methods of solution presented are (i) a geometric method, and (ii) a quadratic programming formulation. Of these, the geometric method is simpler and more efficient. It is seen that for a class of problems, the geometric method is well suited and very efficient while the graph theoretic method, in general, will give only approximate solutions in spite of the increased efforts involved. But, for a different class of problems, the graph theoretic approach will be more appropriate while the geometric method will provide only approximate solutions though with ease. Finally, some feasible applications of importance are outlined and a few meaningful extensions are indicated.     

A branch and bound algorithm for the minimum storage‐time sequencing problem

The minimum storage‐time sequencing problem generalizes many well‐known problems in combinatorial optimization, such as the directed linear arrangement and the problem of minimizing the weighted sum of completion times, subject to precedence constraints on a single processor. In this paper we propose a new lower bound, based on a Lagrangian relaxation, which can be computed very efficiently. To improve upon this lower bound, we employ a bundle optimization algorithm. We also show that the best bound obtainable by this approach equals the one obtainable from the linear relaxation computed on a formulation whose first Chvàtal closure equals the convex hull of all the integer solutions of the problem. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 313–331, 2001     

The residual life of the renewal process: A simple algorithm

We develop a simple algorithm, which does not require convolutions, for computing the distribution of the residual life when the renewal process is discrete. We also analyze the algorithm for the particular case of lattice distributions, and we show how it can apply to an inventory problem. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 435–443, 1999     

A platform for initial testing of multiple camouflage patterns

The human visual system is still an important factor in military warfare; military personnel receive training on effective search strategies, and camouflage that can effectively conceal objects and personnel is a key component of a successful integrated survivability strategy. Previous methods of camouflage assessment have, amongst others, used psychophysics to generate distinctiveness metrics. However, the population from which the human observers are drawn is often not well defined, or necessarily appropriate. In this experiment we designed a new platform for testing multiple patterns based on a camouflaged object detection task, and investigate whether trained military observers perform better than civilians. We use a two-alternative forced choice paradigm, with participants searching images of woodland for a replica military helmet displaying Olive Green, Multi Terrain Pattern, US Marine Pattern or, as a conspicuous control, UN Peacekeeper Blue. Our data show that there is no difference in detection performance between the two observer groups but that there are clear differences in the effectiveness of the different helmet colour patterns in a temperate woodland environment. We conclude that when tasks involve very short stimulus presentation times, task-specific training has little effect on the success of target detection and thus this paradigm is particularly suitable for robust estimates of camouflage efficacy.     

Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel

We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP‐hard for any fixed number (≥2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two‐phase heuristics and dynamic two‐phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Optimization and mediated bartering models for ground delay programs

The Federal Aviation Administration (FAA) and the airline community within the United States have adopted a new paradigm for air traffic flow management, called Collaborative Decision Making (CDM). A principal goal of CDM is shared decision‐making responsibility between the FAA and airlines, so as to increase airline control over decisions that involve economic tradeoffs. So far, CDM has primarily led to enhancements in the implementation of Ground Delay Programs, by changing procedures for allocating slots to airlines and exchanging slots between airlines. In this paper, we discuss how these procedures may be formalized through appropriately defined optimization models. In addition, we describe how inter‐airline slot exchanges may be viewed as a bartering process, in which each “round” of bartering requires the solution of an optimization problem. We compare the resulting optimization problem with the current procedure for exchanging slots and discuss possibilities for increased decision‐making capabilities by the airlines. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006