An implicit enumeration algorithm for the computer system configuration/expansion problem

Author

Richard S. Butturini

Date of Award

12-1983

Degree Type

Thesis

Degree Name

Master of Science

Major

Management Science

Major Professor

Kenneth C. Gilbert

Committee Members

Robert S. Garfinkel, Richard E. Rosenthal

Abstract

This paper introduces the Computer System Configuration/Expansion Problem (CSCEP), a combinatorial problem of selecting the hardware and software components of a computer system to provide the required capacity at a minimum cost. We present a general integer programming formulation of the problem and a method of solution based on the implicit enumeration procedure of Trotter and Shetty [23].

By exploiting the special structure of the CSCEP, we have developed a very efficient algorithm. Typically a hardware or software device will provide only one or two types of capacity (although it may consume many different types of capacity). This fact is the basis for efficient procedures for augmentation, computing objective function bounds and dynamically bounding variables in the CSCEP algorithm.

The algorithm was implemented with data derived from Oak Ridge Associated University's historical capacity requirements. Problems with 33 variables and 19 constraints were solved in core using a 32 kilobyte region on a PDP 11/34 minicomputer.

Recommended Citation

Butturini, Richard S., "An implicit enumeration algorithm for the computer system configuration/expansion problem. " Master's Thesis, University of Tennessee, 1983.
https://trace.tennessee.edu/utk_gradthes/14764