Strategy selection: an info-gap methodology

The evaluation and selection of military strategy requires consideration of myriad factors – social, historical, political, geographical and technological – together with vast uncertainties encompassing all these domains. Info-gap decision theory is a conceptual framework that can support these deliberations and that has substantive implications for the formulation, evaluation and selection of strategic goals and of the means to attain them. In particular, while the analyst may desire to reliably achieve the best possible outcome, info-gap theory provides a critique of, and alternative to, the paradigm of optimizing the outcome of a decision. In selecting between strategy alternatives, the analyst must sometimes choose between one alternative that is purportedly better than another, but also more uncertain. Such a choice is a dilemma whose resolution requires the analyst to balance between the different predicted qualities of each alternative and their different vulnerabilities to uncertainty. The dilemma can be managed with the info-gap methodology of robustly satisfying critical requirements.     

Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is N P‐hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst‐case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two‐machine flow shop and the open shop problems with a single server are also shown to be N P‐hard in the strong sense. However, we reduce the two‐machine flow shop no‐wait problem with a single server to the Gilmore—Gomory traveling salesman problem and solve it in polynomial time. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304–328, 2000