Kerstin Bongard-Blanchy

Carole Bouchard

Améziane Aoussat

Limits of Kansei -Kansei unlimited

Keywords:

This paper discusses momentary limitations of Kansei

Engineering methods. There are for example the focus on the evaluation of colour and form factors, as well as the highly time consuming creation of the Kansei questionnaires. To overcome these limits we firstly, suggest the integration of related scientific research results on product emotions etc. in the Kansei questionnaires. Thereafter we present a study on the wide range of Kansei aspects treated in an industrial conception setting. The results together with the literature review lead us to a framework on user-centred product conception aspects. This framework unfolds potential expansion points for Kansei contents. Both perspectives underline the potential of Kansei Engineering for future applications and show our vision of Kansei Engineering beyond the limits.

INTRODUCTION

This paper has for objective to lay open limitations in the application of Kansei Engineering methods in hitherto cases and to propose solutions to overcome these limits. At first Kansei-related research data and tools which might be directly integrated in the conception of Kansei questionnaires are introduced. As a second step, we present a study on Kansei factors during product conception. The findings of the literature review and the study allowed us to establish a framework on Kansei aspects of product conception. It shows aspects, besides semantics of forms and colours, which could potentially be treated through Kansei techniques, for example sensations evoked by textures or emotions triggered by motions. At the end, we discuss the findings under the perspective of Kansei beyond the limits.

FROM SEMANTIC DIFFERENTIALS TO HYBRID KANSEI ENGINEERING SYSTEMS

When Osgood proposed semantic differentials as a tool for measuring meaning in 1957, he provided the base for Kansei Engineering KE [START_REF] Osgood | The measurement of meaning[END_REF]. Nagamachi took on the method and created a methodology for the consideration of Kansei in product development [START_REF] Nagamachi | Innovations of Kansei Engineering[END_REF]. Since then, the KE methods have been applied and refined in many countries, especially in South-and East-Asia. The Japanese word Kansei, commonly translated as "feeling", includes a wide range of words related to style, emotions, affect, and semantic descriptors of products. The goal of KE is to facilitate the evaluation of the Kansei evoked by certain product attributes and to help designers to adapt products to the envisioned user experience. The classic Kansei Engineering proceeds in the following steps [START_REF] Nagamachi | Innovations of Kansei Engineering[END_REF]:

1. At the beginning a word base needs to be constituted.

The researchers collect terms typical for the product and its sector through brainstorming, journals, websites, etc. They select the most adapted words and group them into pairs of semantic differentials.

2. As a second step, rules for the repartition of the product components have to be deducted.

3.

A large number of participants evaluate the product or its components on the expression of its attributeslike form or colourwith a questionnaire that contains the previously defined semantic differentials.

4. The results are treated through statistical analysis of the relation between the Kansei values and the chosen attributes.

5. In order to exploit the results of the analytical part in further projects, the data is kept in a data base which is integrated in a Kansei Engineering System. Such a system links Kansei words with forms or colours and can be used as a design tool.

Various Kansei Engineering Systems have been developed to automatically support the design process [START_REF] Matsubara | Hybrid Kansei engineering system and design support[END_REF][START_REF] Shibata | Kansei Information Processing and Virtual Reality Techniques for Japanese Traditional Crafting Presentation[END_REF][START_REF] Tsai | Automatic design support and image evaluation of two-coloured products using colour association and colour harmony scales and genetic algorithm[END_REF][START_REF] Hsiao | Applying aesthetics measurement to product design[END_REF][START_REF] Wang | A Hybrid Kansei Engineering Design Expert System based on Grey System Theory and Support Vector Regression[END_REF]. Sophisticated systems contain interfaces that enable designers to manipulate the design's Kansei instantly through e.g. form or colour modifications.

KE methods have been used in various sectors, including mobile communication [START_REF] Lai | User-oriented design for the optimal combination on product design[END_REF][START_REF] Hong | Optimal balancing of multiple affective satisfaction dimensions: A case study on mobile phones[END_REF][START_REF] Yang | Constructing a Hybrid Kansei Engineering System Based on Multiple Affective Responses: Application to Product Form Design[END_REF], transportation interior design [START_REF] Tanoue | Kansei engineering: A study on perception of vehicle interior image[END_REF], [START_REF] Guerin | Kansei Engineering for Commercial Airplane Interior Architecture[END_REF], architecture [START_REF] Shibata | Kansei Information Processing and Virtual Reality Techniques for Japanese Traditional Crafting Presentation[END_REF], [START_REF] Llinares | Differential semantics as a Kansei Engineering tool for analysing the emotional impressions which determine the choice of neighbourhood: The case of Valencia, Spain[END_REF], [START_REF] Llinares | Kano's model in Kansei Engineering to evaluate subjective real estate consumer preferences[END_REF], tools and technical elements [START_REF] Wang | A Hybrid Kansei Engineering Design Expert System based on Grey System Theory and Support Vector Regression[END_REF], [START_REF] Schütte | Design of rocker switches for work-vehicles--an application of Kansei Engineering[END_REF], shoe design [START_REF] Ishihara | An analysis of Kansei structure on shoes using selforganizing neural networks[END_REF][START_REF] Alcantara | Application of product semantics to footwear design. Part II-comparison of two clog designs using individual and compared semantic profiles[END_REF][START_REF] Bouchard | A European emotional investigation in the field of shoe design[END_REF] and many others.

