g VOLUME 27, Number1
`I $eptember1995
`i
`
`'
`
`'
`
`Iééw 0166-3615
`I‘
`I
`CINUD427(1)1—94(1995)
`
`I».-.«.s
`
`//
`
`
`
`Page 1 of 29
`
`FORD 1105
`
`

`
`
`
`r s
`
` f
`
`
`
`______.___.'--"r*-jvf‘."
`
`
`-t:v.~.-r-~g-»---i.“lF_-.-‘—!|':'_'-_1;r-".-_-'_a-:=L4..
`
`.,.
`
`corrimreag IN
`
`INDUSTRY
`
`Volume 27, 1995
`
`..
`
`Editor-in-Chief
`Hans Wortmann
`
`co-editor North America
`Colin L. Moodie
`
`Co-editor Industrial Acquisitions
`Gloria Karlrnark
`
`
`
`A
`
`i
`
`Amsterdam — Lausanne — New York — Oxford — Shannon — Tokyo
`
`Page 2 of 29
`
`FORD 1
`
`Page 2 of 29
`
`FORD 1105
`
`

`
` Computers in Industry 27 (1995) 3—21
`
`
`
`COMPUTERS Ill
`HNDISSTRY
`
`
`Configuring computer systems through constraint-based modeling
`and interactive constraint satisfaction
`
`S.M. Fohn b, J.S. Liau “’*, 'A.R. Greef b, R.E. Young “, P.J. O’Grady “
`' Group for Intelligent Design in Manufaertmlrtg, Department oflndustriat Engineering, North Carolina State Urtiuersity, Raleigh, NC
`27695-7906, USA
`
`1' IBM Corporation, NerworkApplr‘cotton Services Dtutsiorr, Thorrtwoad, M10594, 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 solve this
`problem results in an enormous expense for a company. In this paper we present an approach to solving this problem in the
`computer industry through constraint-based modeling and interactive constraint satisfaction. 1’C/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. Sarum’s architecture is presented and an example session with PC/DON 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),
`
`-J_-..._.:_.
`.-.__..:1‘.-...-.—....._-m
`
`
`
`-._.r.
`
`ii
`-.
`
`'1
`
`5.
`
`
`
`E
`t
`1: i.
`I....: L
`
`FORD 1
`
`0166-3615/95/$09.50 © 1995 Elsevier Science B.V. All rights reserved
`SSDI 0l66—361S(94)00D41—7
`
`Page 3 of 29
`
`Page 3 of 29
`
`FORD 1105
`
`

`
`
`
`4
`
`SM. Fahd et ul. / Computers in Industry 27 (1995) 3-21
`
`forcing a customer to return 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
`include product configuration checks both at
`the
`point of sale and between the point of sale and start
`of manufacture. Configuration checking is performed
`either manually or automatically by computer pro-
`grams. 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 infonnation 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
`
`manufacturing. This cyclic approach can have a neg»
`ative affect on a customer who is forced to endure
`
`frustrating product configuration
`long lead times,
`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
`manufacturing lead times and produces incorrect
`orders.
`
`- Configuration.errors can result in a loss of confi-
`dence by customers and can result in a loss of
`sales.
`
`-
`
`Incorrectly configured products can- be quoted
`inaccurately.
`- The configuration problem can be very large,
`
`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 compati-
`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 such as manu-
`facturing and marketing all of whom have an interest
`in computer product configuration. To accommodate
`this approach, we also introduce a Constraint Model-
`ing System called Satum, 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 product line 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 features and capabilities that a com-
`puter-support environment for computer oonfigura~
`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. This is followed by a discussion on the
`nature of the computer product 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 Satum’s interactive constraint satisfac-
`
`FORD 1105
`
`Page 4 of 29
`
`FORD 1105
`
`

`
`S.M. Fohn er ai. / 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 product line.
`
`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 requirements,
`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. Although 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 product configuration problem for a PC is still a
`complex and challenging task.
`In earlier years, manual PC product 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 Sbit 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 32bit 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 backplanc. Table 1 contains the number of
`feasible product configurations for the PS /2 product
`line for 1991/ 1992 and for 1993. The numbers are
`computed from [6] and [7].
`
`Table 1
`
`The number of feasible configurations for the PS/2 product line
`
`Model
`
`Number of configurations
`
`25-086
`25-286
`30
`35
`55
`56
`57
`70
`80
`90
`95
`
`Total
`
`1991 / 1992
`
`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
`
`1993
`
`240
`763
`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,3IS2,4l5,52|J
`
`36,’.-914,208,624
`
`4?2,741,960,848
`
`From the table, we can see that the number of
`configurations increased by more than 400 billion in
`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 3month cycle. In the PC industry 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.
`
`this challenge we consider computer
`To meet
`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. Once all
`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.
`
`Page 5 of 29
`
`FORD
`
`Page 5 of 29
`
`FORD 1105
`
`

