The machine sequencing problem – review and extensions

The deterministic sequencing problem is reviewed from the points of view of variety, models, context, methodology, and current state of the art. The relationship between the theory of sequencing and other areas of control is illustrated with the relationship of sequencing to inventory. The “cyclical EMQ (Economical Manufacturing Quantities)” problem is discussed and new formulations are presented which promise a computationally feasible resolution of this outstanding problem.     

Geometry of the total time on test transform

Total time on test (TTT) plots provide a useful graphical method for tentative identification of failure distribution models. Identification is based on properties of the TTT transform. New properties of the TTT transform distribution are obtained. These results are useful to the user of TTT plots. Although IFR (DFR) distributions are particularly easy to identify from TTT plots, the user must exercise caution relative to identification of IFR A (DFRA) distributions.     

The U.S. versus the Soviet incentive models

This paper is concerned with models of the use of performance incentives in the Soviet Union and United States. The principal analytical result is an extension of an analysis of the methods whereby Soviet planners make the decision about production targets a variable under control of the producer, who is the only one possessing a knowledge of the uncertain condition of production. It is shown that this device can be viewed as a classical inventory problem. There is also an examination of the “U.S. incentive program” referring to multi-incentive contracts in which the profits received by the private producers are related to performance, outcome and cost. The analysis describes how this device can be extended to solve the target output selection problem of the Soviet planning system.     

Application of the stein-chen method for bounds and limit theorems in the reliability of coherent structures

The Stein-Chen method for establishing Poisson convergence is used to approximate the reliability of coherent systems with exponential-type distribution functions. These bounds lead to quite general limit theorems for the lifetime distribution of large coherent systems. © 1993 John Wiley & Sons, Inc.     

Two-agent scheduling with linear resource-dependent processing times

This paper considers a two-agent scheduling problem with linear resource-dependent processing times, in which each agent has a set of jobs that compete with that of the other agent for the use of a common processing machine, and each agent aims to minimize the weighted number of its tardy jobs. To meet the due date requirements of the jobs of the two agents, additional amounts of a common resource, which may be in discrete or continuous quantities, can be allocated to the processing of the jobs to compress their processing durations. The actual processing time of a job is a linear function of the amount of the resource allocated to it. The objective is to determine the optimal job sequence and resource allocation strategy so as to minimize the weighted number of tardy jobs of one agent, while keeping the weighted number of tardy jobs of the other agent, and the total resource consumption cost within their respective predetermined limits. It is shown that the problem is -hard in the ordinary sense, and there does not exist a polynomial-time approximation algorithm with performance ratio unless ; however it admits a relaxed fully polynomial time approximation scheme. A proximal bundle algorithm based on Lagrangian relaxation is also presented to solve the problem approximately. To speed up convergence and produce sharp bounds, enhancement strategies including the design of a Tabu search algorithm and integration of a Lagrangian recovery heuristic into the algorithm are devised. Extensive numerical studies are conducted to assess the effectiveness and efficiency of the proposed algorithms.     

The maximum collection problem with time-dependent rewards

We consider a routing problem where the objective is to maximize the sum of the rewards collected at the nodes visited. Node rewards are decreasing linear functions of time. Time is spent when traveling between pairs of nodes, and while visiting the nodes. We propose a penalty-based greedy (heuristic) algorithm and a branch-and-bound (optimal) algorithm for this problem. The heuristic is very effective in obtaining good solutions. We can solve problems with up to 20 nodes optimally on a microcomputer using the branch-and-bound algorithm. We report our computational experience with this problem. © 1996 John Wiley & Sons, Inc.     

Interactive optimization methodology for fleet scheduling

This article addresses the problem of scheduling the United States Navy's Atlantic Fleet to satisfy overseas strategic requirements. An integer programming formulation is developed but results in a model with prohibitive size. This fact and the qualitative nature of additional secondary objectives and constraints suggest an interactive optimization approach. A system that solves a natural relaxation of the integer program within an interactive environment is discussed.     

Optimal shift scheduling: A branch‐and‐price approach

We present a branch‐and‐price technique for optimal staff scheduling with multiple rest breaks, meal break, and break windows. We devise and implement specialized branching rules suitable for solving the set covering type formulation implicitly, using column generation. Our methodology is more widely applicable and computationally superior to the alternative methods in the literature. We tested our methodology on 365 test problems involving between 1728 and 86400 shift variations, and 20 demand patterns. In a direct comparison with an alternative method, our approach yields significant improvements both in cpu time and in the number of problem instances solved to optimality. The improvements were particularly marked for problems involving larger numbers of feasible shifts. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 185–200, 2000     

On the relationship between the force ratio and the instantaneous casualty-exchange ratio for some lanchester-type models of warfare

A “local” condition of winning (in the sense that the force ratio is changing to the advantage of one of the combatants) is shown to apply to all deterministic Lanchester-type models with two force-level variables. This condition involves the comparison of only the force ratio and the instantaneous force-change ratio. For no replacements and withdrawals, a combatant is winning “instantaneously” when the force ratio exceeds the differential casualty-exchange ratio. General outcome-prediction relations are developed from this “local” condition and applied to a nonlinear model for Helmbold-type combat between two homogeneous forces with superimposed effects of supporting fires not subject to attrition. Conditions under which the effects of the supporting fires “cancel out” are given.