LIMITS OF KANSEI ENGINEERING METHODS

But even though the KE methods have been successfully implemented in the above listed wide range of projects, there remain certain limitations to their application. [START_REF] Schütte | KESoft 2.0 User Manual[END_REF]. However, the intense work on the word base is still required.

3. Kansei evaluations are mostly done based on static images of finished products instead of real objects, concepts or their interfaces. This limits the possibilities to influence the design during the conception process. Furthermore, it inhibits an interaction between user and object and therefore use sequences cannot be tested on their Kansei impact.

Lately we see first works from design researchers who have taken on evaluation of use sequences to overcome this limitation [START_REF] Lin | Semantic shifting within the interaction sequence[END_REF].

4. Kansei evaluation is mainly done on tangible factors of predefined product components. Modifications on each of these product elements can improve the Kansei of the whole object. However, a revision of the component structure, which is also an important part of designing, is not encouraged by the KE methods.

5. The KE measurement usually takes into account the emotions at the moment of first contact. However the Kansei towards a stimulus changes constantly with new insights, progressing understanding or loss of interest. To draw conclusions on the medium-and long-term effects of design's Kansei, the time component needs to be integrated into the methodology. Here too design researchers start to propose first approaches [START_REF] Georgiev | TIME FACTOR OF CORE EMOTIONS DERIVED FROM DESIGN MATERIALS : TOWARDS A DEEPER UNDERSTANDING OF PRODUCT EXPERIENCE[END_REF].

BEYOND THE LIMITS

Despite these momentary limitations, we believe that Kansei Engineering continues to be a promising approach for the development of user-centred products.

To overcome the shortcomings and to explore the presumably unlimited possibilities of Kansei Design, we propose to take into account the manifold research results from neighbouring disciplines like sociology or physiology and to widen the factors taken into account as impacting on Kansei.

Literature review on Kansei-related research data