`
`
`
`6
`
`SM Fohn er al. / Computers in Industry 27 {I995} 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 researchers in the field.
`
`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]. xcorl ensures the
`technical accuracy of customer orders and directs the
`assembly of those orders. xssr. is used interactively
`to select saleable items for a customer’s order and
`
`provides pricing information. PRIDE [9] and OOSSACK
`[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 representatives. Trilogy [1] offers an object-ori-
`ented package called the SalesBU1L.DER to support
`computer product configuration at the point 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
`
`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 in XCON and Lowe’s
`
`proof-plans. The degree of flexibility provided to tlfe
`user of these products is not clear from the literature.
`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 must be 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 computer product configuration. But
`more experienced users will use both their product
`experience and their experience with the configura-
`tion support system to bypass many of the chrono-
`logical steps made redundant through their experi-
`ence. 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 evident that configuration applications
`required today may be obsolete in as little as one
`year’s time. In the interest of time and money, it is
`better to train personnel from the field in 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
`
`FORD 1105
`
`Page 6 of 29
`
`FORD 1105
`
`

`
`S.M. Fohn et ai. / Computers in Industry 27 {I995} 3-21
`
`7
`
`expert systems as seen by DEC’s xssr. and xoon,
`both of which are burdened by their size and com-
`plexity. Together,
`these systems have just under
`14,000 rules, require a staff of 60 to maintain, and
`require a programmer/ analyst to serve a 12 month
`apprenticeship in order to become proficient at up-
`dating the system [2]. A similar level of proficiency
`is required to construct an initial product configura-
`tor in Trilogy as it can take up to 12 months to
`complete. COSSACK and Lowe’s proof-plans have no
`measure of the time it takes to build configuration
`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 aspe_cts. 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 results are presented later in the
`paper.
`issues in computer
`One of the most important
`product configuration is the maintainability and ex-
`pandability of existing configuration information
`models. The results from XSEL and XOON 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 rule does not inadvertently
`create a contradiction with another rule somewhere
`
`else in the system. Thus, extensive testing must be
`done to ensure that rule changes maintain system
`consistency.
`Trilogy hard-codes configuration rules and con-
`straints as rnethods 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
`products 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 in a
`
`relational database and accessed by their Sales-
`BUILDER,
`they have not yet built such a system.
`Consequently, they could provide no estimate as to
`the time required to build the system. In addition, the
`cost of Salessunnna seems high at an average cost
`of $1 million per customer [12], not including main-
`tenance cost-and system updates.
`Maintenance issues are difficult 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 structure. This again requires an
`individual with advanced training and skill in artifi-
`cial intelligence to be involved in the tedious process
`associated with the model maintenance. Maintenance
`
`is similarly difficult to assess in Lowe’s proof-plan
`system but since the issue 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 number of different perspectives
`which should be represented in the configuration
`system. Change is found in all aspects of the indus-
`try: products, prices, discounts 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-
`
`Page 7 of 29
`
`Page 7 of 29
`
`FORD 1105
`
`

`
`
`
`8
`
`SM. Fohrt er of. / 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 demands that
`a product configuration support environment must
`have an architecture to accommodate these character-
`
`istics. The Satum constraint-system shell and its
`integrated coupling to a relational database provides
`a unique architecture from which such environments
`can 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 environment that 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. Constraint sat-
`
`isfaction is achieved through automatic theorem
`proving techniques that operate with propositional
`default logic and order-sorted, first-order predicate
`logic (FOPL) [14]. Since Saturn 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
`
`they are inconsistent with the
`selected such that
`constraints, then the affected constraints are said to
`be violated. The minimum 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 Saturn system’s components are shown in
`
`Cell Editor
`
`* on-line help system
`
`WFF Compiler
`
`" WFF nonnaiization
`
`Cunstrairtt-Sheet Interface
`
`* spreadsheet-like
`* ‘mteracfive
`"' dynarnicalty visible:
`- value propagation
`- consI:rai.nt satisfaction
`
`Constraint Engine
`
`':>
`
`‘ monotonic tlteomn prover ¢|
`~ refutation resolution
`- hyper resolution
`* SQL generation
`* value propagation
`' equation revmung
`
`" WI-'-"l-'-' syntax checking
`- constraint violation
`
`- constraint violations
`
`Relational Database
`Interface
`
`‘ axiomatic theorem prover
`* tightlgr-coupled
`* databasefconstraint sheet
`connection and
`
`comrnurtication mgmt.
`
`Database
`
`FORD 1105
`
`Assumption-based Truth
`Maintenance System
`* non-monotonic theorem
`prover
`* records and displays
`- value justificalions
`
`Fig. 1. Architecture of the Saturn constraint—s)rstetn shell.
`
`Page 8 of 29
`
`FORD 1105
`
`

`
`S.M. Fohn er ai. / Computers in Industry 2? (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 constraint-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 (true), #F
`(false), and #U (unknown). Cells containing Prolog
`_programs 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
`
`the weii-formed formulae
`is entered into Satum,
`(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 value either exists in
`an existentially defined Saturn domain 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
`constraint-sheet
`formula is entered into the con»
`
`straint-sheet. All syntax errors are reported to the
`user and all well formed, domains, values 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 either
`
`satisfied, or unsatisfied, and to perform value propa-
`gation. Satisfied constraints are those that have been
`determined to be true. 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 true.
`Database constraints are first transformed into equiv-
`alent SQL (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 discussed 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
`values by presenting the solution path from which a
`cell’s value was determined. It is this component of
`Saturn, 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—system 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 difficulties of logic theory.
`The tightly coupled 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 sot. enables constraint models to
`
`Page 9 of 29
`
`Page 9 of 29
`
`FORD 1105
`
`

`
`
`
`10
`
`S.M. Fofm ex 31'./Computers in Industry 27 U995) 3-21
`
`Business or engineering
`related need
`
`
`
`Configuration attributes
`whose values satisfy customer
`and manufacturing requirements
`
`Inteflelfllfid hardware, software
`and price Constraints
`
`Consnaints to manage
`search for valid configuration
`Constraints
`
`Constraint Sheet
`
`Relational Database
`
`software
`
`Modelfsubmodel
`Standards
`
`Hardware options
`and upgrades
`
`Software options
`
`Minimun hardware
`
`required to support
`
`Fig. 2. Architecture of the PC/CON constraint-based model.
`
`SUBMODEL_
`DISPLAYS
`
`SPECIAL,
`STANDARDS
`
`SUBMODEL_
`DISPLAY ADAPT
`
`DISPLAY.
`ADAPT
`
`DISPLAYS
`
`
`
`disLot
`n
`
`submodcl
`
`P
`I
`
`VIDEO.
`SUBMODEL_PROC_
`
`UPGRADES
`
`-p1=3r_ada1=IT‘
`
`
`
`LEVE-'.L‘1 CACHE
`
`STORAGE BAYS
`bay
`
`BAY STORAGE
`omgms
`'
`fly type
`
`
`7M
`p oper__sys
`
`
`OPTIONS oper__sys
`
`Z
`
`2
`
`5”3“°DEL-
`ms
`MEMORY
`me:11_Iul
`P
`suhmodel
`n-,,m_k,f
`_ —
`
`—
`
`OOPROC
`WP1'°°—°9l
`
`SUBMODEI-—
`STORAGE_BAYS
`
`op]5,RA'nN(}_
`5Ys'1'EM
`
`SPR.EADSHEEl'_
`PKGS
`5PTd5hLPkS
`
`S'TORAGE__
`
`| D
`S'I‘ORAGE_
`
`Fig. 3. Entity-relationship model for PC/CON.
`
`ge 10 of29
`
`FORD11i)5
`
`Page 10 of 29
`
`FORD 1105
`
`

`
`S.M. Foim er al. /Computers in Industry 27 (1995) 3-21
`
`11
`
`be built 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 previous point in
`the problem. In the following section we demonstrate
`the utility of Saturn by showing how a computer
`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 circuit boards assembly
`[25], and the design of automated storage and re-
`trieval systems [26]. Extensions have been proposed