Septemb
`pete:aBegree 1
`
`
`
`NUD ae-84 (1995)
`N 0166-3615
`
`gOMPUTERSIN.
`
`al ii.
`Aninternationalapplicationorientedresearch|Ne
`
`
`
`iheyaR
`
`
` Editor: Prof. H. Wortmann
`1g eee
`a,tte
`7 ane |
`
`
`on
`*
`‘AyBEER.
`i Bae.
`
`
`
`
`*"
`
`
`
`
`
`1
`
`CONFIGIT 1036
`
`CONFIGIT 1036
`
`1
`
`

`

`~—e¥esSes
`
`1
`
`at
`
`ee
`|
`i)
`
`COMPUTERS IN
`INDUSTRY
`
`4!
`
`Volume 27, 1995
`
`Editor-in-Chief
`Hans Wortmann
`
`Co-editor North America
`Colin L. Moodie
`
`Co-editor Industrial Acquisitions
`Gloria Karlmark
`
`
`
`Amsterdam — Lausanne — New York — Oxford — Shannon — Tokyo
`
`2
`
`

`

`
`
`
`camsee ees
`
`
`ELSEVIER
`
`Computersin Industry 27 (1995) 3-21
`‘‘
`
`
`
`COMPUTERSIN
`INDUSTRY
`
`
`Configuring computer systems through constraint-based modeling
`and interactive constraint satisfaction
`S.M. Fohn > U.S. Liau **, A.R. Greef >, R.E. Young *, P.J. O’Grady *
`
`* Group for Intelligent Design in Manufacturing, DepartmentofIndustrial Engineering, North Carolina State University, Raleigh, NC
`27695-7906, USA
`> BM Corporation, NetworkApplication Services Division, Thornwood, NY10594, USA
`Received 22 November 1993; revised 22 September 1994
`
`Abstract
`
`is ensuring that the products ordered by a
`A major problem in the computer industry, as with many other industries,
`customer are viable products and that they can be delivered at the quoted price. The inability of companies to solvethis
`problem results in an enormous expense for a company. In this paper we present an approachto solving this problem in the
`computer industry through constraint-based modeling and interactive constraint satisfaction. PC/CON, a Personal Computer
`Configuration System, has been built within a computer-based environment called Saturn. The development of pc/con and
`related work is discussed. Saturn’s architecture is presented and an example session with pc/CON is demonstrated. We show
`how Saturn and pc/con have the features and capabilities necessary to support the extremely large variety of products and
`to support the maintenance of a configuration system for a rapidly and continuously changing product line. This approach
`would also appear to be applicable to other industries where there is a wide product variety.
`
`Keywords: Computer configuration; Interactive constraint modeling; Constraint-based reasoning; Concurrent engineering
`
`1. Introduction
`
`A major problem in the computer industry, as
`with many other industries,
`is ensuring that
`the
`products ordered by a customer are viable products
`and that they can be delivered at the quoted price.
`The computers must be configured so that they can
`be readily manufactured and that they can support
`the desired software. The software must be config-
`ured for compatibility between hardware and other
`software so as to achieve good performance. Al-
`
`* Corresponding author.
`
`though a seemingly structured problem, the variety
`of options available for a computer system allows for
`billions of feasible product configurations making
`this problem difficult to solve consistently.
`Trilogy [1] estimates that in the personal computer
`(PC) industry, between 30 and 85 percent of all
`orders are incorrectly configured. The result is an
`enormous expense for a company, especially’ when
`realizing that infeasible product configurations made
`at the point of sale may only be discovered much
`later in manufacturing, or, worse yet, after delivery
`to the customer. The consequences of late discovery
`include having to change a customer’s order (thereby
`delaying manufacturing and increasing the lead-time),
`
`0166-3615/95/$09.50 © 1995 Elsevier Science B.V. All rights reserved
`SSDI 0166-3615(94)00041-7
`
`
`
`3
`
`

`

` 4
`
`S.M. Fohn et al. / Computers in Industry 27 (1995) 3-27
`
`taking it beyond the bounds of human ability to
`solve.
`A. system that solves the computer configuration
`problem must address these issues.
`We present an approach that addresses the issues
`and solves the computer product configuration prob-
`lem in the computer industry through constraint-based
`modeling and
`interactive
`constraint
`satisfaction,
`**Computer Product Configuration’’ is defined as the
`generation of a computer hardware and software
`configuration that meets the price and performance
`constraints imposed by a customer, and the compat-
`bility constraints between hardware and software.
`This approach aims at avoiding the cycling between
`a manufacturer and its customers and focuses on
`interactively assisting order taking from a diverse
`clientele. It furthermore is capable of supporting a
`diverse number of personnel in fields snch as mann-
`facturing and marketing all of whom have an interest
`in computer prodnct confignration. Ta accommodate
`this approach, we also introdnce a Constraint Model-
`ing System called Saturn, which is an interactive
`constraint satisfaction system that can be used to
`implement a computer configuration system. Saturn
`implements a logic-based, ATMS-supported, interac-
`tive constraint satisfaction system tightly coupled
`with a relational database [5]. It has a spreadsheet-like
`development
`interface that,
`in conjunction with a
`database manager, facilitates the construction of a
`constraint-based model representing a productline of
`feasible computer hardware configurations,
`sup-
`ported software configurations, and pricing informa-
`tion.
`
`the development of a computer
`In this paper,
`product configuration system is discussed, beginning
`with the salient featnres and capabilities that a com-
`puter-snpport environment for computer configura-
`tion should have. Next the related work on configu-
`ration systems that have addressed similar problems
`are presented and compared to our constraint model-
`ing approach. Thisis followed by a discussion on the
`nature of the computer prodnct configuration prob-
`lem and a brief description of Saturn’s architecture.
`In this context, the implementation of pc/con, which
`is a personal computer configuration system built
`within Saturn, as a constraint-based model is shown.
`An example session with pc/con is then described
`to show how Satnm’s interactive constraint satisfac-
`
`forcing a customer to retum a shipment of faulty
`orders, and the loss of sales. Furthermore, products
`that are incorrectly configured are most likely incor-
`rectly quoted. As a result, a manufacturer may be
`required to give away free components which were
`omitted from the sales quote yet are needed to
`supply the customer with the promised functionality.
`The costs involved, both monetary and the loss of
`customer good will, can be very high.
`In order to reduce the impact from the sale of
`infeasible products, companies have attempted to
`incinde product configuration checks both at
`the
`point of sale and between the point of sale and start
`of mannfacture, Configuration checking is performed
`either manually or automatically by computer pro-
`prams. Programs like xsEL [2] and Trilogy [1] check
`orders at the point of sale while xcon [3] and Proof-
`Plan [4] check orders after a sale and before manu-
`facture. The effectiveness of point-of-sale checking
`is dependent on the experience of the sales represen-
`tatives and on the variety of the customers. An
`inexperienced sales representative dealing with a
`large number of different concerns from a diverse
`clientele may not be able to answer all questions
`immediately. This results in postponing sales until
`more information can be gathered to address the
`needs of a client. With post-sale checking, any de-
`tected configuration conflicts are resolved by calling
`customers and essentially cycling back to the point
`of sale before a valid work order is released to
`mannfacturing. This cyclic approach can have a neg-
`ative affect on a customer who is forced to endnre
`long lead times,
`frustrating product configuration
`changes, and the prospect of returning products that
`do not meet customer expectations.
`The computer product configuration problem can
`therefore be summarized as follows:
`+ 30% to 85% of all orders are incorrectly config-
`ured,
`:
`+ Late discovery of configuration errors increases
`mannfacturing lead times and produces incorrect
`orders.
`
`* Configuration errors can result im a loss of confi-
`dence by customers and can result
`in a loss of
`sales.
`
`-
`
`Incomectly configured products can be quoted
`inaccurately.
`-
`> The confignration problem can be very large,
`
`4
`
`

