=Paper=
{{Paper
|id=Vol-1128/intro6
|storemode=property
|title=Improving Configuration and Planning Optimization: Towards a Two Tasks Approach
|pdfUrl=https://ceur-ws.org/Vol-1128/paper6.pdf
|volume=Vol-1128
|dblpUrl=https://dblp.org/rec/conf/confws/PitiotAVCG13
}}
==Improving Configuration and Planning Optimization: Towards a Two Tasks Approach==
https://ceur-ws.org/Vol-1128/paper6.pdf
Paul Pitiot, Michel Aldanondo, Élise Vareilles, Thierry Coudert, Paul Gaborit 43
Improving configuration and planning optimization:
Towards a two tasks approach
Paul Pitiot1,2, Michel Aldanondo1, Elise Vareilles1, Thierry Coudert3, Paul Gaborit1
1
University Toulouse – Mines Albi, France
2
3IL-CCI Rodez, France
3
University Toulouse – INP-ENI Tarbes, France
Paul.pitiot@mines-albi.fr
Abstract requirements are then used to support the optimization of
both product and production process.
This paper deals with mass customization and the Given this problem, product performance, process cycle
association of the product configuration task with time and process plus product cost can be optimized, we
the planning of its production process while trying to therefore deal with a multi-criteria problem and our goal is
minimize cost and cycle time. Our research aims at to propose to the user solutions belonging to the Pareto
producing methods and constraint based tools to front. For simplicity we only consider cycle time and total
support this kind of difficult and constrained prob- cost (product cost plus process cost), consequently the two-
lem. In some previous works, we have considered an step process can be illustrated as shown in figure 1.
approach that combines interactivity and optimiza-
tion issues and propose a new specific optimization
algorithm, CFB-EA (for constraint filtering based
evolutionary algorithm). This article concerns an
improvement of the optimization step for large prob-
lems. Previous experiments have highlighted that
CFB-EA is able to find quickly a good approxima-
tion of the Pareto Front. This led us to propose to
split the optimization step in two sub-steps. First, a
“rough” approximation of the Pareto Front is quickly
searched and proposed to the user. Then the user in-
dicates the area of the Pareto Front that he is inter-
ested in. The problem is filtered in order to restrain
the solution space and a second optimization step is Figure 1 - Two-step process
done only on the focused area. The goal of the arti-
cle is to compare thanks to various experimentations Some experimental studies, reported last year [Pitiot et al.,
the classical single step optimization with the two 2012], discusses optimization performance according to
sub-steps proposed approach. problem characteristics (mainly size and constraint level).
That last paper proposes to divide the step 2 (Pareto front
1 Introduction computation) in two tasks, particularly in the case of large
problems: (i) a first rough computation that permit to have a
This article is about the concurrent optimization of product global idea of possible compromises (ii) a second computa-
configuration and production planning. Each problem is tion on a restricted area that is selected by the user. The goal
considered as a constraint satisfaction problem (CSP) and of this article is to present experimental results that show
these two CSP problems are also linked with some con- that this idea allows to significantly reducing optimization
straints. In a previous paper [Pitiot et al., 2013], we have duration while improving optimization quality.
shown that this allows to consider a two-step process: (i) In this introduction, we clarify with a very simple example
interactive configuration and planning, where non- what we mean by concurrent configuration and planning
negotiable user requirements (product requirements and problem and relevant optimization needs. Then the second
production process requirements) are first processed thanks section formalizes the optimization problem, presents the
to constraint filtering and reduce the solution space (ii) op- optimization algorithm and describes the experimental
timization of configuration and planning, where negotiable study. The third section is dedicated to various experimenta-
tions.
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
44 Paul Pitiot, Michel Aldanondo, Élise Vareilles, Thierry Coudert, Paul Gaborit
1.1 Configuration and planning processes. linking seats with sourcing, Cp1 (Seat, R-Sourc, D-Sourc),
and a second one linking range with the assembling, Cp2
Many authors, since [Mittal and Frayman, 1989], [Soininen (Range, R-Assem, D-Assem). The allowed combinations of
et al., 1998] or [Aldanondo et al., 2008] have defined con- each constraint are shown in the 3 tables of figure 2 and lead
figuration as the task of deriving the definition of a specific to 12 solutions for both product and production process.
or customized product (through a set of properties, sub-
assemblies or bill of materials, etc…) from a generic prod-
uct or a product family, while taking into account specific
customer requirements. Some authors, like [Schierholt
2001], [Bartak et al., 2010] or [Zhang et al. 2013] have
shown that the same kind of reasoning process can be con-
sidered for production process planning. They therefore
consider that deriving a specific production plan (opera-
tions, resources to be used, etc...) from some kind of generic
process plan while respecting product characteristics and
customer requirements, can define production planning.
Many configuration and planning studies (see for example Figure 2 - Concurrent configuration and planning CSP model
[Junker, 2006] or [Laborie, 2003]) have shown that each
problem could be successfully considered as a constraint 1.2 Optimization needs
satisfaction problem (CSP). We proposed to associate them
in a single CSP in order to process them concurrently. With respect to the previous problem, once the customer or
This concurrent process and the supporting constraint the user has provided his non-negotiable requirements, he is
framework present three main interests. First they allow frequently interested in knowing what he can get in terms of
price and delivery dates (performance is not considered any
considering constraints that links configuration and planning
more). Consequently, the previous model must be updated
in both directions (for example: a luxury product finish re-
with some variables and numerical constraints in order to
quires additional manufacturing time or a given assembly compute the two criteria. The cycle time matches the ending
duration forbids the use of a particular kind of component). date of the last production operation of the configured prod-
Secondly they allow processing planning requirements even uct. Cost is the sum of the product cost and process cost.
if product configuration is not completely defined, and
therefore avoid the traditional sequence: configure product
then plan its production. Thirdly, CSP fit very well on one
side, interactive process thanks to constraint filtering tech-
niques, 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 problem to solve we recall the very
simple example, proposed in [Pitiot et al., 2012], dealing
with the configuration and planning of a small plane. The
constraint model is shown in figure 2. 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 configuration constraint Cc1 forbids a plane
with 4 seats and a range of 600 kms. The production process
contains two operations: sourcing and assembling. (noted Figure 3 - CSP model to optimize
Sourc and Assem). Each operation is described by two pro-
cess variables: resource and duration: for sourcing, the re- The model of figure 2 is completed in figure 3. For cost,
source (R-Sourc, possible resources “Fast-S” and “Slow-S”) each product variable and each process operation is associ-
and duration (D-Sourc, possible values 2, 3, 4, 6 weeks), for ated with a cost parameter and a relevant cost constraint: (C-
assembling, the resource (R-Assem, possible resources Seats, Cs1), (C-Range, Cs2), (C-Sourc, Cs3) and (C-Assem,
“Quic-A” and “Norm-A”) and duration (D-Assem, possible cs4) detailed in the tables of figure 3.
values 4, 5, 6, 7 weeks). The total cost and cycle time are obtained with a numerical
constraint as follows:
Two process constraints linking product and process varia- Total cost = C-Seats + C-Range + C-Sourc + C-Assem.
bles modulate configuration and planning possibilities: one Cycle time = D-Sourc + D-Assem
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
Paul Pitiot, Michel Aldanondo, Élise Vareilles, Thierry Coudert, Paul Gaborit 45
The twelve previous solutions are shown on the figure 4 The constrained optimization problem (O-CSP) is defined
with the Pareto front gathering the optimal ones. The goal of by the quadruplet where V is the set of deci-
this article is to improve the computation of this Pareto front sion variables, D the set of domains linked to the variables
with respect to the user preference. of V, C the set of constraints on variables of V and f the
multi-valued fitness function. The set V gathers: the product
variables and the resource process variables (we assume that
duration process variables are deduced from product and
resource). The set C gathers: only configuration constraints
(Cc) and process constraints (Cp). The variables operation
durations and cycle time are linked with a numerical con-
straint that does not impact solution definition and therefore
does not belong to V and C. The same applies to the prod-
uct/process cost variables and total cost, which are linked
with cost constraints (Cs) and total cost constraints. The
filtering system allows dynamically updating the domain of
all these variables with respect to the constraints. The varia-
bles belonging to V are all symbolic or at least discrete. Du-
ration and cost variables are numerical and continuous.
Therefore, constraints are discrete (Cc), numerical (cycle
time and total cost) or mixed (Cp and Cs). Discrete con-
straints filtering is processed using a conventional arc con-
Figure 4 – Problem solutions and Pareto front sistency technique [Bessiere, 2006] while numerical con-
straints are processed using bound consistency [Lhomme,
1993].
2 Optimization problem and techniques
2.2 Optimization algorithm
The optimization problem is first defined, and then the op- A strong specificity of this kind of optimization problem is
timization algorithm that will be used is described. Finally, that the solution space is large. [Amilhastre et al, 2002] re-
the experimental process is introduced. port that a configuration solution space of more than
2.1 Optimization problem 1.4*1012 is required for a car-configuration problem. When
planning is added, the combinatorial structure can become
The optimization problem can be generalized as the one huge. Another specificity lies in the fact that the shape of
shown in figure 5. the solution space is not continuous and, in most cases,
shows many singularities. Furthermore, the multi-criteria
problem 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
[Hong et al., 2010] or [Li et al., 2006] consider genetic or
evolutionary approaches to deal with this problem. In this
article we will use “CFB-EA” (for Constraint Filtering
Based Evolutionary Algorithm) a promising algorithm that
we have designed specifically for this problem.
CFB-EA is based on the SPEA2 method [Zitzler et al.,
2001] which is one of the most useful Pareto-based meth-
ods. It’s based on the preservation of a selection of best so-
lutions in a separate archive. It includes a performing evalu-
ation strategy that brings a well-balanced population density
on each area of the search space, and it uses an archive trun-
cation process that preserves boundary solution. It ensures
both a good convergence speed and a fair preservation of
solutions diversity.
To deal with constrained problems, we completed this
Figure 5 – Constrained optimization problem method with specific evolutionary operators (initialization,
uniform mutation and uniform crossover) that preserve fea-
sibility of generated solutions.
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
46 Paul Pitiot, Michel Aldanondo, Élise Vareilles, Thierry Coudert, Paul Gaborit
This provides the six steps following approach: tion, (ii) we have an user who can possibly refine his criteria
1. Initialization of individual set that respect the con- requirements with regard to the solutions obtained during
straints (thanks to filtering), optimization process ; (iii) CFB-EA is relevant for the range
2. Fitness assignment (balance of Pareto dominance and of concurrent configuration and planning problems required
solution density) (size and constraints level) and more particularly it can pro-
3. Individuals selection and archive update pose, in a reasonable amount of time, a good approximation
4. Stopping criterion test of the Pareto Front that allows the user to decide about his
5. Individuals selection for crossover and mutation opera- own cost/cycle time compromise.
tors (binary tournaments) 2.3 Two-task optimization approach.
6. Individuals crossover and mutation that respect the con-
straints (thanks to filtering) As explained in the introduction, the goal of this article is to
7. Return to step 2. evaluate, for large problem, the interest of replacing the
single shot Pareto front computation by two successive
For initialization, crossover and mutation operators, each tasks: (i) a first rough computation that provides a global
time an individual is created or modified, every gene (deci- idea of possible compromises (ii) a second computation on a
sion variable of V) is randomly instantiated into its current restricted area selected by the user.
domain. To avoid the generation of unfeasible individuals, This is shown in the illustration of figure 6. The left part of
the domain of every remaining gene is updated by constraint figure 6 shows a single shot Pareto. The right part of figure
filtering. As filtering is not full proof, inconsistent individu- 6 shows a rough Pareto quickly obtained (first task), fol-
als can be generated. In this case a limited backtrack process lowed by a zoom selected by the user (max cost and max
is launched to solve the problem. This approach doesn’t time) and a second Pareto computation only on this restrict-
need any additional parameter tuning for constraint han- ed area (second task). The restricted area is obtained by con-
dling. In the following, we will briefly remind the principles straining the two criteria total cost and cycle time (or inter-
and operators used in CFB-EA. esting area) and filtering these reductions on the whole
Many research studies try to integrate constraints in EA. C. problem.
Coello Coello proposes a synthetic overview in [Mezura- Total cost Total cost
Montes and Coello Coello 2011]. The current tendencies in max cost
the resolution of constrained optimization problem using
EAs are penalty functions, stochastic ranking, ε-constrained, 2nd Pareto on
multi-objective concepts, feasibility rules and special opera- restricted area
tors. CFB-EA belongs to this last family.
The special operators class gathers methods that try to deal
only with feasible individuals like repairing methods,
preservation of feasibility methods or operator that move
Rough 1rst Pareto
solutions within a specific region of interest within the Single shot
search space as for example the boundaries of the feasible Pareto
region. Generally and has we verified on our last experi- max time
mentations, these methods are known to be performing on
non-over-constrained problems (i.e. a feasible solution can Cycle time Cycle time
be obtained in a reasonable amount of time to be able to Figure 6 – Single shot and two-task optimization principles
generate a population of solutions).
CFB-EA aims at preserving the feasibility of the individuals The second optimization task does not restart from scratch.
during their construction or modification. Proposed specific It benefits from the individuals of the archive that belongs to
evolutionary operators prune search space using constraint the restrained area founded during first task. We thus re-
filtering. The main difference between our approach and placed the initialization of our CFB-EA (constitution of the
others is that we do not have any infeasible solution in our first population) by a selection of a set of the best solutions
population or archive. Each time we modify an individual, obtained during the first rough optimization.
the constraints filtering system is used in order to verify This provides the following process:
consistency preservation of individuals. 1. Interactive configuration and planning using non-
Previous experimentations [Pitiot et al., 2012] allowed us to negotiable requirements of the user (as before),
verify that the exact approaches are limited to problems of 2.1 - 1st global optimization task on negotiable requirements
limited size and that CFB-EA is completely competitive for of the user
the level of constraint of the models which interest us. In 2.2 - 2nd optimization on interesting area initialized with
this article, we propose a new two sub-step optimization individuals of the previous step.
approach that takes advantage of the three following charac-
teristics: (i) EA are anytime algorithms, e.g. they can supply
a set of solutions (Pareto Front) at any time after initializa-
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
Paul Pitiot, Michel Aldanondo, Élise Vareilles, Thierry Coudert, Paul Gaborit 47
3 Experimentations - Aircraft_zoom_1: area that correspond to solutions with
a cycle time less than 410 (solutions with shortest cycle
times),
3.1 Model used and performance measure - Aircraft_zoom_2: area that correspond to solutions with
a cycle time less than 470 and a total cost less than 535
The goal of the proposed experiments is to compare these (compromise solutions),
two optimization approaches (single-shot and two-task op- - Aircraft_zoom_3: area that correspond to solutions with
timization approaches) in terms of result quality and compu- a total cost less than 475 (solutions with lowest total
tation time. In terms of quality we want to compare the two costs).
fronts and will use the Hypervolume measurement proposed
by [Zitzler and Thiele 1998] which is illustrated in figure 7.
It measures the hypervolume of the space dominated by a
set of solutions. It thus allows evaluating both convergence
and diversity proprieties (the fittest and most diversified set
of solutions is the one that maximizes hypervolume). In
terms of computation time, we want to evaluate, for a given
Hypervolume result the time reduction provided by the se-
cond approach.
Figure 8 –Pareto-fronts obtained on “full aircraft model” after 3
and 24 hours of computation
These three areas correspond with a division of the final
Pareto front obtained after 24h of computation in three equal
parts. These areas have been selected in order to evaluate
performance of the proposed two-task approach, but it also
corresponds with some classical preference of a user who
could wish: (i) a less expensive plane, (ii) a short cycle time,
(iii) a compromise between total cost and cycle time. We
Figure 7 – Hyper volume definition will discuss this aspect in section 3.3.
The optimization algorithms were implemented in C++ pro-
In terms of problem size, we consider a model called “full_ gramming language and interacted with the filtering system
aircraft” that gathers 92 variables (symbolic, integer or float coded in Perl language. All tests were done using a laptop
variables) linked by 67 constraints (compatibility tables, computer powered by an Intel core i5 CPU (2.27 Ghz, only
equations or inequalities). Among these variables, we find one CPU core is used) and using 2.8 Go of ram.
21 decision variables that will be manipulated by the opti-
mization algorithms (chromosome in EAs): 3.2 Two-task approach evolutionary settings
- 12 variables (each with 6 possible discrete values) that
describe product customization possibilities, For a first experimentation of the two-task approach, we use
- 9 variables (each with 9 possible discrete values) that classical evolutionary settings (e.g. the same evolutionary
describe production process possibilities. In fact, the settings used for the single-shot approach: Population size:
nine values aggregate 3 resource types and 3 resource 80, Archive size: 100, Individual Mutation Probability: 0.3,
quantities for each of the 9 process operations that Gene Mutation Probability: 0.2, Crossover Probability: 0.8).
compose the production process. The main difference with the single-shot approach is with
Without any constraints, this provides a number of possible the backtrack limit (e.g. number of allowed backtrack in
combinations around 1018 (≈ 612 x 99). An average constraint mutation or crossover operator). This limit has been set to
level (around 93% of solutions rejected) allows 7.3*1016 100 in the one-shot approach and to 30 in the two-step ap-
feasible solutions. Results of experimentation’s with other proach.
model sizes and other constraint levels can be consulted in Indeed in the two-step approach, it could be time consuming
[Pitiot et al., 2012]. to obtain a valid solution. For example with the single-shot
optimization, only 2.5% of filtered individuals were unfea-
Figure 8 shows the Pareto Fronts obtained with CFB-EA sible and none of them were abandoned; while with the two-
after 3 and 24 hours of computation. The rough Pareto front task approach and a lower backtrack limit, around 7% of
obtained after 3 hours of computation allows the user to filtered individuals were unfeasible and 0.3% of them were
decide in which area he is interested in. In the next sub- abandoned. So a lower backtrack limit reduces the time
section, we will study a division of this Pareto front in three spend to try to repair unfeasible individuals.
restricted area:
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
48 Paul Pitiot, Michel Aldanondo, Élise Vareilles, Thierry Coudert, Paul Gaborit
The only other difference between single-shot CFB-EA and - average % standard deviation of hypervolume
two-task CFB-EA is the stopping criterion. While in single- - average computation time,
shot approach, we use a fix time limit (24hours), the two- - average % standard deviation of computation time,
task approach uses a bcondition stopping test that stops ei- - maximum value of hypervolume.
ther if there is no HV improvement after 2 hours or after 12
hours of computation (that must be added to the three initial
hours for getting the rough Pareto Front).
3.3 Experimental results
The goal of this section is to evaluate the two-task optimiza-
tion on the three selected areas of figure 8 (zoom 1, zoom 2
and zoom3) with respect to the single-shot optimization.
First result illustrations
Figure 9 illustrates an example of the Pareto fronts that can
be obtained on the zoom 1 area :
- rough Pareto obtained after 3 hours (fig 9 squares),
- two-task, after 3+12 hours (fig 9 triangles),
- single-shot, stopped after 24 hours (fig 9 diamonds).
Figure 9 –Example of Pareto fronts obtained on zoom1
The Pareto Fronts obtained by the two approaches (single-
shot and two-task) are very close when the cycle is greater
than 355. For lower cycle times, the proposed two-task ap-
proach is a little better. However, these curves correspond
with a specific run. In order to derive stronger conclusions, Figure 10 – Evolution of hypervolume
10 executions of the two approaches have been achieved for
each of the three zoom areas. In terms of quality, the new proposed approach (two-task
optimization) allows to obtain a similar performance with
Detailed comparisons respect to single-shot one:
- 0.4% worse on zoom1
Detailed experimental results achieved on the three zoom - 1% worse on zoom2
areas are presented in figure 10 and table 1. - 4% better on zoom3
On each graph of figure, the vertical axis corresponds to the but in around half of computing time:
hyper volume (average of ten runs) reach and horizontal one - 13 h instead of 24h for on zoom1
is the time spent. At time 0, the single-shot optimization is - 13.5h instead of 24h for on zoom2
launched (dotted line). After 3 hours (10800 seconds): - 10.5h instead of 24h for on zoom 3.
- the single-shot keeps going on (dotted line), Furthermore, this computing time includes the 2 hours of
- the two-task is launched (solid line). computation without any hypervolume reduction before
The table provides numeric results for each zoom area. The stopping (stopping criterion of the two-task approach).
columns display the single-shot, two-task and % gap of:
- average final hypervolume,
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
Paul Pitiot, Michel Aldanondo, Élise Vareilles, Thierry Coudert, Paul Gaborit 49
It can be seen on the figure10 that when the single-shot Front, to ask the user about an interesting area and, to
CFB-EA has trouble to obtain a good Pareto Front during launch Pareto computation only on this area.
the first three hours, the more the two-task CFB-EA is per- According to experimental results, in terms of computation
forming. On zoom1 area, single-shot CFB-EA reaches rela- time, the new two-task approach allows a significant time
tively quickly a near-final Pareto Front; while on zoom3 saving around half of the previous time needed by the sin-
area, it reaches it very slowly. gle-shot optimization approach. In terms of quality, Hyper-
volume computation are very close or even a little better in
Singleshot Twotask some case.
gap in %
CFBEA CFBEA Furthermore, these results have been obtained on a rather
Average large problem that contains around 1016/1017 solutions. With
5849 5823 0.4 smaller problems, the proposed approach should perform
Final HV
Average much better. We are already working on a more extensive
3.8% 5.1%
Zoom1
HV RSD test (different model size and different level of constraints)
Total as we did in [Pitiot et al., 2012]. Another key aspect that
86400(24h) 47996 (≈13h) 44.6 needs to be study is to find a way to define the rough Pareto
time
computation time.
Total
time 0 15%
RSD
Max HV 6043 6057 0.2 References
Singleshot Twotask
gap in %
CFBEA CFBEA [Aldanondo et al., 2008] M. Aldanondo, E. Vareilles. Con-
Average figuration for mass customization: how to extend prod-
1758 1740 1.
Final HV uct configuration towards requirements and process con-
Average figuration, Journal of Intelligent Manufacturing, vol. 19
2.1% 2.3%
Zoom2
HV RSD n° 5, p. 521-535A (2008)
Total [Amilhastre et al, 2002] J. Amilhastre, H. Fargier, P. Mar-
86400(24h) 48501 (≈13.5h) 44
time quis, Consistency restoration and explanations in dynam-
Total ic csps - application to configuration, in: Artificial Intel-
time 0 16% ligence vol.135, 2002, pp. 199-234.
RSD
[Bartak et al., 2010] R. Barták, M. Salido, F. Rossi. Con-
Max HV 1795 1776 1 straint satisfaction techniques in planning and schedul-
Singleshot Twotask ing, in: Journal of Intelligent Manufacturing, vol. 21,
gap in % n°1, p. 5-15 (2010)
CFBEA CFBEA
[Bessiere, 2006] C. Bessiere, Handbook of Constraint Pro-
Average
1765 1844 4.4 gramming, Eds. Elsevier, chap. 3 Constraint propaga-
Final HV
tion, 2006, pp. 29-70.
Average
3.16% 0.07%
Zoom3
HV RSD [Hong et al., 2010] G. Hong, D. Xue, Y. Tu,, Rapid identifi-
Total cation of the optimal product configuration and its pa-
86400(24h) 38185 (≈10.5h) 55.9 rameters based on customer-centric product modeling
time
for one-of-a-kind production, in: Computers in Industry
Total
time 0 26%
Vol.61 n°3, 2010, pp. 270–279.
RSD [Junker, 2006] U. Junker. Handbook of Constraint Pro-
Max HV 1831 1845 0,7 gramming, Elsevier, chap. 24 Configuration, p. 835-875
(2006)
Table 1. Comparison of the two approaches
[Laborie, 2003] P. Laborie. Algorithms for propagating re-
4 Conclusions source constraints in AI planning and scheduling: Exist-
ing approaches and new results, in: Artificial Intelli-
The goal of this paper was to evaluate a new optimization gence vol 143, 2003, pp 151-188.
principle that can handle concurrent configuration and plan-
[Lhomme, 1993] O. Lhomme. Consistency techniques for
ning. First the background of concurrent configuration and
numerical CSPs, in: proc. of IJCAI 1993, pp. 232-238.
planning has been recalled with associated constrained
modeling elements. Then an initial optimization approach [Li et al., 2006] L. Li, L. Chen, Z. Huang, Y. Zhong, Prod-
(single-shot CFB-EA) was described followed by the two- uct configuration optimization using a multiobjective
task approach object of this paper. GA, in: I.J. of Adv. Manufacturing Technology vol. 30,
Instead of computing a Pareto Front on the whole solution 2006, pp. 20-29.
space, the key idea is: to compute quickly a rough Pareto
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
50 Paul Pitiot, Michel Aldanondo, Élise Vareilles, Thierry Coudert, Paul Gaborit
[Mezura-Montes and Coello Coello 2011] E. Mezura-
Montes, C. Coello Coello, Constraint-Handling in Na-
ture-Inspired Numerical Optimization: Past, Present and
Future, in: Swarm and Evolutionary Computation, Vol. 1
n°4, 2011, pp. 173-194
[Mittal and Frayman, 1989] S. Mittal, F. Frayman. Towards
a generic model of configuration tasks, proc of IJCAI, p.
1395-1401(1989).
[Pitiot et al., 2012] P. Pitiot, M. Aldanondo, E. Vareilles, L.
Zhang, T. Coudert. Some Experimental Results Relevant
to the Optimization of Configuration and Planning Prob-
lems, in : Lecture Notes in Computer Science Volume
7661, 2012, pp 301-310
[Pitiot et al., 2013] P. Pitiot, M. Aldanondo, E. Vareilles, P.
Gaborit, M. Djefel, S. Carbonnel, Concurrent product
configuration and process planning, towards an approach
combining interactivity and optimality, in: I.J. of Pro-
duction Research Vol. 51 n°2, 2013 , pp. 524-541.
[Schierholt 2001] K. Schierholt. Process configuration:
combining the principles of product configuration and
process planning AI EDAM / Volume 15 / Issue 05 / no-
vembre 2001 , pp 411-424
[Soininen et al., 1998] T. Soininen, J. Tiihonen, T. Männis-
tö, and R. Sulonen, Towards a General Ontology of Con-
figuration., in: Artificial Intelligence for Engineering
Design, Analysis and Manufacturing vol 12 n°4, 1998,
pp. 357–372.
[Zhang et al., 2013] L. Zhang, E. Vareilles, M. Aldanondo.
Generic bill of functions, materials, and operations for
SAP2 configuration, in: I.J. of Production Research Vol.
51 n°2, 2013 , pp. 465-478.
[Zitzler and Thiele 1998] E. Zitzler, L. Thiele, Multiobjec-
tive optimization using evolutionary algorithms - a com-
parative case study, in: proc. of 5th Int. Conf. on parallel
problem solving from nature, Eds. Springer Verlag,
1998, pp. 292-301.
[Zitzler et al., 2001] E. Zitzler, M. Laumanns, L. Thiele.,
SPEA2: Improving the Strength Pareto Evolutionary Al-
gorithm, Technical Report 103, Swiss Fed. Inst. of
Technology (ETH), Zurich (2001)
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria