This paper 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. Our research aims at producing methods and constraint based tools to support this kind of difficult and constrained problem. In some previous works, we have considered an approach that combines interactivity and optimization 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 problems. Previous experiments have highlighted that CFB-EA is able to find quickly a good approximation 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 indicates the area of the Pareto Front that he is interested in. The problem is filtered in order to restrain the solution space and a second optimization step is done only on the focused area. The goal of the article is to compare thanks to various experimentations the classical single step optimization with the two sub-steps proposed approach.
This article is about the concurrent optimization of product configuration and production planning. Each problem is considered as a constraint satisfaction problem (CSP) and these two CSP problems are also linked with some constraints. In a previous paper [Pitiot et al., 2013], we have shown that this allows to consider a two-step process: (i) interactive configuration and planning, where nonnegotiable user requirements (product requirements and production process requirements) are first processed thanks to constraint filtering and reduce the solution space (ii) optimization of configuration and planning, where negotiable requirements are then used to support the optimization of both product and production process.
Given this problem, product performance, process cycle time and process plus product cost can be optimized, we therefore deal with a multi-criteria problem and our goal is to propose to the user solutions belonging to the Pareto front. For simplicity we only consider cycle time and total cost (product cost plus process cost), consequently the twostep process can be illustrated as shown in figure 1.
Figure 1 - Two-step process Some experimental studies, reported last year [Pitiot et al., 2012], discusses optimization performance according to problem characteristics (mainly size and constraint level). That last paper proposes to divide the step 2 (Pareto front computation) in two tasks, particularly in the case of large problems: (i) a first rough computation that permit to have a global idea of possible compromises (ii) a second computation on a restricted area that is selected by the user. The goal of this article is to present experimental results that show that this idea allows to significantly reducing optimization duration while improving optimization quality.
In this introduction, we clarify with a very simple example what we mean by concurrent configuration and planning problem and relevant optimization needs. Then the second section formalizes the optimization problem, presents the optimization algorithm and describes the experimental study. The third section is dedicated to various experimentations. 1.1
Many authors, since [Mittal and Frayman, 1989], [Soininen
et al., 1998] or [Aldanondo et al., 2008] have defined
configuration as the task of deriving the definition of a specific
or customized product (through a set of properties,
subassemblies or bill of materials, etc…) from a generic
product 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
considered for production process planning. They therefore
consider that 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.
Many configuration and planning studies
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 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 process 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 2 and lead to 12 solutions for both product and production process. With respect to the previous problem, once the customer or the user has provided his non-negotiable requirements, he is frequently interested in knowing what he can get in terms of price and delivery dates (performance is not considered any more). Consequently, the previous model must be updated with some variables and numerical constraints in order to compute the two criteria. 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. The model of figure 2 is completed in figure 3. For cost, each product variable and each process operation is associated with a cost parameter and a relevant cost constraint: (CSeats, Cs1), (C-Range, Cs2), (C-Sourc, Cs3) and (C-Assem, cs4) detailed in the tables of figure 3.
The total cost and cycle time are obtained with a numerical constraint as follows: 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 4 with the Pareto front gathering the optimal ones. The goal of this article is to improve the computation of this Pareto front with respect to the user preference.
The optimization problem is first defined, and then the optimization algorithm that will be used is described. Finally, the experimental process is introduced. 2.1
The optimization problem can be generalized as the one shown in figure 5. The constrained optimization problem (O-CSP) 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-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 constraint that does not impact solution definition and therefore does not belong to V and C. The same applies to the product/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 variables belonging to V are all symbolic or at least discrete. Duration and cost variables are numerical and continuous. Therefore, constraints are discrete (Cc), numerical (cycle time and total cost) or mixed (Cp and Cs). Discrete constraints filtering is processed using a conventional arc consistency technique [Bessiere, 2006] while numerical constraints are processed using bound consistency [Lhomme, 1993]. A strong specificity of this kind of optimization problem is that the solution space is large. [Amilhastre et al, 2002] report that a configuration solution space of more than 1.4*1012 is required for a car-configuration problem. When planning is added, the combinatorial structure can become huge. Another specificity lies in the fact that the shape of 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 methods. It’s based on the preservation of a selection of best solutions in a separate archive. It includes a performing evaluation strategy that brings a well-balanced population density on each area of the search space, and it uses an archive truncation 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 method with specific evolutionary operators (initialization, uniform mutation and uniform crossover) that preserve feasibility of generated solutions. 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 the 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. This approach doesn’t need any additional parameter tuning for constraint handling. In the following, we will briefly remind the principles and operators used in CFB-EA.
Many research studies try to integrate constraints in EA. C. Coello Coello proposes a synthetic overview in [MezuraMontes and Coello Coello 2011]. The current tendencies in the resolution of constrained optimization problem using EAs are penalty functions, stochastic ranking, ε-constrained, multi-objective concepts, feasibility rules and special operators. 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 solutions within a specific region of interest within the search space as for example the boundaries of the feasible region. Generally and has we verified on our last experimentations, these methods are known to be performing on non-over-constrained problems (i.e. a feasible solution can be obtained in a reasonable amount of time to be able to generate a population of solutions).
CFB-EA aims at preserving the feasibility of the individuals during their construction or modification. Proposed specific evolutionary operators prune search space using constraint filtering. The main difference between our approach and others is that we do not have any infeasible solution in our population or archive. Each time we modify an individual, the constraints filtering system is used in order to verify consistency preservation of individuals.
Previous experimentations [Pitiot et al., 2012] allowed us to verify that the exact approaches are limited to problems of limited size and that CFB-EA is completely competitive for the level of constraint of the models which interest us. In this article, we propose a new two sub-step optimization approach that takes advantage of the three following characteristics: (i) EA are anytime algorithms, e.g. they can supply a set of solutions (Pareto Front) at any time after initialization, (ii) we have an user who can possibly refine his criteria requirements with regard to the solutions obtained during optimization process ; (iii) CFB-EA is relevant for the range of concurrent configuration and planning problems required (size and constraints level) and more particularly it can propose, in a reasonable amount of time, a good approximation of the Pareto Front that allows the user to decide about his own cost/cycle time compromise. 2.3
As explained in the introduction, the goal of this article is to evaluate, for large problem, the interest of replacing the single shot Pareto front computation by two successive tasks: (i) a first rough computation that provides a global idea of possible compromises (ii) a second computation on a restricted area selected by the user.
This is shown in the illustration of figure 6. The left part of figure 6 shows a single shot Pareto. The right part of figure 6 shows a rough Pareto quickly obtained (first task), followed by a zoom selected by the user (max cost and max time) and a second Pareto computation only on this restricted area (second task). 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.
Total cost
Total cost max cost 2nd Pareto on restricted area
Rough 1rst Pareto Single shot Pareto
max time Cycle time
Cycle time The second optimization task does not restart from scratch. It benefits from the individuals of the archive that belongs to the restrained area founded during first task. We thus replaced the initialization of our CFB-EA (constitution of the first population) by a selection of a set of the best solutions obtained during the first rough optimization.
This provides the following process: 1. Interactive configuration and planning using nonnegotiable requirements of the user (as before), 2.1 - 1st global optimization task on negotiable requirements of the user 2.2 - 2nd optimization on interesting area initialized with individuals of the previous step.
The goal of the proposed experiments is to compare these two optimization approaches (single-shot and two-task optimization approaches) in terms of result quality and computation time. In terms of quality we want to compare the two 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 second approach. In terms of problem size, we consider a model called “full_ aircraft” that gathers 92 variables (symbolic, integer or float variables) linked by 67 constraints (compatibility tables, equations or inequalities). Among these variables, we find 21 decision variables that will be manipulated by the optimization algorithms (chromosome in EAs): - 12 variables (each with 6 possible discrete values) that describe product customization possibilities, - 9 variables (each with 9 possible discrete values) that describe production process possibilities. In fact, the nine values aggregate 3 resource types and 3 resource quantities for each of the 9 process operations that compose the production process.
Without any constraints, this provides a number of possible combinations around 1018 (≈ 612 x 99). An average constraint level (around 93% of solutions rejected) allows 7.3*1016 feasible solutions. Results of experimentation’s with other model sizes and other constraint levels can be consulted in [Pitiot et al., 2012]. 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 will discuss this aspect in section 3.3.
The optimization algorithms were implemented in C++ programming language and interacted with the 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 Go of ram. For a first experimentation of the two-task approach, we use classical evolutionary settings (e.g. the same evolutionary settings used for the single-shot approach: Population size: 80, Archive size: 100, Individual Mutation Probability: 0.3, Gene Mutation Probability: 0.2, Crossover Probability: 0.8). The main difference with the single-shot approach is with the backtrack limit (e.g. number of allowed backtrack in mutation or crossover operator). This limit has been set to 100 in the one-shot approach and to 30 in the two-step approach.
Indeed in the two-step approach, it could be time consuming to obtain a valid solution. For example with the single-shot optimization, only 2.5% of filtered individuals were unfeasible and none of them were abandoned; while with the twotask approach and a lower backtrack limit, around 7% of filtered individuals were unfeasible and 0.3% of them were abandoned. So a lower backtrack limit reduces the time spend to try to repair unfeasible individuals. The only other difference between single-shot CFB-EA and two-task CFB-EA is the stopping criterion. While in singleshot approach, we use a fix time limit (24hours), the twotask approach uses a bcondition stopping test that stops either 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
The goal of this section is to evaluate the two-task optimization on the three selected areas of figure 8 (zoom 1, zoom 2 and zoom3) with respect to the single-shot optimization.
The Pareto Fronts obtained by the two approaches (singleshot and two-task) are very close when the cycle is greater than 355. For lower cycle times, the proposed two-task approach is a little better. However, these curves correspond with a specific run. In order to derive stronger conclusions, 10 executions of the two approaches have been achieved for each of the three zoom areas.
Detailed experimental results achieved on the three zoom areas are presented in figure 10 and table 1.
On each graph of figure, the vertical axis corresponds to the hyper volume (average of ten runs) reach and horizontal one is the time spent. At time 0, the single-shot optimization is launched (dotted line). After 3 hours (10800 seconds): - the single-shot keeps going on (dotted line), - the two-task is launched (solid line).
The table provides numeric results for each zoom area. The columns display the single-shot, two-task and % gap of: - average final hypervolume, - average % standard deviation of hypervolume - average computation time, - average % standard deviation of computation time, - maximum value of hypervolume. It can be seen on the figure10 that when the single-shot CFB-EA has trouble to obtain a good Pareto Front during the first three hours, the more the two-task CFB-EA is performing. On zoom1 area, single-shot CFB-EA reaches relatively quickly a near-final Pareto Front; while on zoom3 area, it reaches it very slowly.
5823 5.1% 15% 6057
1740 2.3% 16% 1776
CFBEA 1844 0.07% 26% 1845 gap in % 0.4 gap in % 0.2 1.
44 1 4.4 0,7 gap in %
Average 1mHV RSD oo Total
time
RSD Max HV
Average 2mHV RSD oo Total
time
RSD Max HV
Average 3mHV RSD oo Total
The goal of this paper was to evaluate a new optimization principle that can handle concurrent configuration and planning. First the background of concurrent configuration and planning has been recalled with associated constrained modeling elements. Then an initial optimization approach (single-shot CFB-EA) was described followed by the twotask approach object of this paper.
Instead of computing a Pareto Front on the whole solution space, the key idea is: to compute quickly a rough Pareto Front, to ask the user about an interesting area and, to launch Pareto computation only on this area.
According to experimental results, in terms of computation time, the new two-task approach allows a significant time saving around half of the previous time needed by the single-shot optimization approach. In terms of quality, Hypervolume computation are very close or even a little better in some case.
Furthermore, these results have been obtained on a rather large problem that contains around 1016/1017 solutions. With smaller problems, the proposed approach should perform much better. We are already working on a more extensive test (different model size and different level of constraints) as we did in [Pitiot et al., 2012]. Another key aspect that needs to be study is to find a way to define the rough Pareto computation time.