Computer science community is always interested in « benchmarks », e.g. standard problems, by which performance of optimization approaches can be measured and characterized. This article aims at present our research perspectives to achieve a benchmark for concurrent configuration and planning optimization problems. A benchmark is a set of reference models that represents a particular kind of problem. Product configuration and project planning are classic problems abundantly handled in the literature. Their coupling in an integrated model is a more and more handled complex problem; but there is a lack of benchmark in spite of the need expressed by the community during last configuration workshops [config, 2013/2014]]. Two approaches may be combined to obtain a benchmark: (i) generalization of existing real applications (for example, automotive, telecommunication or computer industry), (ii) or using a structural analysis of theoretical model of the problem. In this article, we propose a meta-model of concurrent configuration and planning problem using these two approaches. It shall allow us to supply a representative and complete benchmark, in order to accurately estimate the contribution of existing optimization methods.
Benchmarking of optimization approaches is crucial to
assess performance quantitatively and to understand their
weaknesses and strengths. There are numerous academic
benchmarks associate with various classes of optimization
problem (linear / nonlinear problems, constrained problems,
integer or mixed integer programming, etc.). Studies, reports
and websites of [Shcherbina, 2009] [Domes et al., 2014]
[Mittelmann , 2009] [Gilbert and Jonsson, 2009] are
particularly accomplished examples of existing optimization
benchmark with a multitude of articles and algorithms
benchmarked on great variety of test functions
More than an academic tool, a benchmark should also be representative of real-world problems. For a specific domain, a benchmark represents a reference which should be used by company’s decision-makers to select an approach or an algorithm. But it is not always easy for them to know of which theoretical cases cover their practical cases. Benchmark on configuration field could illustrate this aspect with various industrial cases: automotive [Amilhastre et al., 2002], [Kaiser et al., 2003], [Sinz et al., 2003], power supply [Jensen, 2005], train design [Han and Lee, 2011], etc. A data-base of industrials cases was started on [Subbarayan, 2006] but it is not any more maintained.
Our previous research projects [Pitiot et al., 2013] aim at producing decision aiding tools for a specific problem subject to a growing interest in mass customization community: the coupling between product and project environments. Numerous authors [Baxter, D. et al., 2007] [Zhang et al. 2013] [Hong et al., 2010] or [Li et al., 2006], [Huang and Gu, 2006] showed the interest to take into account simultaneously the product and project dimensions in a decision aiding tool. This concurrent process has two main interests: i) Allowing to model, and thus to take into account, interactions between product and project (for example, a specific product configuration forbids using certain resources for project tasks), ii) Avoid the traditional sequence: configure product then plan its production which is the source of multiple iterations when selected product can’t be obtained in satisfying conditions (mainly in terms of cost and cycle time).
In spite of the growing interest of the community and industrialists, there is no standard (benchmark) for this concurrent problem.
In this article, we propose a meta-model of the whole problem (configuration, planning and coupling) which will be used for a theoretical investigation. We also propose to generate representative instances of the problem. By representative, we mean both:
- Representative of the diversity that could be obtained by theoretical investigation of the meta-model
- Representative of the diversity of industrial existing cases (models and decision aiding process); especially for the configuration part due to its diversity.
Therefore, the paper is organized as follow. The next section details the problem and its combinatorial aspect. The third section proposes first elements relevant to a metamodel of the benchmark tool. Some elements associated with cases diversity are discussed.
For our benchmark, the addressed problem is limited to the coupling between product configuration and project planning. We will describe both environments and the coupling of them in next sub-sections.
2.1
Product configuration problem is a multi-domain, multidisciplinary, multiobjective problem [Viswanathan and Linsey, 2014], [Tumer and Lewis, 2014]. That generates a wide diversity of possible models to represent. We will try to define a classification of existing product models and modelize it in the proposed meta-model. Planning problems are generally more framed (e.g. temporal precedence, resources consumption, cycle time or delay, etc.). To generate various problem instances we can act on the shape of the project graph and on the dispersal of the values assigned for the resources of tasks (cost, cycle time, etc.). Thus, we need to define in our meta-model of the product / project a kind of generic model for each part and for the coupling. The aim of the next step of our study will be to analyze industrial cases and to define this generic model.
Many authors, since [Mittal and Frayman, 1989], [Soininen
et al., 1998], [Aldanondo et al., 2008] or [Hofstedt and
Schneeweiss, 2011] have defined configuration as the task
of 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.
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. More and more studies tackle
the coupling of both environment [Baxter, D. et al., 2007]
[Zhang et al. 2013] [Hong et al., 2010] or [Li et al.,
2006], [Huang and Gu, 2006]. Many configuration and
planning studies
2.2
Combinatorial optimization problem In previous concurrent model, some variables represent decisions of the user (customer or decision-maker on product or project environment). We assume that those decision variables are all discrete variables, so that an instantiation of all these decisions variables corresponds to a particular product / project. Indeed in reality and regardless of the environment, decisions correspond to choices between various combinations. In product environment, decisions correspond to architectural choices between various combinations of sub-systems, or to a choice among various variants for every sub-system. In project environment, decisions correspond to resources choices between various variants. Combinatorial constrained optimization problems consist in a search of a combination of all decision variables that respects constraints of the problem [Mezura-Montes and Coello Coello, 2011]. Instantiation of every decision variable in CSP model corresponds to a specific product/project which could be analyzed and scored according user’s multiple preferences or objectives (cost, delay, etc.). As those objectives could be antagonist, algorithm has to find in a short time a set of approximately efficient solutions that will allow the decision maker to choose a good compromise solution. Using Pareto dominance concept, the optimal set of solutions searched is called the optimal Pareto front. This allows us to define a multiobjective combinatorial constrained optimization problem: a search between various combinations to find a selection of solutions which are the closest possible of the optimal Pareto front. 3
This part aims at present the first elements relevant to a meta-model of a concurrent configuration and planning problem which will be used to generate data on benchmark. 3.1
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 process variables (we assume that duration process variables are deduced from product and resource). In our meta-model, we define two kind of variable: description variables and decision variables. The first ones could be discrete or continuous and allow description of the problem in each environment. On other hand, the decision variables are all discrete, that thus define the combinatorial optimization problem to solve. Those variables, linked by various constraints, describe product and project. In product side, we consider that a generic product can be described by a set of properties or a set of components or a mix of both as proposed in [Aldanondo et al., 2008]. Product description variables can be associated with product properties or component type. The definition domains of these variables are either symbols (for example: type of finish…) or discrete numbers (for example: flight range…). The configuration constraints that link these variables show the allowed combinations of variable values. On figure 1, we represent various groups of variables. It illustrates both the fact that a system is composed of multiple sub-systems, and also that the system and its components are analyzed according to several points of view from various disciplines. Finally, each description variable can have an influence on the product cost and can be therefore associated with a cost variable defined on a real domain. On project side, we consider that a generic production process can be described with a set of planning operations (supplying, manufacturing, assembling…) linked with anteriority constraints. Each operation is defined with: • Three operation temporal variables: possible starting time, possible finish time, possible duration, defined on a real domain,
• Two operation resource variables: required resource, defined on a symbolic domain, quantity of resource, defined on integer domain.
Planning constraints link temporal variables in order to represent temporal precedence. Resources description variables can influence the production process cost and thus are linked to cost variable.
The coupling materializes by some coupling constraints that link at least one variable of the configuration model with at least one variable of the planning model. In terms of objective variable, the global cost can be defined as the sum of all product cost and operation cost variables. The global cycle time corresponds with the earliest possible finishing time of the last operation of the production process. The definition of these coupling constraints completes the model and allows the representation in figure 1 of the global constraint model associating configuration and planning. 3.2
To be able to generate various problems, we analyze the meta-model structure, e.g. relations between variables. It is necessary to describe the types of relations ("pattern") existing between variables in every environment (product / project / coupling). Each of these environments corresponds to a subset of continuous or discrete variables connected by constraints. To generate various models, we can act on the number of variables, on theirs domains or on their relations (constraints). Every variable possesses a domain gathering the set of the values or the possible intervals for this variable. Combinatorial problems stem from cartesian product of every domain of decision variables. A first variation would be obviously the number of variables and the average number of states by variable. For a given complexity, we could also evaluate impact of a few number of variables with large domains or the opposite.
We can also generate diversity by acting on constraints: constraints density, number and kind of constraints. These variations will allow generating models more or less difficult to solve, especially because they define the ratio between feasible and unfeasible solutions and thus the difficulty of the search.
Finally, we can act on distribution of the values affected to each state for each variable involved in evaluation of objectives. For example, it concerns acting on the costs and the performances of components or on the costs and durations of project tasks. This will allow us to act on the density of solutions in the search space. 3.3 3.3.1
Product environment is a multi-domain, multidisciplinary and thus multiobjective context. In meta-model, product configuration model corresponds to a description of relation between architectural or components choices represented by decision variables. Each domain or discipline describes its own point of view of the product and its decomposition using constraints. Their analysis could take into account some context description variables. The result is a fragmented model stemming from the aggregation of these analyses all connected with the decision variables. For the objective aspect, every configuration model takes into account cost dimension. Other objective could also appear like technical performance, environmental impact, etc. For cost aspect, we expect that at least a cost variable is linked (directly or not) to each component choice. Concerning the distribution of values that allows to calculate objective satisfaction, we assume that the model has to be balanced in order: (i) to be an interesting optimization problem to solve and (ii) to be representative of real problems. For the optimization aspect, if an option is systematically better than others, the optimization problem will not be very hard to solve. Furthermore, it corresponds to a better description of the reality where that kind of option will not be conserved in the catalog.
Relations between variables and distribution of values are generally consistent at elemental level, e.g. considering and analyzing only few variables using a specific point of view. Indeed in realty, option choices are generally coherent; in the sense that existence of each option is justified by differences with other options and those differences generally correspond to an application of some basic relations or behaviors. We identify four kind of basic behavior between two variables: - Positively correlated: the increase of the one leads to the increase of other one. For example, performing components will be more expansive. - Negatively correlated: the increase of the one leads to the decrease of other one. For example, components with low environmental impact will be more expansive. - Aggregation: values of a variable are summation of values of some others variable. For example, global product cost is summation of every component costs. - Compatibility/incompatibility of some combinations of values: some values of different variables will be incompatible.
Effects of a positive or a negative correlation aren’t necessarily linear but this study will be limited to linear interactions. Figure 2 shows possible linear correlations between two variables. Of course, extension dealing with three, four or five variables will be considerate as for example flight range, flying speed, seat capacity and cost.
It is the accumulation of a large number of simple and sometimes conflicting elementary behaviors that gives its complexity to the problem. Furthermore, real problems also show some additional singularities on elementary level (for example, a high performing solution for a component) or at system level (for example, the choice of a standard configuration, e.g. a selection of standard components, could lead to an important discount). 3.3.2
On project side, meta-model is more framed on its diversity: - project is a set of task to achieve, - tasks are linked by chronological and precedence constraints, - tasks are described by some temporal description variable (duration, beginning, end) and some variables that represent resource choices.
On this side, decision variable are the resource choices (make, buy or make by subcontract decision). In this same way as in product side, the different options for each resource choice are going to differ with regard to the objectives. For example considering cost and duration objective, a cost and duration could be assigned to each resource choice, then total cost is obtained by a summation and project cycle time by a constraint propagation on temporal constraints.
As in product side, values distribution between various resource choices has to be balanced and consistent in order to represent real problems. We must unsure there is no useless or dominant option and value distributions must represent accumulation of some basic behavior. Here for example, we expect that there is a positive correlation between cost and quantity/quality of resources or a negative correlation between duration and quantity/quality of resources. Except these particular aspects, project environment can contain other description variables and other objectives connected with decision variables. 4
The goal of this paper was to present our research perspectives for a benchmark on concurrent configuration and planning. This problem is more and more studied. Although there are a lot of cases of Knowledge-based configuration systems applied on the industrial practice and project planning, there is a real lack of real-word inspired benchmark. In this study, we propose the first elements of a meta-model that can represent this diversity and that will allow to generate various test models for our benchmark goal.