`

`SM. Fohn et al. f Computers in Industry 27 (1995) 3-21
`
`tion capabilities are harnessed by PC/CON to perform
`PC configuration. Finally,
`it is shown how Saturn
`and pC/ CON have the features and capabilities neces-
`sary to support computer product configuration and
`to support the maintenance of a configuration system
`for a rapidly and continuously changing productline.
`
`2. Embracing the task of computer product cou-
`figuration
`
`Product configuration is a critical yet a complex
`task in most industries. This is particularly true for
`the computer industry. To deliver a viable product,
`the computers not only need to meet the customers’
`functional reqnirements, they also must be config-
`ured so that they can be readily manufactured and
`they possess compatibility between hardware compo-
`nents and between hardware and the desired soft-
`ware. Althongh a seemingly structured problem, the
`variety of options available for a computer system
`allows for billions of feasible product configurations,
`making this problem difficult to consistently solve.
`As an illustration, we explore the computer product
`configuration problem in the personal computer (PC)
`industry. Compared to a supercomputer or a mini-
`computer, a PC typically has a simpler operating
`system, a smaller amount of memory and primary
`storage space, limited input and output devices, and
`is a single user system. However, as we will show,
`the prodnet configuration problem for a PCis still a
`complex and challenging task.
`In earlier years, manual PC prodnct configuration
`was Viable. This is readily seen by examining the
`number of feasible hardware configurations possible
`for the IBM model 25, with an 8086 8 MHz proces-
`sor and an 8bit PC bus architecture. This machine
`had only 240 feasible configurations and could run
`all software products. Today, consistently configur-
`ing PC orders manually is nearly impossible. The
`IBM model 95, with an 80486 33 MHz processor and
`a 32 bit MCA bus architecture has 467 billion feasi-
`ble hardware configurations without considering any
`of the 115 cards that could plug into any of the 8
`slots in its backplane. Table 1 contains the number of
`feasible product configurations for the PS/2 product
`line for 1991/1992 and for 1993. The numbers are
`compnted from [6] and[7].
`
`Table 1
`The numberof feasible configurations for the PS/2 product line
`Model
`Numberof configurations
`1991/1992
`1993
`
`25-086
`25-286
`30
`35
`55
`56
`57
`70
`80
`90
`95
`
`Total
`
`240
`768
`21,760
`145,317,888
`835,584
`235,929,600
`115,605,504
`258,048
`23,181,312
`5,138,022,400
`31,085,035,520
`
`240
`768
`11,520
`238,132,224
`2,151,552
`2,615,328,768
`308,625,408
`1,347,840
`131,843,712
`2,082,103,296
`467,362,415,520
`
`36,744,208,624
`
`472,741,960,848
`
`From the table, we can see that the number of
`configurations increased by more than 400 billion im
`just one year. The explosion of software products
`and their inherent incompatibility problems and plat-
`form-specific requirements has added to the com-
`plexity of computer product configuration. Com-
`pounding the problem is the weekly release of new
`products and changes to existing products. Major
`product introductions that require significant restruc-
`turing of the entire PC model line are now occurring
`in a Jmonth cycle. In the PC imdustry it is not only
`essential to support the task of PC product configura-
`tion but also to support the development and mainte-
`nance of the information upon which that support is
`based. This calls for a configuration environment
`that can accommodate growing product complexity
`stemming from technological progress and from con-
`sumer demand.
`To meet
`this challenge we consider computer
`product configuration to be a highly interactive,
`non-monotonic, step-wise process. A user can spec-
`ify any permutation of product/price attribute val-
`ues. The output is made up of consistent values for
`locally related attributes whose values were previ-
`ously unspecified or of feedback information for
`resolving inconsistent partial configurations. Onceall
`of the attributes have values and there are no incon-
`sistencies among them, the computer product config-
`uration is a valid working product that can be readily
`manufactured.
`
`
`
`
`
`
`
`5
`
`

