A NEW APPROACH TO PRODUCT CONFIGURATION
`
`Hans Jrargen Skovgaard
`
`BEOLOGIC Division
`Bang & Olufsen Technology A/S
`Struer, Denmark
`
`ABSTRACT
`
`This paper decribos a new method for product configuration based upon constraint
`techniques. The method is implemented in the BEOLOGIC Product Configurator. It has
`very powerful features for the end user; free order of choices, guaranteed fast response
`times and optimization functions. The method supports an easy maintenance process
`with a unique consistency check of configuration data. We compare the tool with
`previousty propose_d methods like expert systems to show the advantages of this
`approach. An example of car configuration is presented.
`
`KEY WORDS
`
`Product-oriented information systems, Al, Design for Manufacturabilityl
`Dependability,Testabi|ity, Product Configuration, Constraints, Interactive configuration.
`
`Page 1 of 5
`
`Page 1 of 5
`
`FORD 1110
`
`

`
`
`
`1.
`
`INTRODUCTION
`
`2. METHODOLOGY
`
`2.1 Objects & Resources
`
`be represented as objects e.g., the screen resolution on a PC although it derives from
`
`4.1 Constraints
`
`with traditional programmin , as with
`d
`1'
`master the general infonnatigon flow. Ag: l[:'9cSll.lol? ifleesgygfiggiléhgrgfiyfrlgfmiggtgazfig
`th
`-
`-
`’
`-
`.
`.
`_
`ey are hard to develop, test and maintain when either incomplete information or
`
`Hence it is possible to have a providerfconsurner principle. e.g., devices use certain
`amounts of power whereas power-supplys provide more power.
`
`2.2 Constraints
`
`The inference engine in the BPC '
`t t
`—
`f—
`-
`I
`‘
`both boolean algebra and finite dirfiafina:ri?hr:ih;i:ncc[:rc:2:'gfig :I:I'.::featIi.{l1;].'IJ-otifi fi1i?irfl:$f
`
`-
`-
`-
`-
`'
`f
`one that has more than 32 Mb
`iradmonal configuration Systemsytes o memory. This strong feature is impossible in
`
`trarisformed on a one-to-one basis into constraints.
`Two types of constraints are supported: boolean algebra and finite domain arithmetic.
`Examples from a UNIX workstation.
`
`Storage >= 300
`"The system should entail at least 300 Mb of storage (resource)."
`FlAM_8Mb + RAM_32Mb + RAM_64Mb <= 2
`"The model can only accommodate two optional memory options."
`impossible( Model_A, CDROM )
`"Model A does not support CDROM."
`
`The representation of UNIX workstations consists of only 30-40 constraints.
`
`
`
`Page 2 of 5
`
`FORD 1110
`
`

`
`
`
`The concept of the inference engine allows it to take advantage of future hardware
`improvements, and it will not be slow on weak computers.
`
`6. DISCUSSION
`
`5.
`
`COMPARISON WITH TRADITIONAL CONFIGURATION SYSTEMS.
`
`5.1 Representation
`
`Configuration problems are by nature NP-complete. Traditional configuration systems
`deal with this problem in several ways.
`
`* For expert system rules that deal with the execution of the application are added to
`reduce the problem to a_ simple linearlpolynomial problerrt. Adding Ease rulfiismig
`very bad for maintainability because they are not founded in the pro em con e
`but only in the context.
`_
`_
`_
`% The BPC does not have rules that deal with execution issues.
`
`* For decision trees the user is forced to make his choices in a prdefined order. This
`reduces the problem by avoiding unordered information flow. This yields an
`application that is very constraining for the user. imagine that a customer wants“:
`red car. The system will prompt for model.erigine, etc. And when it comes o
`colour it might not be possible to select red_at all.
`_
`% The BPC provides complete freedom in the order of choices.
`
`* Batch mode validation does not allow for interactive configuratipjn therefoifiimtthz
`problem is reduced by avoiding incomplete information. Batch rno_e1r_neanf
`_m
`use; picks all the parts that he assumes appropriate. Then the vaiida iotn a goal‘ m
`produces a list of missing and conflicting parts. Here the user has to pu up wi
`an
`iterative process. Imagine that the customer specifically said that he wanted I? part
`and the configurator then says that it is not possible. Then he has to start a over
`in.
`.
`$§a The BPC has an interactive mode where the status of resources are displayed
`dynamically such as price, storage and weight to give the user better overview.
`
`5.2 Maintenance.
`
`Maintenance of the product model is an extremely important feature of a configuration
`system where product changes may occur on a monthly basis or even more frequently.
`Traditional configuration tools have drfflculties with rapidly changing product modelg;
`For expert systems it is known that rule bases with up to 10, 000 rules exist [5] wh
`unfortunately makes it hard for even experienced engineers to change the rules.
`II
`Easy maintenance in the BPC is achieved by keeping the number of constraints sma .
`A single constraint often replaces many production rules and a companys products
`should be split into several knowledge bases. It is therefore ppssibie for even quite
`complicated products to be represented by less than 100 constraints.
`_
`Before the release of any configuration system a test must be made to see if errors
`occur in the configuration data. with the product range decomposed it
`Is On‘?
`necessary to test the changed products. Whereas if you have one big knowledge baseci
`you might have introduced side effects and the whole product range must be taste
`3. am.
`Tgie BPC allows for concurrent product configuration datamaintenance.
`
`200
`
`The reason for the progress made in the BPC is the recent development in constraint
`satisfaction algorithms [3][4] that allows them to successfully solve real world problems.
`
`The representation in the BPC is restricted to constraints on boolean and finite domain.
`It does not allow expressions like "exp( cos(x))". However most configuration tasks that
`sales people are able to perform with the printed documentation and sufficient time is
`suitable for the BPC. With the BPC it has been established that you can make
`configurations for cars, trucks, PABX's, computers, doors, coffee automates, custom
`installation guides, water pumps, hydraulic proportional valves etc.
`
`7.
`
`EXAMPLE : CAR CONFIGURATION
`
`The configuration problem is from SAAB Automobiles 1992 with the models from the
`900 series. We will show how products can be modelled within the BPC representation.
`
`in the example only the objects and constraints will be considered in depth except for
`the Object "Models". Therefore issues related to menu positioning, ID, Button names,
`Descriptions, object lD's and Languages are omitted. A graphics tool, BPC Engineering
`Environment, exists that helps the user to declare objects, resource, menus etc in an
`easy way and enables users to make rules by pick and place. This tool will not be
`described here.
`
`7.1 Declarations
`
`First the objects are declared.
`
`The 3 models are SAAB 900, Cabriolet and Turbo Cabriolet.
`They are declared as object "Models" of the type ONEOF.
`
`Object Type :
`Name :
`Identifier :
`Description :
`Parent Menu :
`Position X,Y :
`Default Value :
`Elements: Name :
`
`ONEOF
`Models
`Model
`"Some of the models in .... .."
`TOPLEVEL
`1,1
`SAAB_900
`"SAAB 900"
`ldentifer :
`ID/Pait No :
`Description :
`Resources :
`Name :
`identifier :
`lD/Part No :
`Description :
`Resources :
`Name :
`Identifier :
`ID/Part No :
`
`SAAB_9OO
`xxx—yyy
`"The safest car
`Price=fi|e , Weight=1112
`"Cabriolet"
`Cabriolet
`xxx—qqq
`"Unique features ...."
`Price=fi|e , Weight=1123
`"Turbo Cabriolet"
`Turbo_Cabriolet
`xxx-zzz
`
`Description :
`Resources :
`201
`
`"The ultimate driving ...."
`Price=file, Weight=1234
`
`
`
`
`
`
`Page 3 of 5
`
`
`ORD 1110
`
`Page 3 of 5
`
`FORD 1110
`
`

`
`
`
`The 4 engines are 2.0i, 2.1 i, 2.08 and Turbo.
`They are declared as one object "Engine" of the type ONEOF
`
`Available accessories are Automatic gearbox, ABS-brakes, Air Bag, Air-condition,
`Audio system. Automatic air-conditioning, Eec. mirrors/windows and Cruise control.
`These are declared as eight objects of the type SINGLE.
`
`Available Sunshine roofs are Manual steel, Electric steel and Electric glass.
`The sunroofs are declared as one object "Sunroof" of the type ATMOSTONE.
`
`Available Trims are Velour Jet—Tuff Horizon, Velour pique Parallel, Leather Contour
`and Leather Suede Contour. The trims are declared as one object "Trim" of the type
`ONEOF.
`
`Available trim Colors are Labrador, Marine, Puma, Angora, Buffalo and Pamir.
`These are declared as one object "TrimColor" of the type ONEOF.
`
`Available standard paints are Cirrus white, Black. Embassy blue, Cherry red and
`Talladega red. The paints are declared as one object "Stdpaint" of the type
`ATMOSTONE.
`
`NEW 2
`
`Leather <> TrimColor[ Pamir] or TrimColor[ Buffalo];
`Sub grouping of leather trim color"
`
`A:
`
`B:
`
`lmpossible( AirCondition, Automatic_AirCondition);
`
`Model[ Turbo_Cabrio|et] -> Engine[ Turbo] and
`Metalpaint and Leather and cruise_control;
`
`C&D:
`
`Model[ Cabriolet] -> Engine[ s21] and not TrimColor[ Marine];
`
`E 3
`
`F:
`
`G I
`
`H 2
`
`atgtrziaintl Ch8rry__red].or Stdpaint[ Tal_ladega_red] or
`Mara1:ia:in[
`itrin_beige] or Metalpaint[ Scarabe_green] -> not TrimColor[
`
`Illa/|Le[t1aal5::aint[ Citrin_beige] or Metalpaint[ P|atana_grey] —> not TrimColor[
`
`WARNING (Engine[ Turbo] and not ABS);
`
`Model[ Cabriolet] or Model[ Turbo_Cabrio|et] -> not Sunroof'
`
`Available metallic paints are Citrin beige, Platana grey, Le Mans blue, Scarabe green
`and Monte Carlo yellow. Declared as one object "Meta|paint" of the type ATMOSTONE.
`
`NEW:
`
`‘ll/letalpaint or Stdpaint;
`You must pick one type of paint"
`
`Objects that do not relate to physical items are Leather and delivery time. Leather is
`declared as an object of the type SINGLE. Delivery time is declared as one object of
`the type ENUM [0—35].
`
`Declared resources are Price, Weight and Horse power. Declared menus are
`Accessories, Trims, Paints, Accessories at Dealer.
`
`I:
`
`Delivery_time == 14 * Model[ SAAB 900
`+ 35 * Model[ Turbo_Cabriolet];_
`
`] +
`
`21 * M cl
`I
`'
`0 e[ Cabnolet]
`
`A warning constraint is a constraint that can be
`I
`cl b
`'
`‘
`desirable. For cars mostly boolean constraintsogieruuied LlJ)tuftO;Onl:]OOSt11:‘t:"S[::)(tiI.l{ll:'tlSS“ski
`PABX's the configuration model consists mainl
`f
`'th
`'
`'
`mostoptions can come in different numbers.
`y 0 an metlc Constraints because
`
`7.2 Constraints
`
`SAAB configuration guidelines:
`
`*A
`*B
`
`It is impossible to have both Air conditioning and automatic Air conditioning.
`The turbo cabriolet come with Turbo engine, metallic paint, leather trim and cruise
`control.
`
`*0 Ordinary cabriolets comes with 2.1 litre engine.
`‘D Ordinary cabriolets cannot have the Marinepairit.
`‘E Models with red, grey or green paints cannot be ordered with Marine trim.
`‘F Models with beige or green paints cannot be ordered with Puma trim.
`‘G Cars with Turbo engine should be ordered with ABS brakes.
`*H
`Sunroof cannot be ordered for cabriolets.
`*l
`Delivery times are 14 days for the SAAB 900, 21 days for the Cabriolet and 35
`days for the Turbo Cabriolet.
`
`These configuration guide lines yield the following knowledge base. Note the almost
`one to one correspondence between the written guidelines and the constraints. in the
`constraints the objects identifiers are used.
`
`Knowledge base :
`
`Fig. 1 Saab Sales tool Example
`
`7.3 Runtime Sales Tool
`
`With these declarations and con t
`'
`t
`th
`d
`'
`'
`'
`leftmost column of buttons is stsahadlarscl f:n§tr1onLsSt3hasta1:: tB)g'C|So?‘fheOr\s/ntiilg fiii%e1' TE:
`::$C$1r:'c:§a3;etglgr:::iical|y displayed at the bottom of the window. The obiects are
`name] Modeis _ “SAl;t.lBl‘Cg3b" wo selections Ihaveualready been made ‘in the window,
`9roup1o icall
`related ob‘ ct at“: Engme = 2»'°5 ‘The .b°" “"9"” "Pam" is “Sad *0
`acfivmedgl
`V
`is s.
`e sub menu Accessories at dealer‘ is shown when
`With the objects you can configure in the naive we b
`‘ckin
`d
`'
`I
`opened list for "Metallic Paints“ you will notice that thg oiztiigrli "M§n:C:r?ore\§1ellor1ivEhi:
`::r’_l::_l:i:;3sd E13‘:“fieJzlfiifihygegwrgsghoant
`ciaptitcin is ntotlonger available due to the
`‘
`I
`:56
`‘
`1\I':Flll'llCléggrlier selections have to be overrulegl.
`so I and the Syswm will resolve
`runtime system holds a number features that are not described in any length
`e
`here like Trace, Total list. D'sc u t
`F‘
`' h D t
`-
`resource, Loadfsave contiguraltio:
`mls ,
`e amt’ Response times’ Load/Save
`
`NEW :
`
`Leather <> Trim[ Leather_Contour] or Trim[ Leather_Suede];
`"Sub grouping of leather trim types"
`202
`
`
`
` FORD 1110
`
`Page 4 of 5
`
`Page 4 of 5
`
`FORD 1110
`
`