We reviewed research publications in search of potentially complementary tools from Kansei-related fields. Our focus here lay on established word lists which could significantly accelerate the cumbersome creation of project specific Kansei questionnaires (the second identified limitation of today's KE methods). Sets of Kansei words could be a) generic, b) sector specific or c) product specific.

Looking at research from psychology, sociology and ergonomics, we find abundant material on emotions and values as well as usability. We can comfortably access schemas that contain all possible states of human emotions and extract those important for design. There are, for example, the Geneva Emotion Wheel [START_REF] Scherer | What are emotions? And how can they be measured?[END_REF],Plutchik's multi-dimensional model of emotions and his word-pair list [START_REF] Plutchik | The Emotions[END_REF], as well as the fourteen basic emotions (in English, Dutch, Finnish and Japanese) elicited by products proposed by Desmet [START_REF] Desmet | Designing Emotions[END_REF]. To access emotions stimulated by a product design, lexical methods like semantic differentials are not the only means. Lang's Self-Assessment Manikin SAM as well as Desmet's animated PrEmo character are both visual tools that bring a playful and universal component to the evaluation activity [START_REF] Bradley | Measuring emotion: The self-assessment manikin and the semantic differential[END_REF].

Sensations by their nature are limited through the available number of sensesvisual, audible, tactile, olifactif, gustatory, etc. The sensation describing words are therefore very closely related to physical product properties. For a basic vocabulary, we appreciate the work of Karana who assembled a list of verbal appraisals on perceived tactile or visual properties of materials [START_REF] Karana | Meanings of Materials[END_REF]. Another rich vocabulary was proposed by Zuo et al. who extracted a primary and a secondary "minimum lexicon" on tactile textures. It contains geometrical, physical, emotional and associative dimensions [START_REF] Zuo | An investigation into the sensory properties of materials[END_REF].

The science of ergonomics divides usability into three elements: efficiency, effectiveness and satisfaction. While the first two can be measured through performance parameters (time, quantity, quality, etc.); satisfaction can only be accessed through self-evaluation for the moment [START_REF] Tullis | Measuring the User Experience[END_REF]. In previous Kansei studies undergone by our Master students we found that the notion of satisfaction or the attitude towards the product or brand has a great influence on the rating of the semantic differentials. If people dislike a certain brand they tend to assign semantic descriptors that express things they find negative in general, regardless of the product's actual expression. Same goes for people who are completely indifferent towards the product. We therefore agree with Mantelet who suggests evaluating the participant's satisfaction in Kansei questionnaires [START_REF] Mantelet | Prise en compte de la perception emotionnelle du consommateur dans le processus de conception de produits[END_REF]. To better understand the user's reactions, Mantelet also proposes to integrate questions about the user's values at the beginning of Kansei questionnaires. A often cited reference and good word base is Rokeach's values list [START_REF] Rokeach | The Nature of Human Values[END_REF]. A Master student of our laboratory successfully adopted this list for the evaluation of the coherence of the product designs with the brand image [START_REF] Wu | Prise en compte de l'image de marque dans l'analyse du besoin relative au Kansei[END_REF]. Equally interesting is Schwartz' "Model of Relations between Motivational Values" [START_REF] Schwartz | Schwartz Model of Relations between Motivational Values[END_REF] which is based on human values which were found consistent between 40 countries.

While the previously discussed aspects can be represented through a limited number of possible conditions, the number of semantic terms to describe a product is merely infinite. Therefore literature review cannot provide us with an exhaustive list. However, our previous studies have shown that certain terms, for example: dynamic, comfortable, funny, luxurious, etc., are used by many participants. This means that there exist generic terms for certain types of products and sectors. Here collaborative work between all members of the Kansei community is desirable to establish a Kansei word pool.

Discussion

This collection of references on Kansei words and related measurement methods is far from complete.

Especially on sensation describing words, further resources are still to be revealed. Many KE researchers have probably already used some of the mentioned lists in the course of the creation of their questionnaires. We will continue the collection and evaluation of these tools and hope to share experiences on their practicability with the Kansei community.

Study on tangible and intangible aspects treated during product conception

After this excursion into research literature, this second part of the paper will look at real product designs. The different research tendencies already point at the complexity of product Kansei. It cannot be ignored that there are various features, besides form and colour (as stated under the first current limitation), which influence the Kansei of the user. To identify all product aspects that elicit Kansei, we conducted a study on the design conception of a fictive product in an industrial setting.

Methods

The study had for objective to detect all user and product related aspects treated by designers and engineers during the conception of consumer products and to indentify relations between these aspects. Eleven professionals from two French companies participated.

One was a design agency, the other a manufacturer of telecommunication devices. Among the participants were five product designers, three graphic designers, and three engineers. The task was to generate a purely lexical design concept for: "A communicating coffee machine for Adidas".

The study consisted of two parts. First, each professional faced the fictive brief and underwent a mind mapping during one hour. They were asked to note all words on post-its, place them on a paper surface and link related words with marker lines. The duplication or relocation of words was allowed. The participants were repeatedly encouraged to simultaneously verbalize their thoughts which enabled the researchers to follow their reflexion during the activity. Following this individual exercise, the produced words were united into a word pool and classed by three researchers. The participants assembled and received a marker of a different colour each. During 45 minutes they could choose words from the pool, position them on a wall, and mark relations between words with drawn lines. Thereby we encouraged discussion on the choice of relations among the participants. Everybody who agreed on a chosen link marked it with a line of his colour.

The study was videotaped. All mind maps were reproduced in Adobe Illustrator. The noted words were sorted and listed in excel tables. The data was statistically analysed on the absolute and relative word occurrence par identified aspects. Furthermore a data base was programmed, to register all linked word pairs. The data base helped to extract the absolute and relative quantity of relations between words of different categories. We normalized the data by dividing the absolute number of links between two conception aspects by the product of words assigned to them.

Results in general

Each participant produced a mind map. Another mind map was developed by the whole team in both companies. Figure 1 shows one product designer's individual production. In Figure 2 the collective mind map of one company is illustrated.

Result 1: Occurrence of tangible and intangible aspects during product conception

Among the identified aspects were product properties like form (e.g. strait, open, symmetrical), colour (e.g. green, red, golden), material (e.g. polyamide, carbon, wood), texture (e.g. brilliant, craggy, smooth), and patterns (e.g. arabesque, point, small squares). Furthermore we found words related to technical functionalities (e.g. geo-localization, aeration, power supply), product components (e.g. body housing, screen, battery), and basic aspects of production (e.g. casting, injection, engraving). We call them tangible aspects. The array of found attributes related to the user ranges from values (e.g. liberty, sustainability, reliability) to semantic product descriptors (e.g. dynamic, classic, feminine), sensations (e.g. warm, soft, aromatic), and emotions (e.g. assuring, pleasant, funny), words that describe a specific style (e.g. edge, retro-cool, pop-art), and analogies which transport a metaphoric idea (e.g. like a water drop, dragonfly, magic lantern). We also classed gestures of the user to interact with the product (e.g. touch, rotate, push, scroll), words related to the expected macro function of the product (e.g. communication, protection, leisure), the use context (e.g. morning, at home, rendezvous), and the target user (e.g. adolescent, early adopter, family) under these intangible aspects.

Table 2 shows all identified aspects and their definition.

The statistical analysis of all 513 terms allowed us to estimate the pertinence of each conception aspect.

Table 1 shows the percentage distribution of the collected words under the identified aspects.

Result 2: Relations between tangible and intangible aspects of product conception

To investigate the relation between the different tangible and intangible conception aspects, the links on the idea maps, produced by the participants during the study, were analyzed. The normalized repartition of links between tangible and intangible aspects can be seen in Table 3.We state the following connections:

1. Words belonging to the same aspect were frequently related. We find strong connections among colours, materials, forms, and words defining target users. The same applies on a slighter level for words belonging to texture, values, sensations, and gestures.

2. Between tangible aspects, colours were often related to forms. Materials were often paired with textures. And patterns show multiple links with texture too.

3. Between intangible aspects, values were frequently related to semantic product descriptors and to words describing the use context. The context also appeared often together with terms on target users. Furthermore, emotions and sensations very closely related.

Strong links between tangible and intangible aspects

were formed between style and forms as well as between style and colours. And semantic descriptors where frequently related to material and texture. 5. Pattern, style and emotions were the groups with the least number of words and therefore, despite the normalization, a complete lack of links with many aspects appeared.

Discussion

We gathered a wide base of lexical data related to the conception of a product. Sorting and statistical analysis of these terms enabled us to identify various types of tangible and intangible aspects of product conception. The obtained data allowed us to see tendencies in the occurrence of the various aspects. However, the level of abstraction between the found tangible and intangible aspects ( Table 2) differs strongly. Some of them are features (e.g. components or functionalities) while others are the characterization of these features (e.g. colours or semantics) [START_REF] Hassenzahl | The Thing and I: Understanding the Relationship Between User and Product[END_REF]. The level of granularity of the categories varies. Theoretically, procedures and components could be further sub-categorized into fabrication, assemblage, etc. Only their occurrence was too low to create relevant subcategories.

Looking at the data from the point of view of Kansei methods, forms and colours were well represented on the tangible side. But we also found a wide range of complementary product properties like texture, material, patterns which might make a difference for the user experience. Kansei relevant aspects like semantic product describing adjectives, emotions, and sensations had their place among the terms identified on the intangible side during the fictive conception process. Looking at the wide spectrum of found aspects, we propose to broaden the Kansei space to all these factors and effects of design on the human. As such we consider values and analogies (associations evoked by the design) as part of Kansei too.

Our second objective was to lay open relations between the tangible and intangible aspects of product conception. The fact that intra-category links appeared frequently might be due to their contextual proximity. The other found links like between material and texture or style and form correspond to the common sense of the profession. They show that designers and engineers today already hold the knowledge to estimate the consecutive consequences of choices on one aspect like material on others like colour, values or functionalities. However, the mind maps (Figure 1and Figure 2) illustrate the complexity of the knowledge which has to be treated in the design process. Here the Kansei Engineering tools could be deployed to take into account relations between enlarged tangible and intangible conception aspects.

A framework of complex Kansei relations

The findings of the study and the literature review nourished our proposition of a framework that includes the identified tangible and intangible aspects of product conception (Figure 3). Like the "framework of aesthetic interaction" [START_REF] Locher | A Framework for Aesthetic Experience[END_REF], our framework too has two poles: the user's Kansei and the materialization in the product. The cognitive flow is triggered by tangible aspects of the product, e.g. the form, the colour, or the material. They stimulate the user's receptors and are being perceived through comparison with memory contents. If the stimuli is identified as relevant, the user shows an emotional or/and a motoric response. E.g. a particular reflection raises his interest and he reaches out to move the object. Now a new stimulus, for example the soft surface, is being perceived and responded to. This cycle is called the "sensorimotor coupling" [START_REF] Lenay | Énaction , Externalisme et Suppléance Perceptive[END_REF].

If we look at the human side, we see a number of factors which can potentially be addressed through Kansei Design. There are semantics and emotions, social values, sensations, as well as aspects related to usability satisfaction, effectiveness and efficiency [START_REF] Tullis | Measuring the User Experience[END_REF]. We refer to them as "intangible aspects of product conception". On the side of the artefact are the product features and their characteristics [START_REF] Hassenzahl | The Thing and I: Understanding the Relationship Between User and Product[END_REF]. They form the stimuli and include product characteristics like form, colour, material, texture, motion, and function of the product and its components. Furthermore, externally visible components, parts of the product architecture and modes of fabrication or joining can also potentially stimulate the user. We use the term "tangible aspects" of product conception to group aspects directly related to the product. While the same product might stimulate different intangible aspects in different users, we consider the perception of the tangible aspects of this same product consistent between all users, except in case of cognitive or physical limitations.

Discussion: Perspectives of Kansei beyond the limits

The literature review and the study have allowed us a first step to think of Kansei methods that overcome actual limits. For example, to overcome the first identified limitation (focus on colour and form), we propose an extension of the Kansei space. To do so one can consult the introduced "framework of complex Kansei relations" to choose which aspects on the intangible side (the user) and which on the tangible side (the product) are relevant for the product. Then the Kansei methods can be adapted to these points. Another interesting source to widen the Kansei space is the list of Kansei Study Keywords assembled by Levy, Nakamori and Yamanaka. It gives an overview on the manifold contents which are already being considered important by the KE community [START_REF] Levy | Explaining Kansei Design Studies[END_REF]. action, he can evaluate use sequences.

As already mentioned, the semantic differentials are not the only possible method for Kansei Design. Characters like those of Desmet or Lang can change the monotonous filling of a word based questionnaire while even providing reliable results. As already proposed by other Kansei researchers, physiological and comportmental measures can complete the Kansei Engineering methods. They allow the researcher to unveil unconscious relations between visual stimuli and emotional responses [START_REF] Lokman | KANSEI ENGINEERING CONCEPT IN E-COMMERCE WEBSITE[END_REF], [START_REF] Kim | Modeling cognitive and affective processes of designers in the early stages of design : Mental categorization of information processing[END_REF]. Now the interesting challenge we see is to investigate which combination of methods is the most pertinent to measure the impact of which tangible aspect on the Kansei.

CONCLUSION

This paper had for objective to show limitations of Kansei that became visible during the literature study on Kansei Engineering related projects. To address some of the limitations, we proposed to enlarge the understanding of Kansei relevant aspects. References from literature were presented which might be used for a simplified creation of meaningful Kansei questionnaires. We reviewed research results of Kanseirelated disciplines and proposed some useful collections of words describing emotions, values, etc., as well as some additional measurement techniques.

A study was conducted to identify a wide range of intangible (values, semantics, analogies, emotions, and sensations) and tangible aspects (form, colour, material, texture, functionalities, motions, components, and production procedures). These can all potentially become elements of Kansei studies.

We finished with a brief outlook on how the applications of Kansei Methods could evolve in the near future. One option to augment the pertinence of Kansei evaluation would be its application throughout the whole product design process, and in particular on dynamic product representations like scenarios or interfaces.

Figure 1 :

 1 Figure 1: A participant's individual mind mapping.

Figure 2 :

 2 Figure 2: Collective mind map in one company. The maps include 513 conception words (mostly in French, for this paper examples were translated into English). Furthermore, the participants linked pairs of these words about 861 times (in average 78.3 links per person) during the individual phase. The group activity amplified the number of links to 1790, which is equivalent to 174.5 links per person.

Figure 3 :

 3 Figure 3: Framework of Kansei relationsthe experience flow from the user's point of view.

  Today's KES are project-specific and can hardly be used in other contexts. Their development is very costly in terms of time and resources because a new set of Kansei words and questionnaires has to be developed for each product. Schütte already proposed a generic software to quickly create Kansei questionnaire forms

1. The most evaluated aspects to this day are forms and colours. Of the analysed research papers on Kansei Engineering nearly 40% looked at the Kansei of form factors, about 15% related Kansei with colours and 10% combined both, form and colour. Most of the other papers presented advancements of the algorithms and methods for statistical analysis. Discussions among the Kansei community in social networks already propose different ideas to expand KE application to other fields of human interaction, e.g. advertisement or project management [19]. 2.

Table 1 : Percentage distribution of conception words in the identified conception aspects, 513 words.

 1

	We find slightly more than half of all mentioned concept
	words under intangible aspects (56.2%). The importance
	of both, tangible and intangible, aspects was balanced.
	The attributes containing most conception words were
	analogies (12.4%) and semantic descriptors (8.9%) on
	the intangible side and functionalities (18.2%) on the
	tangible side. Style and emotions on the intangible and
	procedures on the tangible side were the groups with the
	least number of words.

Table 2 : List of conception aspects, *definitions based on Oxford dictionary.

 2

Table 3 : Normalized repartition of links made between conception aspects.

 3

ACKNOWLEDGMENTS

The study presented in this paper is part of a large-scale research project, Skippi, for the development of a software for the stimulation of the conception process. We thank the Agence Nationale de la Recherche France for their support of this project, the industrial partners for their friendly participation in the study and our academic partners Professor Nathalie Bonnardel and Damien Lockner from the Research Centre in Psychology of Cognition, Language and Emotion (PsyCLE) for their rich input and the productive collaboration.


Paul Pitiot
email: paul.pitiot@mines-albi.fr

Michel Aldanondo
email: michel.aldanondo@mines-albi.fr

Elise Vareilles
email: elise.vareilles@mines-albi.fr

Linda Zhang
email: l.zhang@ieseg.fr

Thierry Coudert
email: thierry.coudert@enit.fr

Some Experimental Results Relevant to the Optimization of Configuration and Planning Problems

Keywords: mass customization, aiding configuration, aiding planning, constraint satisfaction problem, evolutionary algorithm

This communication deals with mass customization and the association of the product configuration task with the planning of its production process while trying to minimize cost and cycle time. We consider a two steps approach that first permit to interactively (with the customer) achieve a first product configuration and first process plan (thanks to non-negotiable requirements) and then optimize both of them (with remaining negotiable requirements). This communication concerns the second optimization step. Our goal is to evaluate a recent evolutionary algorithm (EA). As both problems are considered as constraints satisfaction problems, the optimization problem is constrained. Therefore the considered EA was selected and adapted to fit the problem. The experimentations will compare the EA with a conventional branch and bound according to the problem size and the density of constraints. The hypervolume metric is used for comparison.

Introduction

This paper deals with mass customization and more accurately with aiding the two activities, product configuration and production planning, achieved in a concurrent way. According to the preferences of each customer, the customer requirements (concerning either the product or its production) can be either non-negotiable or negotiable. This situation allows considering a two-step process that aims to associate the two conflicting expectations, interactivity and optimality. The first interactive step, that sequentially processes each non-negotiable requirement, corresponds with a first configuration and planning process that reduces the solution space. This process is present in many commercial web sites using configuration techniques like automotive industry for example. Then, a second process optimizes the solution with respect to the remaining negotiable requirements. As the solution space can quickly become very large, the optimization problem can become hard. Thus, this behavior is not frequent in commercial web sites. Meanwhile some scientific works have been published on this subject (see for example [START_REF] Hong | Identification of the optimal product configuration and parameters based on individual customer requirements on performance and costs in one-of-a-kind production[END_REF] or [START_REF] Aldanondo | Configuration for mass customization: how to extend product configuration towards requirements and process configuration[END_REF]) and the focus of this article is on the optimization problem. In some previous conferences we proposed an interesting adapted evolutionary algorithm for this problem [START_REF] Pitiot | Using constraints filtering and evolutionary algorithms for interactive configuration and planning[END_REF]. However, the presentation was rather descriptive and experimentations were not significant. Therefore, the goal of this paper is to compare this algorithm with a classical branch and bound. This initial section introduces the problem and the organization of the paper.

Concurrent Configuration and Planning Processes as a CSP

Deriving the definition of a specific or customized product (through a set of properties, sub-assemblies or bill of materials, etc…) from a generic product or a product family, while taking into account specific customer requirements, can define product configuration [START_REF] Mittal | Towards a generic model of configuration tasks[END_REF]. In a similar way, deriving a specific production plan (operations, resources to be used, etc...) from some kind of generic process plan while respecting product characteristics and customer requirements, can define production planning [START_REF] Barták | Constraint satisfaction techniques in planning and scheduling[END_REF]. As many configuration and planning studies (see for example [START_REF] Junker | Handbook of Constraint Programming[END_REF] or [START_REF] Barták | Constraint satisfaction techniques in planning and scheduling[END_REF]) have shown that each problem could be successfully considered as a constraint satisfaction problem (CSP), we have proposed to associate them in a single CSP in order to process them concurrently. This concurrent process and the supporting constraint framework present three main interests. Firstly, they allow considering constraint that links configuration and planning in both directions (for example: a luxury product finish requires additional manufacturing time or a given assembly duration forbids the use of a particular kind of component). Secondly they allow processing in any order product and planning requirements, and therefore avoid the traditional sequence: configure product then plan its production [START_REF] Aldanondo | Towards an association of product configuration with production planning[END_REF]. Thirdly, CSP fit very well on one side, interactive process thanks to constraint filtering techniques, and on the other side, optimization thanks to various problem-solving techniques. However, we assume infinite capacity planning and consider that production is launched according to each customer order and production capacity is adapted accordingly.

In order to illustrate the addressed problem we consider a very simple example dealing with the configuration and planning of a small plane. The constraint model is shown in figure 1. The plane is defined by two product variables: number of seats (Seats, possible values 4 or 6) and flight range (Range, possible values 600 or 900 kms). A constraint Cc1 forbids a plane with 4 seats and a range of 600 kms. The production process contains two operations: sourcing and assembling. (noted Sourc and Assem). Each operation is described by two process variables: resource and duration: for sourcing, the resource (R-Sourc, possible resources "Fast-S" and "Slow-S") and duration (D-Sourc, possible values 2, 3, 4, 6 weeks), for assembling, the resource (R-Assem, possible resources "Quic-A" and "Norm-A") and duration (D-Assem, possible values 4, 5, 6, 7 weeks). Two constraints linking product and process variables modulate configuration and planning possibilities: one linking seats with sourcing, Cp1 (Seat, R-Sourc, D-Sourc), and a second one linking range with the assembling, Cp2 (Range, R-Assem, D-Assem). The allowed combinations of each constraint are shown in the 3 tables of figure 1. Without taking constraints into account, this model shows a combinatory of 4 for the product (2x2) and 64 for the production process (2x4) x (2x4) providing a combinatory of 256 (4 x 64) for the whole problem. Considering constraints lead to 12 solutions for both product and production process.

Optimizing Configuration and Planning Concurrently

Given previous problem, various criteria can characterize a solution: on the product configuration side, performance and product cost, and on the production planning side, cycle time and process cost. In this paper we only consider cycle time and cost. The cycle time matches the ending date of the last production operation of the configured product. Cost is the sum of the product cost and process cost. We are consequently dealing with a multi-criteria optimization problem. As these criteria are in conflict, it is better for decision aiding to offer the customer a set of possible compromises in the form of Pareto Front.

In order to complete our example, we add a cost and cycle time criteria as represented in figure 2. For cost, each product variable and each process operation is associated with a cost parameter and a relevant cost constraint: (C-Seats, Cs1), (C-Range, Cs2), (C-Sourc, Cs3) and (C-Assem, cs4) detailed in the tables of figure 2. The total cost is obtained with a numerical constraint and the cycle time, sum of the two operation durations, is also obtained with a numerical constraint as follow:

Total cost = C-Seats + C-Range + C-Sourc + C-Assem.
Cycle time = D-Sourc + D-Assem The twelve previous solutions are shown on the figure 3 with the Pareto front gathering the optimal ones. In this figure, all solutions are present. When non-negotiable requirements are processed during interactive configuration and planning, some of these solutions will be removed. Once all these requirements are processed, the identification of the Pareto front can be launched in order to propose the customer a set of optimal solutions. A strong specificity of this kind of problems is that the solution space is large. It is reported in [START_REF] Amilhastre | Consistency restoration and explanations in dynamic csps -application to configuration[END_REF] that a configuration solution space of more than 1.4* 10 12 is required for a car configuration problem. When planning is added, the combinatorial structure can become huge. Specificity lies in the fact that the shape of the solution space is not continuous and in most cases shows many singularities. Furthermore, the multicriteria aspect and the need for Pareto optimal results are also strong problem expectations. These points explain why most of the articles published on this subject (as for example [START_REF] Li | Product configuration optimization using a multiobjective GA[END_REF]) consider genetic or evolutionary approaches to deal with this problem. However classic evolutionary algorithms have to be adapted in order to take into account the constraints of the problem as explained in [START_REF] Coello Coello | Theoretical and numerical constraint-handling techniques used with EAs: A survey of the state of art[END_REF]. Among these adaptations, the one we have proposed in [START_REF] Pitiot | Using constraints filtering and evolutionary algorithms for interactive configuration and planning[END_REF] is an evolutionary algorithm with a specific constrained evolutionary operators and our goal is to compare it with a classical branch and bound approach.

In the following section we characterize the optimization problem and briefly recall the optimization techniques. Then experimentation results are presented and discussed in the last section.

2

Optimization Problem and Optimization Techniques

Optimization Problem

The problem of figure 2 is generalized as the one shown in figure 4. The optimization problem is defined by the quadruplet <V, D, C, f > where V is the set of decision variables, D the set of domains linked to the variables of V, C the set of constraints on variables of V and f the multi-valuated fitness function. Here, the aim is to minimize both cost and cycle time. The set V gathers: the product descriptive variables and the resource variables. The set C gathers constraints (Cc and Cp). Cost variables and operation durations are deduced from the variables of the set V thanks to the remaining constraints.

Fig. 4. Constrained optimization problem

Experimentations will consider different problem sizes: different numbers of product variables, different number of production operations and different number of possible values for these variables. Different constraint densities (percentage of excluded combinations of values) will be also considered.

Optimization Techniques

The proposed evolutionary algorithm is based on SPEA2 [START_REF] Zitzler | SPEA2: Improving the Strength Pareto Evolutionary Algorithm[END_REF] with an added constraints filtering process that avoids infeasible individuals (or solutions) in the archive. This provides the six steps following approach:

1. Initialization of individual set that respect the constraints (thanks to filtering), 2. Fitness assignment (balance of Pareto dominance and solution density) 3. Individuals selection and archive update 4. Stopping criterion test 5. Individuals selection for crossover and mutation operators (binary tournaments) 6. Individuals crossover and mutation that respect constraints (thanks to filtering) 7. Return to step 2.

For initialization, crossover and mutation operators, each time an individual is created or modified, every gene (decision variable of V) is randomly instantiated into its current domain. To avoid the generation of unfeasible individuals, the domain of every remaining gene is updated by constraint filtering. As filtering is not full proof, inconsistent individuals can be generated. In this case a limited backtrack process is launched to solve the problem. For full details please see [START_REF] Pitiot | Using constraints filtering and evolutionary algorithms for interactive configuration and planning[END_REF].

The key idea of the Branch and Bound algorithm is to explore a search tree but using a cutting procedure that stops exploration of a branch when a better branch has already been found. The first tool is a splitting procedure that corresponds to the selection of one variable of the problem and to the instantiation of this variable with each possible value. The second tool is a node-bound evaluation procedure. The filtering process is used to achieve this task with a partial instantiation and is able to evaluate if the partial instantiation is consistent with the constraints of the problem, and, if this is the case, to provide the lower bound of each criterion cycle time and cost. When the search reaches a leaf of the search tree, or complete instantiation, the filtering system gives the exact evaluation of the solution. Thus, the values of leaf solutions can be used to compute the current Pareto front and then to cut remaining unexplored branches that are dominated by any aspect of the Pareto front solution (e.g. the upper bounds of the leaf solution dominate the minimal bounds of the branch to cut).

Experimentations

The optimization algorithms were implemented in C++ programming language and interacted with a filtering system coded in Perl language. All tests were done using a laptop computer powered by an Intel core i5 CPU (2.27 Ghz, only one CPU core is used) and using 2.8 GB of RAM. These tests compared the behavior of our constrained EA algorithm with the exact branch-and-bound algorithm.

First Experimentation: Problem Size and Constraint Densities

An initial first model, named "full model" is considered. It can be consulted and interactively used at http://cofiade.enstimac.fr/cgi-bin/cofiade.pl select model 'Aircraft-CSP-EA-10'. It gathers five product variables with a domain size between 4 and 6, six production operations with a number of possible resources between 3 and 25. Without constraints consideration, the solution space of the product model is 5,184, and the planning model is 96,000. The size of the global problem model is 497,664,000. A second model, named "small model", has been derived from the previous one with the suppression of a high combinatory task and a reduction of one domain size. This reduces the planning problem size to 12,000 and global model 6,220,800. In order to evaluate the impact of constraints density, two versions of each model were produced: one with a "weak density" of constraints (20% of possible combinations are excluded in each constraint Cc and Cp) and the other with a "high density" of constraints (50% excluded). These values are frequently met in industrial configuration situations. This provides four models characteristics in table 1.

Solution quantity

Without For the small models, evolutionary settings are tuned to: population size: 50; archive size: 40; Pmut: 0.4; Pcross: 0.8. The ending criterion used is a time limit of half an hour. For the full models, we adapt settings for a wider search: population size: 150; archive size: 100; Pmut: 0.4; Pcross: 0.8. The ending criterion used is the time required by the BB algorithm. In order to analyze the two optimization approaches, we compare the hypervolume evolution during optimization process. Hypervolume metric has been defined in [START_REF] Zitzler | Multiobjective Optimization Using Evolutionary Algorithms -A Comparative Case Study[END_REF]. It measures the hypervolume of space dominated by a set of solutions and is illustrated in Figure 5. 6 where EA curves are average results for 30 executions. Both algorithms start with a lapse of time where performance is null. For the BB algorithm, this corresponds to the time needed to reach a first leaf on the search tree, while for the EA; it corresponds to the time consumed to constitute the initial population.

For the small models (first two curves), the BB algorithm reaches the optimal Pareto front much faster compared with EA performance. On the other hand, when the problem size increases, the EA is logically better than the BB algorithm on the full model. For example, on the low-constrained model, the BB algorithm took 20 times longer to reach a good set of solutions (less than 0.5% of the optimal hypervolume).

The impact of constraints density could also be discussed. As it can be seen, the BB algorithm performance is improved when the density of constraints is high. Indeed the filtering allows more branches to be cut on the search tree, in such way that the algorithm reaches leaf solutions and, consequently, optimal solutions more quickly. The EA performance moves in the opposite way. The more the model is constrained, the more the random crossover operation will have to backtrack to find feasible solutions, and thus the time needed by the algorithm will be consequent.

Experimentations on Problem Size

In order to try to identify the problem size where EA is more suitable than BB, we have modified the low constrained model as follows. We consider now a model gathering six product variables and six production operations with three possible values for each, and sequentially add either a product variable and or an operation. The range of study is between 12 and 16 decision variables with three possible values for each. Relevant solution spaces without constraint vary between 1.6*10 6 and 43*10 6 .

The results are shown in the left part of figure 7. The vertical axis corresponds with the computation time and the horizontal one with the number of decision variables. For BB curves, it shows the time to reach the optimal solution. For the EA curve it shows the time required for nine EA runs over ten to reach the optimal solution. Order of magnitude are close for both around 13 or 14 variables corresponding with a solution space around 2*10 6 to 5*10 6 comparable with our previous small model size.

Fig. 7. Experimentation results dealing with problem size

As we already mentioned, industrial models are frequently larger than that. We therefore try our EA approach with a low constrained model with 30 variables and a solution space around 10 16 . The stopping criterion is "2 hours without improvement". The right part of figure 7 shows that the optimization process has stopped after 48 hours (172800 seconds). It can be noticed that 90% of the final score was obtained after 3 hours and 99% in 10 hours. This allows underlining the good performance of our approach when facing large low constrained problem.

Finally we also try to break optimization in two steps. The idea is: (i) compute quickly a low quality Pareto, (ii) select the area that interest the customer (iii) compute a Pareto on the restricted area. The restricted area is obtained by constraining the two criteria total cost and cycle time (or interesting area) and filtering these reductions on the whole problem. The search space is greatly reduced and the second optimization much faster. This is shown in figure 8

Fig. 1 .

 1 Fig. 1. Example of a concurrent configuration and planning CSP model

Fig. 2 .Fig. 3 .

 23 Fig. 2. Concurrent configuration and planning model to optimize

Fig. 5 .

 5 Fig. 5. Hypervolume linked to a Pareto front

Fig. 6 .

 6 Fig. 6. First experimentation results

  where the left part shows the single step process with 10 and 60 minutes Pareto and the right part shows the restricted area with the two previous curve and the one corresponding with a 10 minutes Pareto launched on the restricted area. It shows that the sequence of two optimization steps of 10 minutes provide a result almost equivalent (only 3 points are missing) to a 60 minutes optimization process.

Fig. 8 .

 8 Fig. 8. Experimentations with a two steps optimization process

Table 1 .

 1 Problems characteristics

		constraints	Low density	High density
	Small model	6 220 800	595 000	153 000
	Full model	497 664 000	47 600 000	12 288 000

Conclusions

The goal of this communication was to propose a first evaluation of an adapted evolutionary algorithm that deals with concurrent product configuration and production planning. The problem was recalled and the two optimization approaches (Evolutionary algorithm and branch and bound) where briefly presented. Various experimentations have been presented. A first result is that: (i) the proposed EA works fine when the size of the problem gets large compare to the BB, (ii) when problem tends to be more constrained the tendency goes to the opposite. When problem is low constrained (90% of excluded solutions) with 13-14 decision variables with 3 values each, they perform equally. When the problem gets larger, BB cannot be considered and EA can provide good quality results for the same problem with up to 30 variables (around 10 16 solutions -90% unfeasible). Finally some ideas about a two steps optimization process have shown that the proposed approach is quite promising for large problems. These are first experimentation results and we are now working on comparing our proposed EA with some penalty function approaches.