`

`SM. Fohn et al. / Computersin Industry 27 (1995) 3-21
`
`This research is focused on embracing the task of
`computer product configuration with respect to two
`aspects of the problem. First, is the development of a
`computer tool that allows product configuration sys-
`tems to be built by non-specialists and exercised by
`personnel with diverse skills. Second, is the creation
`of a model that can represent the complex interrela-
`tionships among its elements while retaining an or-
`ganizational simplicity such that people with no spe-
`cific training in a computer-related field can perform
`development, maintenance, and expansion. The em-
`phasis placed on the above research topics are a
`response to the new character of contemporary,
`highly volatile markets and have not yet been ad-
`dressed by other researchersin the field.
`
` 6
`
`complex interrelationships among the elements of
`the model while retaining an organizational simplic-
`ity such that people with no specific training in a
`computer-related field can perform development,
`maintenance, and expansion. These are capabilities
`that we consider
`to be of prime importance for
`application in the computer industry.
`XSEL and Trilogy somewhat support computer-
`product configuration as outlined in Section 2 in that
`they are employed at the point of sale and not after
`an order has been taken as im XCON and Lowe’s
`proof-plans. The degree of flexibility provided to the
`user of these prodnets is not clear from theliterature.
`However, since XSEL is a rule-based system and
`Trilogy is an object-oriented system,
`their model
`(knowledge) must comprise a hierarchical represen-
`tation of all of the solution paths possible for all
`feasible configurations. These approaches to model-
`ing tend to impose one particular problem solving
`approach on a user that mustbe strictly adhered to at
`all times. This does not accommodate the need to
`support a number of diverse users with varying
`degrees of experience [11]. A novice sales represen-
`tative may need a chronological paradigm to help
`determine a compnter product confignration. But
`more experienced users will use both their product
`experience and their experience with the configura-
`tion support system to bypass many of the chrouo-
`logical steps made redundant through their experi-
`euce. By supporting such diverse users, the useful-
`ness of a configuration support system is ensured
`both as an aid for novices configuring computer
`products and as a configuration checker for more
`experienced users. This spectrum of support is ob-
`tained through the use of constraint-based modeling,
`interactive constraint propagation, and dynamic in-
`teraction with a relational database.
`Again considering the volatility of the computer
`market, it is evideut that configuration applications
`required today may be obsolete m as little as one
`year’s time. In the interest of time and money,it is
`better to train personnel from the field m information
`modeling and the use a software package than to
`train Artificial Intelligence (AI) specialists in the
`field. Hence, an environment is demanded that will
`enable rapid model building by product and manu-
`facturing engineers, and sales representatives. This
`approach does not appear possible with rule-based
`
`3. Related work in automated product configura-
`tion
`
`The most well known computer system used for
`sales support is XSEL and for computer product con-
`figuration is Xcon (R1). Both are rule-based expert
`systems used by Digital Equipment Corporation to
`configure their product set [2,3,8]. xcoN ensures the
`technical accuracy of customer orders and directs the
`assembly of those orders. XSEL is used interactively
`to select saleable items for a customer’s order and
`provides pricing information. pripe [9] and cossack
`[10] are frame-based expert systems which were built
`to support
`the design of paper handling systems
`inside copiers and to configure micro-computer sys-
`tems. COSSACK was adapted from the PRIDE system
`specifically to solve the computer configuration
`problem. Lowe [4] proposes the technique of proof-
`plans, a technique used in induction-based theorem-
`proving systems, to check orders previously taken by
`sales represeotatives. Trilogy [1] offers an object-ori-
`ented package called the SalesBUILDER to support
`computer product configuration at the poiot of sale.
`Technically, all of these systems can perform
`computer product configuration, What we are inter-
`ested in, however,
`is their ability to support
`the
`computer-product configuration task from our per-
`spective. As discussed above, first, do they support
`the construction of product configuration systems by
`non-specialists that can be exercised by personnel
`with diverse skills. Second, do they represent the
`
`6
`
`

