The LP/POMDP marriage: Optimization with imperfect information

A new technique for solving large‐scale allocation problems with partially observable states and constrained action and observation resources is introduced. The technique uses a master linear program (LP) to determine allocations among a set of control policies, and uses partially observable Markov decision processes (POMDPs) to determine improving policies using dual prices from the master LP. An application is made to a military problem where aircraft attack targets in a sequence of stages, with information acquired in one stage being used to plan attacks in the next. © 2000 John Wiley & Sons, Inc., Naval Research Logistics 47: 607–619, 2000     

Scheduling parallel dedicated machines with the speeding‐up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two‐machine problem is NP‐hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst‐case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple‐choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Discounted production scheduling and employment smoothing

We consider the problem of minimizing the sum of production, employment smoothing, and inventory costs over a finite number of time periods where demands are known. The fundamental difference between our model and that treated in [1] is that here we permit the smoothing cost to be nonstationary, thereby admitting a model with discounting. We show that the values of the instrumental variables are nondecreasing in time when demands are nondecreasing. We also derive some asymptotic properties of optimal policies.     

Dynamic multiattribute models for mixed manpower systems

This paper reviews a wide variety of manpower and personnel models of the goal programming variety. This is done from a strategy-oriented point of view addressing the problems of interest for immediate implementation as well as basic problems of manpower model research development. Particular emphasis in this paper is concerned with how analytical models can be brought to bear on the problems of combining military and civilian manpower into one management system. This includes a discussion of the computer support arrangements necessary to implement the models. First, we discuss an extension of multilevel models to provide an integrated approach to program planning which includes the dynamics of the manpower requirements-inventory relationships of mixed military-civilian manpower systems. Then, focus is given to some of the potential Navy applications particularly in terms of ways the outputs from the global multilevel model might be interfaced with assignment models for operational planning. The paper concludes with a discussion of static and dynamic multiattribute assignment models which operate on the individual man-job matching level. It is at this level of detail that dynamic mixed manpower systems might be constructed for use in equal employment opportunity planning and for local organization design studies.     

A note on the relationship between some specialized binary algorithms and the algorithm of land and doig

This note examines the relationship between several specialized binary algorithms and the pioneering work of Land and Doig. This relationship may provide new ideas which could enhance the effectiveness of these algorithms.     

An improved branch and bound procedure for n × m flow shop problems

This paper considers the classical nXm flow shop sequencing problem. An improved branch and bound procedure is proposed. Computational experience shows that the proposed procedure is more efficient compared to the existing optimizing procedures.     

Coordinated replenishments of items under time-varying demand: Dynamic programming formulation

We consider a group (or family) of items having deterministic, but time-varying, demand patterns. The group is defined by a setup-cost structure that makes coordination attractive (a major setup cost for each group replenishment regardless of how many of the items are involved). The problem is to determine the timing and sizes of the replenishments of all of the items so as to satisfy the demand out to a given horizon in a cost-minimizing fashion. A dynamic programming formulation is illustrated for the case of a two-item family. It is demonstrated that the dynamic programming approach is computationally reasonable, in an operational sense, only for small family sizes. For large families heuristic solution methods appear necessary.     

A complete importance ranking for components of binary coherent systems,with extensions to multi-state systems

Means of measuring and ranking a system's components relative to their importance to the system reliability have been developed by a number of authors. This paper investigates a new ranking that is based upon minimal cuts and compares it with existing definitions. The new ranking is shown to be easily calculated from readily obtainable information and to be most useful for systems composed of highly reliable components. The paper also discusses extensions of importance measures and rankings to systems in which both the system and its components may be in any of a finite number of states. Many of the results about importance measures and rankings for binary systems are shown to extend to the more sophisticated multi-state systems. Also, the multi-state importance measures and rankings are shown to be decomposable into a number of sub-measures and rankings.     

AN ALGORITHM FOR THE SEGREGATED STORAGE PROBLEM

The segregated storage problem involves the optimal distribution of products among compartments with the restriction that only one product may be stored in each compartment. The storage capacity of each compartment, the storage demand for each product, and the linear cost of storing one unit of a product in a given compartment are specified. The problem is reformulated as a large set-packing problem, and a column generation scheme is devised to solve the associated linear programming problem. In case of fractional solutions, a branch and bound procedure is utilized. Computational results are presented.