`5eeepteermb 1995
`
`ISSND1663615
`_
`7
`Icniuloa 27(1)1——94(1995)
`
`
`
`
`
`
`
`
`
`
`Editor. Prof. H. Wortmann
`
`'
`
`-
`
`.
`
`gompurrns IN
`IN‘ DU srnv .£9
`
`
`An international application orientedresear-ch-iaurnal
`IIIIIHII':
`
`
`' I"II III
`II
`
`LI'I'II'I‘II'I
`I I III
`'II
`'II
`
`”II I I I
`WW. #H':IIII
`
`III-III
`IIII-
`
`IIIIIII
`IIIIII
`
`.‘
`
`W9~9‘
`~9uw
`
`L‘JO'
`
`1
`
`CONFIGIT 1036
`
`I
`
`I .
`
`CONFIGIT 1036
`
`1
`
`
`
`CQMPWERS IN
`INDUSTRY
`
`Volume 27, 1995
`
`Editor-in-Chief
`Hans Wortmann
`
`Ctr-editor North America
`Colin L. Moodie
`
`Co—editor industrial Acquisitlnns
`Gloria Karlmark
`
`
`
`Amsterdam — Lausanne — New York — Oxford — Shannon - Tokyo
`
`
`
`2
`
`
`
`.a 111.1 u
`
`
`ELSVIEER
`
`Computers in Industry 27 (1995) 3721
`\‘.
`
`
`
`CGMPIWERS IN
`"MUST“
`
`
`Configuring computer systems through constraint-based modeling
`and interactive constraint satisfaction
`
`SiM. Fohn 1’, J.S. Liau "", AR. Greef b, R.E. Young 3, P.J. O’Grady 5‘
`' Group for Inteiligent Design in Manufacturing, Department ofIndustrial Engineering, North Carolina State University, Raleigh. NC
`27695-7906, USA
`5 IBM Corporation, Network Application Services Division, Thornwood, NY 10594, 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. 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 sofIWare must be config-
`ured for compatibility between hardware and other
`software so as to achieve good performance. A]-
`
`' 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/50950 © 1995 Elsevier Science EN. All rights reserved
`SSDI 0166-3615(94)00041-7
`
`
`
`3
`
`
`
`SIM. Fohrt et at. /C0mputers in Indus-try 27 (1995) 3-21
`
`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 mauu—
`facturiug 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 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 product line of
`feasible computer hardware configuratious,
`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 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. 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 SatLu'u, as a constraint-based model is shown.
`An example session with PCfirst: is then described
`to show how Saturn’s interactive constraint satisfao
`
`- Late discovery of configuration errors increases
`manufacturing lead times and produces incorrect
`Orders.
`
`- Configuration errors can result in a loss of confi
`dance by customers and can result
`in a loss of
`sales.
`
`-
`
`Incorrectly configured products can be quoted
`inaccurately.
`- The configuration problem can he very large,
`
`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—
`Plau [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
`
`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 ramming 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.
`
` 4
`
`4
`
`
`
`51M. Fohn at at. / Computers in Industry 2? (1995} 3—2.1l
`
`Lion 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 con—
`figuration
`
`Product configuration is a critical yet a cornplex
`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 configruatious,
`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 Shit 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 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
`computed from [6] and [7].
`
`Table 1
`The number of feasible configurations for the PS/2 product line
`Model
`Number of configurations
`1991/1992
`1993
`
`25—086
`25-286
`30
`35
`55
`56
`5'?
`70
`80
`90
`95
`
`Total
`
`240
`768
`21,760
`145,317,888
`335,584
`235,929,600
`115,605,504
`258,048
`23,181,312
`5,138,022,400
`31,085,035,5 20
`
`240
`768
`11,520
`238,132,224
`2,151,552
`2,615,325,763
`308,625,408
`1,347,840
`131,843,212
`2,082,103,296
`467,362,415; 20
`
`36,744,208,624
`
`422341360348
`
`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.
`
`
`
`
`
`
`
`5
`
`
`
`SM Fain: at at. / Computers in Industry 27 0995) 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
`
` 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 in xcou and Lowe’s
`
`proof—plans. The degree of flexibility provided to the
`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—
`tiou 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-
`teractiou 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 pile-based
`
`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. xsat 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 Prime system
`specifically to solve the computer configuration
`problem. Lowe [4] proposes the technique of proof-
`plans, a technique used in mduction-based theorem-
`proving systems, to check orders previously taken by
`sales representatives. Trilogy [1] offers an objectwori-
`ented package called the SaleanILDER 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 persounel
`with diverse skills. Second, do they represent the
`
`6
`
`
`
`S.M. Fohn er oi. / 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 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
`important
`One of the most
`product 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 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 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 coufigurator 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 rewrite
`ing methods without introducing any incousistency
`into the system, a difficult task without a cousistency
`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 SaleanthER 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 nf 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-
`
`
`
`7
`
`
`
`SM. Fohn er of. / Computers in Industry 27 (1'995) 3-21
`
`ests mentioned above have a direct effect in the vva}r
`in which a competitive company must view com-
`puter product configuration.
`Consequently,
`the nature of cemputer product
`configuration cannot be seen simply as a process of
`combining compatible components into feasible eon-
`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 Saturn 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) [14L Since Satu'm 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
`
` 8
`
`Cell Editor
`
`‘ on-liue help system
`
`“FF Compiler
`
`' WFF neutralization
`
`
`
`‘ WFF syntax checking
`
`Constraint-Sheet Interface
`
`
` * spreadsheet-like
`
`“ monotonic theorem prover <2]
`* interactive
`‘ refutation resolution
`
`
`* dynamically visible;
`- hyper resolution
`
`
`- value propagation
`' SQL generation
`
`
`- canslninl satisfaction
`’I‘ value propagation
`~ constraint violation
`
`
`* equation rewriting
`
`
`- constraint violations
`
`Relaunua‘1 Database
`Interface
`
`‘ axiomatic theorem prover
`* tightlycoupled
`‘ daubaselconstraint sheet
`connection and
`communication Ingmlv
`
`Constraint Engine
`
`
`E>
`
`
`
`
`Assumption-based Truth
`Maintenance System
`* non-monotonic theorem
`prover
`* records and displays
`- value justifications
`
`Fig 1. Architecture of the Saturn constraint—system shell.
`
`8
`
`
`
`SM. Fohn er al. / Computers in Industry 27 (1995} 3—21
`
`9
`
`Fig. 1. The constraintvsheet 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 diaplayed with respect to
`their evaluation state denoted by #T (true), #F
`(false), and #U (anknoivn). 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 well-formed formulae
`is entered into Saturn,
`(W17) 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 W'FF 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 cen-
`straints are translated intemally 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 c0ustraints 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 am
`known. Constraint propagation is achieved if variable
`values can be found by the constraint engine such
`that
`anlmown constraints
`can be proved true.
`Database constraints are first transformed into equiv~
`alent SOL (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 Sysv
`tern (ATMS) [17,18]
`is a non-monotonic theorem
`prover based on propositional logic that functions as
`an archive for all inferences perfOnned 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, Satum’s ability to
`generate dynamic sot, enables constraint models to
`
`
`
`
`
`9
`
`
`
` 10
`
`SM. Fohn at at / Computers in Indian)! 27 (1995) 3—21
`
`Business or engineering
`related need
`
`
`
`
`Relational Database
`
`
`Configuration amibutes
`
`whose values satisfy customer
`and manufacmring requirements
`
`
`
`Minimun hardware
`<::|
`
`software
`
`
`
`Intenelared hardware, software
`and price constraints
`
`Constraints to manage
`search for valid configuration
`Constraints
`
`Model/Submodel
`Standards
`
`Hardware options
`and upgrades
`
`Software options
`
`required to support
`
` Constraint Sheet
`
`Fig. 2. Architecture of the PC/CDN Constraint-based model.
`
`
`DISPIAYS
`
`SUBMODEL-
`DISPLAYS
`
`SPECEAL_
`STANDARDS
`
`
`
`SUB MODEL_
`DISPLA‘L
`DISPLAY ADAPT
`ADAPT
`
`P .iispladeapt—Z
`SUBMCDEL_PROC_
`VIDEO_
`UPGRADES
` v_mem_opl
`
`
`
`
`
`
`MEMORY,
`
`ms
`OOFROC
`SUBMODEL_
`P
`meuLt'u
`coprocjpt
`STORAGE,BAY5
`
`
`SUBMODEL_
`
`STORAGE REQMTS
`
`
`someway
`MEMORY
`submodel
`rnemjd:
`
`OPERATJNCL
`SYSTEM
`w:
`
`ems
`
`
`
`
`
`
`
`SPREADSH BEL STORAGE__
`PKGS
`
`LEVEL: CACHE
`
`
`
`STORAGE SAYS
`bar We
`
`17
`BA Y_STURAGE"
`OPTIONS
`' ELW
`storwopl
`
`P
`
`STORAGE;
`OPTIONS
`
`
`
`r opensys
`
`Fig. 3. Entity—relationship model for PC/CON.
`
`1O
`
`10
`
`
`
`SM. Fan." :1 at. /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. Saturn 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. hr 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
`in the areas of analysing large-scale systems [27],
`. handling imprecision [28}, using genetic algorithms
`[29], and hierarchical modeling [30].
`
`6. Implementing PC / CON in Saturn and a rela-
`tional database
`
`I