Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Configuration Control File (CCF) production is very complex, thousands of code packages, data blocks and parameter values must be linked under many constraints including: Common data and code less than 8192 bytes Maximum of 5 registers per task All systems data must have common capabilities NP-complete problems are commonly known as knapsack or bin packing problems. They have no known algorithm which solves them in a time period bounded by a polynomial function of the number of inputs. Rules-of-thumb, or heuristics are the only practical approach to their solution. CCF segmentation to meet constraints discussed above is an example of Expert System technology applied to a classic NP-complete problem. Heuristics developed with traditional data processing techniques initially performed satisfactorily. However, as program development proceeded, Central Processor Unit (CPU) time for CCF production became a concern, both from a commitment of CPU resources and lost productivity. Traditional techniques failed to improve the heuristics and the project began to slip. Projected time to produce the CCF for a fully developed program was totally unacceptable, jeopardizing the project. Clearly another approach was required. Because existing heuristics were based on a concept of rules, research indicated an expert system using rules and a knowledge based approach had the highest probability of success. The paper emphasizes the development process of a knowledge based system from the perspective of the responsible project manager. The methodology is also applicable to common business problems.

REFERENCES

• a: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• b: S. Basse, Computer algorithms: introduction to design and analysis, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• c: Grogan, John R., Expert Systems Technology Guides RNTDS Segmentation. Sperry Technical Symposium, May 18-~, 1986.
• d: T. C. Hu , M. T. Shing , Y. S. Kuo, Combinatorial Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• e: Kimball, David B., Theoretical Limits to the CCFGEN Segmentation Algorithm. Unpublished Technical Paper, Unisys Technical Services Division, San Diego, CA

INDEX TERMS

Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Management, Theory