`

`S.M. Fohn et al. / Computers in Industry 27 (1995) 3-21
`
`7
`
`expert systems as seen by DEC’s xseL and XCoN,
`both of which are burdened by their size and com-
`plexity. Together,
`these systems have just under
`14,000 mules, reqnire a staff of 60 to maintain, and
`require a programmer/analyst ta serve a 12 month
`apprenticeship m order to become proficient at np-
`dating the system [2]. A similar level of proficiency
`is required to construct an initial product configura-
`tor in Trilogy as it can take np to 12 months to
`complete. cossack and Lowe’s proof-plans have no
`measure of the time it
`takes to bnild confignration
`applications as this was not their focus of interest;
`but, based on their implementation descriptions, they
`appear to have similar limitations. Rapid develop-
`ment of configuration applications such as PC/CON
`results from two implementation aspects. First,
`the
`large quantity of rapidly changing yet stable interre-
`lationships between product components were mod-
`eled in a relational database. Second,
`the slower
`changing and more general constraints were modeled
`in Saturn. These resnlts are presented later in the
`paper.
`issues in computer
`important
`One of the most
`prodnet configuration is the maintainability and ex-
`pandability of existing configuration information
`models. The results from xsEL and xCoN show that
`maintenance of these systems requires an enormous
`effort.
`In addition to the specialized personnel in-
`volved,
`it is extremely difficult
`to ensure that
`the
`alteration or addition of a mile does not inadvertently
`create a contradiction with another rule somewhere
`else in the system. Thus, extensive testing must be
`done to ensnre that mle changes maintain system
`consistency.
`Trilogy hard-codes configuration rules and con-
`straints as methods that are part of objects in a class
`hierarchy. Trilogy emphasizes the ease of system
`“maintainability in their approach since most new
`products can be added to the configurator in terms of
`the existing products. Yet
`it
`is when the existing
`prodnets change and when new products, indepen-
`dent of the existing ones, are introduced that main-
`taining and updating the system becomes an issue.
`Such change is not nominal since it involves rewrit-
`ing methods without introducing any inconsistency
`into the system, a difficult task without a consistency
`checking mechanism. Although Trilogy has stated
`that the product
`information could be stored m a
`
`relational database and accessed by their Sales-
`BUILDER,
`they have not yet built such a system.
`Consequently, they cunid provide no estimate as to
`the time required to build the system. In addition, the
`cost of SalesBUILDER seems high at an average cost
`of $1 million per cnstomer[12], not inclnding main-
`tenance cost and system updates.
`Maintenance issues are difficnlt to assess in PRIDE
`
`and COSSACK since these systems were never used in
`a production environment nor was maintenance
`specifically addressed in their prototype form. How-
`ever, since the product information is hard-coded in
`the frames and class hierarchy, changes to the prod-
`uct information would require altering or rebuilding
`the basic system stnicture. This again requires an
`individual with advanced training and skill in artifi-
`cia] mtelligence to be mvolved in the tedious process
`associated with the model maintenance. Maintenance
`
`is similarly difficnlt tn assess in Lowe’s proof-plan
`system bnt since the issne was not addressed, it was
`most likely not solved.
`In summary, the above systems, while all able to
`support configuration in some form,
`fall short of
`dealing with a spectrum of users and attending to the
`needs of a diverse market in the computer industry
`which is characterized by a continuously changing
`and expanding product
`line. This becomes more
`apparent when considering the nature of computer
`product configuration.
`
`4, The expansive nature of computer product
`configuration
`
`The most distinguished characteristics of com-
`puter product configuration in the computer industry
`are change and the numberof different perspectives
`which should be represented in the configuration
`system. Change is found in all aspects of the indus-
`try: products, prices, disconnts for special configura-
`tions available for a limited time, software applica-
`tions, components, and the market focus. Such rapid
`and continuous change affects many areas in a com-
`pany, and each area can view the configuration
`problem from their own perspective. Each perspec-
`tive places a different emphasis on what aspects are
`considered to be more important in a configuration.
`In summary, both the change and the diverse inter-
`
`
`
`7
`
`

`

`S.M. Fohn et al. Computers in Industry 27 (1995) 3~21
`
`ests mentioned above have a direct effect in the way
`in which a competitive company must view com-
`puter product configuration.
`Consequently,
`the nature of computer product
`configuration cannot be seen simply as a process of
`combining compatible components into feasible con-
`figurations. It must be seen as an interactive, dy-
`namic process whereby answers to a large number of
`diverse questions from different perspectives can be
`found in the context of continuously changing prod-
`uct lines and product information. This demandsthat
`a product configuration support environment must
`have an architecture to accommodate these character-
`
`istics. The Saturn constraint-system shell and its
`integrated coupling to a relational database provides
`a unique architecture from which such environments
`cau be built.
`
`5. Architecture of Saturn—A constraint-system
`shell
`
`Saturn is a constraint-system shell in which prob-
`lems can be modeled as constraints and exercised
`through interactive constraint satisfaction [13]. Our
`
`is any interrelationship
`perception of a constraint
`among elements of a model; for example, a con-
`straint can be a rule, equation, relation, rows in a
`database table or any data structure. Saturn provides
`an environmentthat facilitates rapid model building
`and database interfacing, and provides user assis-
`tance when attempting to determine a feasible solu-
`tion to these constraint-based models. Coustraint sat-
`isfaction is achieved through automatic theorem
`proving techniques that operate with propositional
`default logic and order-sorted, first-order predicaté:
`logic (FOPL) [14]. Since Satum supports user inter-
`active constraint satisfaction, constraint variables can
`receive values in either of two ways: user assertion
`or value propagation. Through the selection of suit-
`able variable values, Saturn will propagate values to
`other interrelated variables. If variable values are
`selected such that
`they are inconsistent with the
`constraints, then the affected constraints are said to
`be violated. The minimnm set of variables that con-
`tributed to the violations are determined and pre-
`sented to the user who then attempts to alleviate the
`violations either by adjusting the constraints or by
`selecting alternative variable values.
`The Satum system’s components are shown in
`
` 8
`
`Cell Editor
`
`* on-line help system
`
`* WFF syntax checking
`
`>>
` Constraint-Sheet Interface
`Constraint Engine
`
`
`
` * spreadsheet-like
`* monotonic thecremprover eo
`* interactive
`- refutation resolution
`
`
`* dynamically visible:
`- hyper resolution
`
`
`
`~ value propagation
`* SQL generation
`
`
`
`- constraint satisfaction
`* value propagation
`
` - constraint violation
`* equation rewriting
`
`
`- constraint violations
`
`WFF Compiler
`
`* WEF nonnalization
`
`
`
`Relational Database
`Interface
`
`* axiomalic theorem prover
`* tightly-coupled
`* database/constraint sheet
`connection and
`communication mgmt.
`
`Assumption-based Truth
`Maintenance System
`* non-monotonic thearem
`prover
`* records and displays
`~ Value justifications
`
`Fig. 1. Architecture of the Satum constraint-system shell.
`
`8
`
`

`