`
`
`
`8.
`
`IMPLEMENTATION
`
`'
`
`'
`
`The BPC has an Engineering Environment that runs on MS-Windows, and executable
`’””':,'"° °"‘{f"5]?m.;'." ;?.at.i‘§I‘c°RpI‘f;.°§?I§4 cg:-euzgigogespgrted to anyplatfonn. The
`d MOTIF The “Mme
`We ace is ”' up n
`n
`-
`'
`-
`-
`etc The inference
`BPC does not demand any pI’0P|‘I9¥aW application such as ‘M35359
`-
`engine uses a compiled version of the constraints to execute efficiently.
`
`|'
`
`REFERENCES
`
`CONCEPTION SIMULTANEE DE L'ATELIER
`
`ET DE son SYSTEME DE PILOTAGE
`
`'
`
`B. Grabot
`Ecole Nationale d'Ingénieurs de Tarbes
`Tarbes, France.
`
`'
`I
`with Boolean Constraints. Final report.
`fi|e'rF,,r(iBE;;3hgg§r.P{!;:%fiem&£2%tifique IBM France. Dec. 1991.
`
`AEROSPATIALE - Centre
`
`Concept of the BEOLOGIC Product Configurator. BEOLOGIC Division,
`'
`'
`'
`-
`Technology NS. 1994.
`
`B
`
`ang
`
`& 0|
`
`U S
`1‘ en
`
`RESUME
`
`
`
`
`Constraint satisfaction in Logic Programming. Pascal Van Hentenryck. The MIT PFeS5- 193 -
`9
`zine. Spring
`
`Algorithms for Constraint-Satisfaction Problems. A Survey. Vlpln Kumar
`,
`.
`.
`-
`-
`'
`'
`1992.
`
`. AI M
`
`693
`
`t‘
`'
`.
`.
`.
`Expert System for Configuration at DIGITAL. XCON and beyond. Commumca Ion
`32) Dec. 1988.
`
`ACM (
`
`I 31
`vo.
`
`—
`
`/
`
`Le développement du systems do pilotege cl‘
`un atelier est une tache cofrteuse et
`difficile. car celui~ci doit etre parfaitement adepté
`‘
`’
`son onvrronnement. Des rn
`
`'
`simuttanéo do l‘atelier or do son systems do pilotage. a I‘
`-
`'
`‘
`ilotags. Pour verifier Ia bonne
`adéquation entre Ies deux systemes décrits, des re
`'
`développees: cos regles génersnt des messages d‘avertissement lors de la verification
`PARADIGMPlusmetFUSIONSoftcasem,surstationdetravailSun.Quatreateliersdo
`de coherence dos rnodeles proposes. Lo développement de prototypes du systems est
`en cours on we d‘évaIuer deux supports informatlques de la rnéthode FUSION :
`I'AEFtOSPATtALE jugés représentatifs ont éte analyses on we de la conception do
`cette premiere base de regles.
`
`MOTS CLES
`Pilotage d'ateIIer, méthodes d'anaIy
`simultanée, ingénierie concourante.
`
`ABSTRACT
`
`se orientée objet, regles de coherence, conception
`
` _
`its environment. In order to allow a concurrent design of the PAC
`system and of the workshop. we first suggest reference models of the production
`activity control module. On the bases of these models. the workshop and its future
`control system are modelled through the FUSION object—oriented analysis method, in
`'
`‘
`order to develop the production activity control s
`
`
`
`I]
`
`ll
`l
`
`I
`
`1
`
`1'
`
`I
`
`I
`I
`
`‘
`
`I
`
`I
`
`I
`
`I
`
`I.
`
`'
`
`I
`
`
`
`ll
`
`I
`
`
`
`
` Production Activity Control, Object oriented analysis method, consistency rules,
`
`concurrent design, concurrent engineering.
`205
`
`
`
`
`
`H
`
`204
`
`Page 5 of 5
`
`FORD 1110