`S.M. Fohn et al. / Computers in Industry 27 (1995) 3-21
`
`9
`
`Fig. 1. The constraint-sheet interface serves as the
`environment interface, Each cell
`in the sheet may
`contain either a domain, a logic constraint, a macro,
`a coustraint-sheet formula, or a text string that can be
`used to annotate an application. A cell with a domain
`represents a constraint-variable and may also have a
`name and value. Cells containing logic constraints
`(logic sentences may contain conjunction, disjunc-
`tion, implication, etc.) are displayed with respect to
`their evaluation state denoted by #T (irue), #F
`(false), and #U (unknown). Cells containing Prolog
`_prograins and database access declarations are re-
`flected in the constraint-sheet with the symbol
`#MAC (Macro). Cells containing constraint-sheet
`formula display the evaluation result of the formula.
`These sheet elements are entered into the constraint-
`
`sheet through the cell editor. The cell editor is cell
`specific and accommodates model development by
`providing a mechanism through which the sheet’s
`contents are entered and altered.
`
`A cell’s domain defines the range of values that
`can be accommodated by the cell. Domains may be
`explicitly enumerated in any constraint-sheet cell or
`defined over a column in a database. When a domain
`is entered into Satur,
`the well-formed formulae
`(WFF) compiler performs a number of checks to
`ensure that the domain is syntactically correct and
`that any references either to the database or a domain
`defined in another cell, are correct. When a value is
`entered into a cell,
`the WFF compiler performs a
`syntax check to ensure that the valne either exists ia
`an existentially defined Saturn dnmain or in a refer-
`enced database table’s column. All database interac-
`tion is performed via the Relational Database Inter-
`face as shown in Fig. 1. Similar syntax checking is
`performed whenever a logic constraint, macro, or
`constramt-sheet
`formula is entered into the con-
`straint-sheet. All syntax errors are reported to the
`user and all well formed, domains, valnes and con-
`Straints are translated internally into sentences of an
`order-sorted, first-order, predicate logic theory (see
`[15] for the formal theory).
`Variable values and normalized constraints are
`passed on to the constraint engine where they are
`used during theorem proving. The constraint engine
`implements hyper-resolution, refutation-based resolu-
`tion, mathematical equation evaluation and database
`query evaluation to prove the constraints as cither
`
`satisfied, or unsatisfied, and to perform value propa-
`gation. Satisfied constraints are those that have been
`determined to be frue. Conversely, violated (or un-
`satisfied) constraints are those that have been deter-
`mined to be false. If the constraint engine is inca-
`pable of determining the satisfiability or unsatisfia-
`bility of a constraint,
`the constraint remains un-
`known. Constraint propagation is achieved if variable
`values can be found by the constraint engine such
`that
`unknown constraints
`can be proved frue.
`Database constraints are first transformed into equiv-
`alent sox (Structured Query Language) sentences by
`the constraint engine’s theorem prover. Theoretically
`this is achieved by taking a proof-theoretic view of
`the relational DBMS as discnssed extensively by
`Reiter [16]. These constraints are then passed to the
`relational DBMS query processor, via the tightly
`coupled Relational Database Interface, for evalua-
`tion. The other constraints and macros are used by
`the standard constraints for data processing purposes.
`The Assumption-Based Truth Maintenance Sys-
`tem (ATMS) [17,18]
`is a non-monotonic theorem
`prover based on propositional logic that functions as
`an archive for all inferences performed and contra-
`dictions found by the constraint engine. The archived
`dependencies allow a user to view constraint viola-
`tions and resolve conflicts by rolling back to an
`application’s previous search state. Additionally, the
`ATMS can provide justifications for all variable
`valnes by presenting the solution path from which a
`cell’s value was determined. It is this component of
`Satum, together with the visual truth-values denoting
`the state of the constraints in the constraint-sheet that
`provides feedback to a user when performing con-
`straint satisfaction.
`
`The above architectural description of the Saturn
`constraint-systein shell provides an overview of the
`features and capabilities available for performing
`constraint-based modeling and interactive constraint
`satisfaction. Application developers are supported by
`a familiar spreadsheet-like interface that enables more
`emphasis to be placed on modeling and not on
`programming nor on the difficnities of logic theory.
`The tightly conpled database interface enables large
`constraint models to be built in a structured manner
`while still retaining the organizational simplicity of
`interrelated tables.
`In addition, Saturn’s ability to
`generate dynamic soL enables constraint models to
`
`
`
`
`
`9
`
`

`

` 10
`
`5.M. Fohn et al. f Computers in Industry 27 (1995) 3-21
`
` Business or engineering
`
`related need
`
`
`
`Model/Submodel
`Standards
`
`Hardware options
`and upgrades
`
`OI
`
`Software options
`
`Minimunhardware
`
`required to support
`software
`
`
`
` Constraint Sheet
`
`
`
`Relational Database
`
`
`|Hardware]Software[Price|
`
`
`Configuration attributes
`whose values satisfy customer
`
`and manufacturing requirements
`
`
`
`Interrelated hardware, software
`and price constraints
`
`Constraints to manage
`search for valid configuration
`Constraints
`
`
`
`Fig. 2. Architecture of the PC/CON constraint-based model.
`
`SUBMODEL_
`SPECLAL_
`SUBMODEL_
`DISPLAYS
`DISPLAY_ADAPT
`STANDARDS
`DISPLAYS
`
`submodel
`std_features
`
`DISPLAY_
`ADAPT
`
`
`
`
`
`
`
`
` SUBMODEL_ MEMORY_ MATH_
`
`
`MEMORY
`KITS
`COPROC
`SeuaNe—
`
`submodel)
`P
`mem_kit
`coproc_opt
`SUBMODEL_
`;
`STORAGE_BAYS
`rorsAe
`;ee
`
`
`
`
`
`
`OPERATING_
`SYSTEM
`oe
`
`SPREADSHEET_ STORAGE_
`PEGS
`
`STORAGE_
`SUBMODEL_
`STORAGE _REQMTS
`
`stor_opt
`
`
`
`
`Fig. 3. Entity—relationship mode! for pc/con,
`
`10
`
`10
`
`

`

`
`
`6. Implementing Pc / CON in Saturn and a rela-
`tional database
`
`11
`
`SM, Fohn et al, / Computers in Industry 27 (1995) 3-21
`
`1]
`
`be bnilt that represent the feasible interrelationships
`between elements of the model. This contrasts with
`other approaches that hard-code all search paths
`representing feasible configurations. Satum is able to
`dynamically alter its search space leading to a signif-
`icant reduction in the size and complexity of models
`[19]. A diverse number of users are supported by
`Saturn’s use of a constraint sheet in conjunction with
`the non-monotonic ATMS. This combination gives
`users the flexibility to approach a problem’s solution
`from an extremely wide number of directions. The
`_ constraint sheet allows a user to begin at any one or
`number of points in the problem and the ATMS
`enables a user to fall back to any previons point in
`the problem. In the following section we demonstrate
`the utility of Satum by showing how a compnter
`configuration system is implemented in Saturn and a
`relational database.
`Saturn, and its predecessors [20], have been ap-
`plied to a number of concurrent engineering tasks,
`including, design for assembly [21], rotational parts
`[22,23],
`testability of electronics assemblies [24],
`process planning for printed circnit boards assembly
`[25], and the design of automated storage and re-
`trieval systerns [26]. Extensions have been proposed
`in the areas of analysing large-scale systems [27],
`" handling imprecision [28}, using genetic algorithms
`[29], and hierarchical modeling [30].
`
`The database holds all computer model and sub-
`model, hardware options and upgrades, software op-
`tions, minimum hardware requirements to support
`certain software, and all pricing information. This
`data
`represents
`specific
`interrelationship