Thomas Bordonné
email: bordonne@prism.cnrs.fr

Manuel Dias Alves

Mitsuko Aramaki

Sølvi Ystad

Richard Kronland-Martinet

Manuel Dias-Alves

Assessing sound perception through vocal imitations of sounds that evoke movements and materials

Keywords: Perception, Voice, Imitation, Invariant, LPC

come   L'archive ouverte pluridisciplinaire

Introduction

Here we present a suggestion for a new method to investigate auditory perception. As a starting point we base our study on the ecological approach to perception proposed by Gibson [START_REF] Gibson | The ecological approach to visual perception: classic edition[END_REF] in the visual domain, which considers that invariant structures that carry meaning are contained in a perceived stimulus. This approach was later extended by McAdams [START_REF] Mcadams | Thinking in sound: The cognitive psychology of human audition[END_REF], who assumed that these invariants are divided in two categories: structural invariants characterizing the physical properties of a sound object, and transformational invariants, describing the action over the object.

The main goal of our study is to identify such invariants. Several methods already exists, for example in [START_REF] Aramaki | Controlling the perceived material in an impact sound synthesizer[END_REF] or [START_REF] Conan | An intuitive synthesizer of continuous-interaction sounds: Rubbing, scratching, and rolling[END_REF], but our approach is different. While traditional approaches usually use intermediates to study perception, our approach allow us to directly question one's perception. We propose to determine invariants using vocal imitations. We suppose that the vocal imitation will sort of summarise one's perception of a sound. In fact, it has been shown that vocal imitation is more efficient to describe a sound than words [START_REF] Lemaitre | On the effectiveness of vocal imitations and verbal descriptions of sounds[END_REF]. In order to validate the fact that invariants can be retrievd from vocal imitations, we developed a preliminary experiment, which is presented in this paper. We posed two main questions: Which characteristics of a sound do we use when we imitate sounds? How are they transmitted by the voice?

In this study we used sounds based on invariant structures identified previously. Hence one transformational invariant responsible for the evocation of elliptic movements [START_REF] Thoret | From sound to shape: auditory perception of drawing movements[END_REF] was combined with 3 structural invariants responsible for the evocation of 3 different material categories, i.e wood, metal and glass [START_REF] Aramaki | Controlling the perceived material in an impact sound synthesizer[END_REF]. We asked participants to vocally imitate sounds that evoked the elliptic movement on one of these three materials. To analyze the vocal imitations, we decided to use a non-conventional method by linear predictive coding (LPC), proposed in [START_REF] Marelli | On pole-zero model estimation methods minimizing a logarithmic criterion for speech analysis[END_REF]. This method is based on the pole-zero estimation of the log of the spectral envelope. The fact is that a conventional method (i.e a pole estimation of the spectral envelope) only fit with the spoken or sung voice. While imitating, one will use unconventional configurations of their vocal tract, which lead, for instance with nasal vowels, to the apparition of spectral anti-resonances. Trying to modelize the vocal tract with a conventional method is consequently irrelevant, and it was necessary to use the chosen method to increase our chances to find something interestisng.

Method

Through a movement sonified thanks to a perceptually-validated synthesizer, we studied the perception of these invariants.

Creation of the referent sounds

In this experiment, the referent sounds are composed of synthetic rubbing sounds generated from a velocity profile, derived from an elliptic movement made by an experimenter.

In practice, an experimenter drew an ellipse on a WACOM INTUOS PRO graphic tablet. He was asked to reproduce the same shape 10 times. We asked the experimenter to draw the ellipse "in the most natural way", using the most available space. No instructions were given concerning the eccentricity nor orientation either. We used a 60 bpm metronome while the experimenter was drawing to help him being periodic. The position of the stylus was recorded by a Max/MSP interface at a sampling rate of 129 Hz. We then derived the position to get the velocity profile and kept the one that best corresponded to the initial 60 bpm rhythm. For technical reasons, we then duplicated the chosen velocity profile three times. The total duration of the drawing was 604,5 milliseconds. It has been shown in [START_REF] Thoret | From sound to shape: auditory perception of drawing movements[END_REF] that an ellipse can be recognized when a blindfolded subject listens to the sound of the pencil or to the sonified trajectory. We therefore chose this shape for the vocal imitations to check the perceptual importance of the dynamics of this movement.

Then, we used the sound synthethizer described in [START_REF] Aramaki | Controlling the perceived material in an impact sound synthesizer[END_REF] and [START_REF] Conan | An intuitive synthesizer of continuous-interaction sounds: Rubbing, scratching, and rolling[END_REF] to generate the sounds textures that evoked different material categories. The elliptic movement was then combined with the three materials: wood, metal and liquid, to evaluate the subjects' capacity to imitate the perceived timbre. The advantage of using this synthesizer is that the acoustic descriptors of the materials have already been perceptually validated in previous studies meaning for example, that no preliminary study needed to be conducted to check whether subjects recognized the material.

We finally obtained the following three referent sounds: rubbing on wood, rubbing on metal, and rubbing on a liquid.

Experimental setup

All participants provided written consent to participate in this study.

Stimuli We used the 3 referent sounds. Each sound was presented only once in a random order. The order of presentation was different for each subject. The volume of the sounds was equalized.

Participants A total of 31 French speaking persons volunteered as participants in the experiment (21 male, 10 female), between 20 and 62 years old (median 26 years old). Each participant performed an audiogram before participating in the experience. We reported no hearing impairments.

Apparatus The sounds were played with an Apple Macintosh MacBookPro 9.1 (Mac OS X 10.9.5) with a MOTU UltraLite mk3 over a single Yamaha HS5 studio speaker facing them. The vocal imitations were recorded by a SMK4060 DPA microphone at a 44100 Hz sampling rate. The participants were also facing an interface displayed on a screen. They could interact with the interface and control the microphone with a mouse and a keyboard left at their disposal. This interface was developed with Max/MSP software. Participants were seated in a in a quiet room, acoustically isolated from the outside.

Procedure The participants with a normal audiogram were introduced to the experience. They were first introduced to a preliminary experiment aiming at familiarizing the subject with thee experimental setup. It also enabled to create a small database for later use. The preliminary experience was performed in three steps: A recording aiming at ensuring the effective comprehension of the instructions. Then, the subjects pronounced five French vowels [ a ø i o y](in phonetical alphabet), that were recorded. Finally, an additional recording of two French sentences containing all the French phonemes was effectuated.

Sentence 1: "Au loin, un gosse trouve, dans la belle nuit complice, une merveilleuse et fraîche jeune campagne." Sentence 2: "Il faut déjà que vous sachiez que les bords de telles rues ne sont qu'un peu glissants le matin Zermatt."

The participants then began the experience. The instruction was: "You will hear sounds produced by movements on different materials. You will have to record one or two vocal imitations that describe at best the sound you heard." The participants first accessed an interface where they were allowed to record two imitations. The participants were informed that they had to record at least one imitation and listen to it before continuing. The participants secondly accessed another interface were they were allowed to evaluate their vocal imitations. The evaluation was done on a scale from 1 to 5, from "Not satisfied at all" to "Very satisfied". Finally, they had to answer the following questions: "What did you try to imitate? Which elements of the sounds did you based your imitation on?". The participants could write their answers in a designed location.

Analysis For each referent sound, we gathered one or two vocal imitations per subjects. For clarity reasons, when the subject has made two vocal imitations, we kept the one with the best evaluation. Depending on the participant, we obtained whether conventional voices, easy to modelise with a linear predictive model, or more complicated, like nasal vowels (the [Õ] in "Bonjour" in french for example). We then analyzed the imitations with the LPC ARMA method proposed in [START_REF] Marelli | On pole-zero model estimation methods minimizing a logarithmic criterion for speech analysis[END_REF], which gave us an estimation of the positions of the formants and anti-formants. We also smoothed these values over the duration of the signal performing a Savitzky-Golay filtering [START_REF] Savitzky | Smoothing and differentiation of data by simplified least squares procedures[END_REF] with a window of 31 samples and a third order interpolation. We performed this smoothing in order to guarantee the continuity between consecutives frames, and suppressed the possible noise induced by the LPC ARMA algorithm.

We chose to look at the results in the space formed by the first formant frequency (F1), and the second formant frequency (F2) (See Figure 1). We extracted the smoothed values of F1 and F2 from the previously cited method, and plotted them in an F1F2 space. We then studied the shape of the trajectory of the formants by fitting an ellipse to 90% of the trajectory. We then extracted the phase, the surface and the orientation of the fitted ellipse. The phase is related to the eccentricity by the following relation:

φ = 2 * arctan 1 -e 2 (1)
With e the eccentricity of an ellipse. We chose to look at the phase instead of the eccentricity because the range of variations is larger. It allows us to study smaller variations of the eccentricity. It is important not to confuse the fitted ellipse and the drawn ellipse, used in the stimuli. They are two completely different variables, and their characteristics are independant.

A representation of the different extracted parameters is given Figure 2 We also measured the fundamental frequency using the YIN method [START_REF] De Cheveigné | Yin, a fundamental frequency estimator for speech and music[END_REF]. When a fundamental frequency could be detected, that is to say, where the subject did not only make noise, but chose to voice the imitation, we calculated Fig. 1. Formant space between the first formant frequency and the second formant frequency. Here the different vowels corresponding to a couple of F1,F2 are represented. Source: [START_REF] Peterson | Control methods used in a study of the vowels[END_REF] the ratio between voiced and unvoiced parts over the total length of each vocal imitations in order to measure a voicing ratio. In this case, we also retrieved the range between the minimum and maximum values of the fundamental frequency. The threshold used to distinguish voiced and unvoiced part is based on an aperiodicity coefficient, calculated by the YIN method. The threshold was set so that from an aperiodicity of 0.5 to 1 (the maximum), the segment of voice is considered as unvoiced, and vice-versa.

We performed an analysis of variance (ANOVA) using STATISTICA, on all of these variables, except on the range of the fundamental frequency, due to a lack of data. A Tukey's HSD test was used in order to specify significant effects. Results are presented and discussed in the next section.

Results

One of the main goals of this study was to determine the characteristics of the sounds chosen by the subjects during imitation, and to figure out in which case voicing was used. We identified four possible indices. Studying the trajectory of the first two formants, we fitted an ellipse, allowing us to identify 3 indices: the phase, derived from the eccentricity, the surface and the orientation of this ellipse. The fourth indice, the voicing ratio, is based on the fundamental frequency. Means and standard deviations of these four indices are presented in Table 1. Fig. 2. Formant trajectory drawn in the F1,F2 space. The trajectory is represented by the dotted grey line. The fitted ellipse is represented in black. The angle is calculated between the major half axe, represented here by the small arrow in black, and the horizontal level. We can see here that the center of the ellipse (F1 = 1289, F2 = 1901) is situated at the limit of the known vowels

Phase The flatter the trajectory, i.e. the closer the phase is to 0, the more selective between the formants the participant is. In other words, if the phase is small, the participant varies over one formant or the other, but not both. The ANOVA performed over the phase between materials did not showed any significant differences (F(2,60) = 0.991 , p = 0.377). This means that independently of the materials, there is a preferred use of F1 or F2

Area The area of the trajectory in the formant space represents the range of frequency the participants used to reproduce the sounds. The bigger the area is, the bigger the range is. The ANOVA performed did not showed either any significant differences (F(2,60) = 1.611, p = 0.208) between materials. This means that the participants used the same frequency range within the F1F2 space to reproduce the sounds, with no difference between materials. 1. Means and standard deviation (in parenthesis) for the descriptors, for the three materials. Units are specidied next to the descriptors.

means that only F1 is used. On the contrary, if the orientation is close to 0, it means that only F2 is used. Here again, the ANOVA did not show any significant differences (F(2,60) = 0.574, p = 0.566) between materials meaning that there is a preferred orientation during imitation. Looking at the values of the orientation, there is a covariation between F1 and F2.

Voicing Ratio The voicing ratio indicates us the quantity of voice there in an imitation. The ANOVA showed a significant difference (F(2,60) = 13.596, p = 0.00001) between materials. A Tukey's HSD test showed us that the metal was significantly different from the wood (p = 0.0004) and from the liquid (p = 0.0001). In addition it revealed that approximately half of the participants voiced their imitation for the metal (16 out of 31), which was more than for wood (7 out of 31) and liquid (5 out of 31).

Furthermore, in the case where the imitation was voiced, we compared the range of the fundamental frequency for the different materials. Results are shown in Table 2 Wood Metal Liquid F0 range (in Hz) 124.1 (79.80) 92,50 (65,52) 118,5 (80,75) Table 2. Means and standard deviation (in parenthesis) for the range of fundamental frequency, for the three materials.

Unfortunately, no statistics can be done over the range of fundamental frequency because of the lack of data. We can only make the assumption that there is a difference between metal, and the other two categories (wood and liquid).

Discussion and further work

Here we discuss several points raised by the previous results. The initial questions were related to the characteristics of the sound used by the participants during their imitation, and, consequently, how did they expressed it. Given the previous results, dynamics and the material are the two characteristics the participants chose. They transmitted it through replicating the dynamic and voicing or not their imitation.

Participants imitate the dynamics similarly

One initial hypothesis was that the participants could retrieve the dynamics of the movement independently from the three materials. Results show that participants in majority percieved the same dynamics of the sound. The three chosen descriptors of the trajectory in the formant space are not significantly different across materials. Results also show that the participants used the same strategy to reproduce the dynamics of the sound. Even if it is unsure whether participants specifically perceived the shape of the ellipse used to generate the sounds, the rhythm induced by the dynamics of the elliptical shape was recognized and imitated.

The written reports made by the participants themselves tend to confirm this tendency. Indeed, when they were asked what they tried to imitate and what they used to imitate the sound, nearly all the participants evoked the rythm, or at least, a cyclic aspect. We can therefore assume that the morphological invariant linked to the dynamics is perceived and expressed.

One way to check this assumption would be to ask participants to imitate sounds with different dynamics. It has been shown in [START_REF] Thoret | From sound to shape: auditory perception of drawing movements[END_REF] that a biological movement following the 1/3 power law1 can be recognized through timbre variations by the velocity profiles and that drawn shapes also can be distinguished through the different velocity profiles produced during the drawing process. It would be interesting to study the influence of changing the dynamics of the sound. First, simply by changing the shape from which the velocity profile is taken. And second, by making the velocity profile following another law. This would maybe allow us to retreive, or not, the already known dynamical invariant in relation with the shape, by looking at the dynamic evolution of the imitation.

The fundamental frequency as an information related to the material

Our hypothesis was that the participants would make a difference between materials during their imitations by changing the timbre. What can be seen is that only the metal induced a change in timbre. The "metallic" aspect, which can sound like more "resonant" or more "harmonic", convinced the participants to voice their imitation more than for the other materials. One could think that the participants participants who voiced their imitation did not used an (F1,F2) variation, or at least used a different strategy than the participants who did not voice their imitations. In fact, voicing seems to provide a complementary information over the material, as the participants who voiced their imitations used the same strategy over (F1,F2) than the participants who did not voice their imitations.

The frequency range of the fundamental frequency also gives us some interesting clues, even though it cannot be considered statistically relevant. The range for the metal seems to be lower and more precise than for the other materials (see table 2). We could make the assumption that when a fundamental frequency is perceived, it is easier and more relevant for the participants to include it as a relevant information in their imitation. Thus, in order to make a difference between sounds with no fundamental frequency, another descriptor has to be found.

To differentiate materials we hypothesized that the formants' bandwidths carried material-related information. By measuring the proximity between formants and anti-formants, it could be found that for different materials, a measurable law allowing us to distinguish the material could be found.

The hypothesis that different materials induce different imitations is comforted by the reports of the participants. The participants reported a perceptual difference of perception between the three materials. More investigations should be done to identify new descriptors that will enable us to distingish the for the moment non-distinguishable imitations.

For instance, the mean distance between pole and zeros in the spectrum could give another indication about the material. It could allow us to statistically differentiate the wood and the liquid, the wood being, a priori, "more resonant" than the liquid in our model.

Further work

In addition to the previous propositions, the excitation is an object of importance. For the moment, all the descriptors we studied, except the fundamental frequency to a certain extent, were extracted from the spectrum. The excitation has to be be taken into account when analyzing and describing complex sounds. For example, in the case of liquid sounds, the information included in the spectrum or the fundamental frequency is not sufficient. Imitations can be half-voiced half-unvoiced, for example the French pronunciations of "r" or "j", like in "rouler" or "jouer". Using inverse filtering in LPC to retrieve information about the excitation can easily be made, but modeling complex sounds like the previously cited ones is more complicated. The next field of investigation will surely focus on this aspect.

More broadly, assessing the sound perception through vocal imitations opens a wider perspectives for sound synthesis. In [START_REF] Aramaki | Prospective view on sound synthesis bci control in light of two paradigms of cognitive neuroscience[END_REF], the authors proposed an approach based on a Brain-Computer Interface (BCI) to highlight and extract the aforementioned invariants. The idea was to use what is perceptually relevant in the sound as a lever to control sound synthesis. Our final aim is the same, but the approach differs, being a lot less invasive. In fact, instead of looking at variations in encephalograms to reveal invariants, we directly spotlight what is relevant for subjects. If by imitating sounds, we succeed at extracting the invariant, it may be a more robust method. Or at least a complementary one. We could finally imagine developping a sound synthesis tool that uses vocal imitations as a control, in regard of the sound synthesis tool controled by a BCI interface.

In this experiment, we aimed at determining the main characteristics of sounds used by participants during vocal imitations. We also wanted to determine how the participants translated these characteristics using their own vocal apparel. For that, we extracted several descriptors from the F1,F2 space: The phase, the area and the orientation of an ellipse fitting the trajectory of the formants. We also extracted the fundamental frequency to characterize its usage. The dynamics of the sound turned out to be well recognized and well imitated by all the participants. In addition, the fundamental frequency is used by participants as a tool to complete the missing information given by the formants concerning the material. Further work is planned to deepen these two assumptions. Vocal imitation seem to be a good tool to access the perception and determine which aspects of the sounds are relevant. The next goal is to validate its use in the search of invariants.

First

For documentation about 1/3 power law, see[START_REF] Viviani | Minimum-jerk, two-thirds power law, and isochrony: converging approaches to movement planning[END_REF]

Acknowledgments. This work was financed by the National Research Agency (ANR), within the Sonimove project (Project reference: ANR-14-CE24-0018).


L Duta
email: duta@valahia.ro

J M Henrioud
email: henrioud@ens2m.fr

I Caciula

A REAL TIME SOLUTION TO CONTROL DISASSEMBLY PROCESSES  

Keywords: production control, real time systems, decision making, stochastic programming 

Disassembly of manufactured products induces both disassembly costs and revenues from the parts saved by the process. At the planning stage a good trade-off has to be found between the costs of disassembly and the final profit. At the control stage it is important to assure an optimal balance of the line as well as the complete disassembly processing during the rest of the working time. A real time control method based on modeling of disassembly by the precedence graph and on a stochastic algorithm is presented in this article.

INTRODUCTION



The disassembly process is the main stage in the recycling of manufactured products at the end of their life. The aim of this process is to extract the reusable parts of the product, materials to recycle, as well as the dangerous materials. Products submitted to the disassembly process are out of use so we have to take into account their physical state.

Disassembly is a non-destructive technique: it implies the extraction of the desired components and/or materials. If parts are not reusable after reconditioning, partial or total destructive operations are applied: drilling, cutting, wrenching, and shearing. These techniques are used in view of material or energy recovery.

The aim of the valorization process is to save the value of parts and materials by repairing and recovering operations.

Thus a trade off has to be made between the cost of disassembly operations and the revenue brought by the parts or the material retrieved. This problem is made more complex by the occurrence, during the disassembly process, of uncertainty in the possibility of components separations (Penev and De Ron, 1996).

Deteriorations and deformations of some elements, absence of one or more components, presence of corrosion and rust are perturbations often encountered in the disassembly process. Therefore, some operations cannot be carried out due to the physical degradations of the components and other operations are not performed if they are not profitable. So, a choice has to be made, between applying an alternative disassembly destructive operation (dismantling), and abandoning the disassembly procedure (Salomonski and Zussman, 1999). Thus, control of disassembly process involves two essential decision variables: disassembly level and disassembly mode: clean or destructive. A third decision variable may be added: the task assignment to the station. This decision variable (the only one available in assembly) is far more constrained than the two former ones. This makes from the control of disassembly systems a far more complex problem than the control of assembly systems.

As mentioned above, an essential criterion for a disassembly system is the benefit it brings, that is the revenue brought by the retrieved parts and material, decreased by the cost of their retrieval. Another important criterion, especially for manual systems is the line balancing. One way to deal with this multicriteria problem is to use a multi-criteria method, the problem is that this will require a weighting of the two criteria (revenue and line balance) and there is no satisfying way to choose the weights. In order to avoid this problem, the authors have proposed a two stages method.

At the first stage, which is the Disassembly Line Design, disassembly level is obtained by the optimization of the revenue produced by the line. This is resolved by modeling the set of valid disassembly sequences using a Petri Net and Linear Programming (Addouche et al, 2002). At this stage, disassembly costs are supposed to be simply proportional to the disassembly time.

At the second stage, of the Disassembly System Control, decisions are made in order to optimize the line balance and guarantee that the production plan will be realized at the end of the plan horizon (usually the week). Assumption of disassembly costs proportional to disassembly time is no longer relevant. While working, as soon as the line gets unbalanced, time becomes highly valuable at overloaded workstations and without any value at idle ones.

Few authors have addressed the control problem of disassembly lines (few had addressed before the control problem of assembly lines). One first attempt was made by (Kizilkaya and Gupta, 1998) who used the method "just-in-time" and a flexible Kanban system to control the flow of the disassembly process. But his approach is not suited to the automatic disassembly lines. Chevron in his doctoral research (Chevron, 1999) proposed the Colored Petri Nets for modeling the disassembly process and a dedicated computer to perform the on-line control. The lack of his method is that he didn't take into account the application of the destructive operations in the case of the disassembly failure. (Wiendahl et al, 1999) proposed a special architecture of the disassembly system control. This one includes a decision module which gives the possible tasks assignments on the line. They proposed the linear programming to program this module but they never gave an example. Recently (Kopacek and Kopacek, 2005) describes a control system for mobile phones disassembly cells. Unfortunately, this system can not be functional in the case of destructive operations. In fact, even the author specified that the system is suited for small series of products that haven't suffered great structure modifications in their functional life.

Preliminary considerations

The problem considered in this paper is the real time control of a Disassembly Line whose design has been optimized so that the Line produces, on an average production, the best trade-off between disassembly cost and revenue brought by the retrieved parts and material. The result is:

-the disassembly level, -the choice of disassembly operations : destructive or not destructive, -the design of the line and the assignment of operations to workstations.

At the On Line Control Level, it is very important to assure the Line Balance, more specially, but not only, if the Line is mostly manual. This is far more critical in disassembly than in assembly because disassembly times present an important dispersion.

What follows will be based on the following assumptions.

-the Disassembly Line is multi-product and all the operations to perform and their precedence relations may be represented by a single precedence graph, where nodes represent generic operations. Operative times take the zero value for operations missing on some products (when optional components are involved). -The sequencing of the product on the line has been fixed and cannot been changed. -The objective of the control is to make sure that the products that are to be disassembled in the current period will be as completely treated as possible during the remaining time and that the line keeps a good balance in the dynamic sense.

The objective function

Notations:

n -the number of workstations m i -the total number of operations on the workstation W i t cy -the cycle time t j -the operational time for the task j Considering the balancing function presented in (Duta et al, 2005) which gives the difference between the operational times and the cycle time the next formula gives one objective function to minimise:

In a static approach of the disassembly process the cycle time is defined as the ratio between the duration of the planning period H and the number S of products to be disassembled (Duta, 2006;Lambert and Gupta, 2006):

It is supposed that the products to disassemble are similar (with the same structure), so the operational times are equal from one product to another. Thus, the objective function has the same form and the operational times are multiplied by S.

Equation (1) becomes

A problem occurs in the case of the real time disassembly: the operation can be fulfilled or not or there are destructive operations to accomplish. The aim is find the form of the objective function in real time.

Notations:

-n is the number of workstations, -Tr is the time remaining for the disassembly process -Tr i is the time left for workstation W i to complete its remaining workload In a dynamic approach, the objective defined above may be expressed by formula (4) which is the objective function to be minimized:

  2 1 n i i F T r T r    (4)
Tr i can be expressed as a sum of the operational times performed by workstation W i .

Real time coefficients

To compute Tr i , we have introduced three binary variables: ij  the assignment coefficient that defines assignment of tasks to stations for different products.

Pm i ij ij ij ij ij ij i j Tr t t              ( 5
)
Where m is the total number of operations, P is the number of products to be disassembled ij t is the average duration attributed to the operation O j on a product P i when it is performed in a non destructive way.

' ij t is the average duration attributed to operation O j on a product P i when it is performed in a destructive way.

Remarks:

1. An operation O j is still to be performed on some products yet to be disassembled, if   i so as 1 ij   . Thus, ij  has two functions: first it defines the operations still to be performed, hence the disassembly level, and second it defines the assignment of tasks to workstations.

i i m n cy j i j W f t t t             (1) cy H t S  (2) 2 2 1 1 () i i m m n n cy j j i j i j f t S t t H S t                         (3) 2. Table [ ij 
] is subject to two kinds of constraints:

-Assignment constraints that define for each operation the workstations that are able to perform it. Mostly workstations are dedicated to specific tasks, due to the tooling, and there are few possibilities of reassignment.

-Precedence constraints that are represented by a precedence graph A possible combination of the three binary coefficients is given in the Table 1.

Table 1. Binary coefficients variants

No ij  ij  ij 
Meaning 1 1 0 0 Operation j made in a destructive way on the workstation i 2 1 0 1

Operation j made in a nondestructive way on the workstation i 3 1 1 0 Operation j has to be made in a destructive way on the workstation i 4 1 1 1

Operation j has to be made in a non-destructive way on the workstation i

Defining the solution space search

A solution for the optimisation problem stated above is given by tables

[ ij  ], [ ij  ] and [ ij 
] and it defines a valid partition of the precedence graph where no operation in a workstation with rank i can precede an other operation on a workstation with rank less than i. For any suppressed operation O j all operations, O h such that O i precedes O h , are also suppressed. The optimal tasks assignment as optimal solution must be searched in the neighbourhood of the current solution.

Definition 1: Two solutions are neighbours if one of them can be transformed into the other one, by one of the four transformations T1 -T4, given below.

Definition 2: The upper (or lower) border of a workstation W i is the set of all tasks that have no predecessor (or successor) in W i . To obtain a neighbourhood four transformations can be possible: T1. One task belonging to the upper border of a workstation is moved to the lower border of the next workstation T.2. Suppression of a task. This transformation applies only to tasks that have no other successor than the last task of the precedence graph (the unloading of what is left of the product to disassemble).

T3. The introduction of a task that has been suppressed before. This transformation applies only to tasks that have no predecessor in the precedence graph (the loading of the product to disassemble on the disassembly line).

T4. Transformation of a task that may be performed either in the destructive mode or in the non destructive one: if it was planned in the destructive mode, it becomes non destructive and reverse.

THE ALGORITHM

The algorithm used for the optimisation problem formulated in the previous section is a Kangaroo algorithm that belongs to the stochastic algorithms class. Kangaroo algorithm has already been used in the closed problem of Assembly Line by V. Minzu (Minzu and Henrioud, 1998). The first step in the building of a stochastic algorithm was to define the solution space and a neighbourhood in this space. This algorithm searches the optimal solution in the neighbourhood of the current solution. The steps of the Kangaroo algorithm are described as it follows:

Step1 Let fix a value N Aa M     where   1, 2 a  ,
c  c+1; if ( ) ( ) f v f u  then begin if ( ) ( ) f v f u 
then begin c  0; // a better value of the function has been obtained; if f(v)<f(u*) then u*  v; //a lowest value of the objective function has been obtained; end; u  v;//the old partition is replaced with the new one end;End. procedure jump (u,u*,c) Begin Generate v in the neighbourhood of u c  c+1; if ( )

( ) f v f u  then begin if f(v)<f(u*) then u*  v; c  0; end;u  v; End.

APPLICATION

The method was simulated on a case study: disassembly of a cell phone which precedence graph is taken from (Lambert and Gupta, 2006).

There are 25 disassembly operations and 30 disassembly sequences. The operational times t j are given in (Gupta and McGovern, 2004). We considered 6 workstations that can accomplish destructive or non-destructive disassembly operations.

Assumptions:

-the supply of product is continuous -a single type of product is disassembled -a task can not be divided between two stations -disassembly tasks are assigned so as not to violate the precedence relationships among them -complete disassembly is performed -destructive operations are taken into account Input data: H: 8 h, S: 1000, t cy : 30 s, operational times t j

The initial assignment is given in Table 3 Table 3. Initial tasks assignment

Workstation

Assigned tasks 1 1,2,3,4, 5 2 6,7 3 8,9 4 10,11, 12, 13, 14, 15, 16, 17, 18, 20 5 19, 23 6 21, 22, 24, 25 The Kangaroo algorithm defines a neighbourhood of the solution in case of a perturbation occurrence and permits the minimisation of the balancing function given by the equation ( 4). Perturbations can be provided by the impossibility to perform a disassembly operation or by the change of its typedestructive or not. Moving an operation to one station to another, a new neighbourhood is obtained and the search of a new solution is performed in real time.

The new assignment solution is provided in real time taking into account the precedence relationships between disassembly operations. The program was implemented in the C++ language. On a 64 AMD Athlon processor the computational time is 10.12 ms.

CONCLUSIONS

A method to control the disassembly processes is presented in this paper. Disassembly processes are submitted to perturbations and uncertainties derived from the used state of the product. Once a perturbation occurs, a fast computation has to be made so as to determine the optimal disassembly sequence and the optimal assignment of the tasks to workstations.

A stochastic algorithm is proposed in order to manage the optimisation problem in real time control. The optimised function is dependent of three discrete variables.

The algorithm does not optimize the balance of the disassembly line, but gives a solution that improves this balance at each computation moment.

Applying a stochastic algorithm in discrete optimisation the quantity of data decreases and the calculus speed rises. In the disassembly process a local and quickly solution for the optimal disassembly sequence is preferred to the complex and slower algorithms. Future work will be concentred on the deduction of the general form of the function (4) that is the balancing function for a product family. In this case the operational times are dependent of the product type. Feasible methods have to be found to control the flow on a family product disassembly line.

  call descent(u,u*,c) else call jump(u,u*,c); until (an end criteria is fulfilled); STOP The two procedures descent and jump are described as it follows: procedure descent (u,u*,c) Begin Generate a solution v in the neighbourhood of u

Fig. 1 .

 1 Fig. 1. Precedence graph of the cell phone

Table 2 .

 2 Cell phone operational times

	Op 1	2	3	4	5	6	7	8
	t j	3	2	3	10 10 15 15 15
	Op 9	10 11 12 13 14 15 16
	t j	15 2	2	2	2	2	2	2
	Op 17 18 19 20 21 22 23 24
	t j	2	3	18 5	1	5	15 2
	Op 25
	t j	2

Addouche S., Perrard C. and Henrioud J.M. (2002) n°7-8, 1998, pp. 831-851. Penev K. D. andA. J. de Ron (1996) Integrated Manufacturing, vol. 15, pp. 211-220 Wiendhal H.P., Seliger G., Perlewitz H., Brukner S., (1999), A general approach to disassembly planning and control, Production Planning and Control,vol. 10. ,No. 8,


François Marmier
email: fmarmier@ens2m.fr

Christophe Varnier
email: cvarnier@ens2m.fr

Noureddine Zerhouni
email: nzerhouni@ens2m.fr

ROBUSTNESS MEASURE FOR FUZZY MAINTENANCE ACTIVITIES SCHEDULE

Keywords: Human Resources, Maintenance, Scheduling, Skill, Uncertainties

Skills management in industry is one of the most important factors in order to obtain good performance with production means. Especially in the field of maintenance services where the different practical knowledge or skills are their working tools. We address, in this paper, both the assignment and scheduling problems that can be found in a maintenance service. Each task that has to be performed is characterized by the level of skill required. The problem lies with making the decision of which time is the right time for the assignment and scheduling of the correct resource to do the task. For human resources, all skill levels are different, they are considered as unrelated parallel machines. Our aim is to assign new tasks to the adequate resources by giving to the maintenance expert a good and robust possibility.

INTRODUCTION

To stay competitive, companies must decrease their costs as much as possible and optimize their production means operations. In order to confer a better availability of equipment, and through them a better availability of the company, the maintenance service intervenes. It deals with problems before and after breakdowns. This improvement mainly requires a better management of the workforce and its skills. The reactivity and the organization of the maintenance service will depend on the importance of the required treatment.

It is difficult to determine precisely the required human resource number in a maintenance service [START_REF] Mjema | An analysis of personnel capacity requirement in the maintenance departement by using a simulation method[END_REF]. Indeed, factors making enabling capacity adaptation are prone to uncertainties. Those are due to several parameters (variations of the intervention requests which are never similar, arrival dates of requests, requests' contents, required treatment dura-tion and equipments availabilities as well as elements related to the real intervention treatments). Thus, the different tasks are well known when they occur. The reactivity and the organization of the maintenance service will depend on the importance of the required treatment.

There are mainly two types of maintenance activities: the preventive maintenance, whose activities can be long term planned, and the corrective maintenance which is related to the non foreseeable breakdowns. Within the service of maintenance, employees have different competencies and different qualification levels. Treatment speed and thus the service reactivity will depend on the choice of the employees assigned to the task.

We give in this paper a method to take care of the new tasks apparition and we propose a decision support to insert it in the current schedule. We work on the case where the task assignment has already been realized (for example with the heuristic presented in [START_REF] Marmier | Maintenance activities scheduling under competencies constraints[END_REF]). The goal is to disturb as less as possible the current schedule. However, the whole schedules are subject to uncertainties and variation between theory and reality. In order to propose insertion solutions for a new task, we have to determine which places in the schedule are the more flexible in order to obtain a scheduling which would be the most robust (the less sensible to uncertainties). The fact to propose schedule solutions taking care of variation by anticipating show that our scheduling method is proactive.

In this article, we detail a methodology which will allow us to assign tasks to resources by considering disturbances. The rest of the paper is organized as followed: In the second section, we will introduce how maintenance services can be managed. In the third part, we will present the scheduling problems with uncertainties. Then we develop our model and a resolution approach. Finally, we will discuss the different obtained results.

MAINTENANCE MANAGEMENT

In scheduling and planning, the time horizon is often split in periods (the short, medium and long term). Then, we can study events on each time interval and not on a continuous scale of time. The context of this article takes place in the short term horizon. In this approach, we consider that maintenance tasks have to be scheduled when they occur (generally it is the case of corrective maintenance). The manpower is then the limiting factor in the scheduling realization. Human resources are then organized in the maintenance service which has to plan their work.

Organization

Within each plant, the maintenance service has to maintain equipment under operation. The level of the results to reach by the maintenance services is generally predetermined. Either a contract is signed between two (or more) partners fixed their cooperation terms, or there is a moral agreement inside the company between production and maintenance service, that fixes the equipment efficiency required. In both case, the objectives of the maintenance are defined by a level of availability (that can be different from one equipment to another). The guaranteed availability is a percentage of the opening time. If, for a machine or a group of machines, the objective of availability is not achieved, penalties have to be paid by the service provider. Conditions concerning the penalties are defined while elaborating the contract and are function of the non availability duration. We will consider in our model the minimisation of those penalties.

Resources

During her thesis, Agnès Letouzey carried out a study on nineteen companies to obtain their opinions on the operators' assignment problem [START_REF] Letouzey | Ordonnancement interactif basé sur des indicateurs : Application à la gestion de commandes incertaines et à l'affectation des opérateurs[END_REF]. It shows that operators' management, according to their competencies, is important for industry leaders and that there is still no software taking this into account. 79% of the companies think that operators' management is useful or essential in scheduling. Whereas in current softwares the operational duration is fixed, for the industry leaders, the consideration of the operators' qualification is very important to determine their assignments. For them, the qualification level has (sometimes for 47% of them and always for 27% of them) an influence over the task's duration of realization.

A maintenance service is an environment composed of m operators working in parallel. We assume that all can perform each task, but not with the same efficiency. Moreover, the resource which is the most effective for a task, would not necessary be effective for all tasks.The multiplicity of competencies shows that we have a parallel machine problem, but with unrelated machines which is noted R or R m | β| γ.

Tasks

On a medium-term, the maintenance service has to plan and assign the best human resource for the treatment of the different maintenance tasks. Preventive and conditional maintenances have for parameters a known duration, a starting date and a completion date. The corrective maintenance tasks generally occurs in the short-term horizon. They also have a duration, which is only evaluated since it depends on a correct diagnosis. Their earliest starting date is not necessarily immediate, since spare parts are not necessarily available (they can be expected from a supplier) or the availability level of the equipment is quite good and then the intervention can be done latter.

SCHEDULING PROBLEMS WITH UNCERTAINTIES

Problem syntheses

In this problem while tasks have not been really treated, their data are stochastic. In order to propose a robust (and proactive) solution, our simulation will consider variations on release-dates, due-dates and of course on the duration of each tasks within the scheduling.

Scheduling under uncertainty

In classical scheduling problems, the data are generally supposed to be known and fixed. However, the re-ality does not check this hypothesis, of course because of variations, but also because a lot of data are only previsions or estimations. Optimal solutions to such scheduling problems which are based on fixed data and do not show the reality, will have only few chances to be applicable and will be subject to modifications.

In the existing model taking into account uncertainty, we find mainly the Davenport and Beck one which present three approaches: proactive, reactive and proactive-reactive approaches [START_REF] Davenport | A survey of techniques for scheduling with uncertainty[END_REF]. Proactivity is the fact to anticipate disturbances before that they really occur. Reactive approaches work in real time, during the scheduling phases. Proactive-reactive methodologies, will try to combined both approaches in order to take into account uncertainties during all the scheduling life cycle and ensure a maximum of performance [START_REF] Herroelen | Project scheduling under uncertainty : Survey and research potentials[END_REF].

A schedule is robust if this performance is few sensible to data uncertainties and variations. Moreover a schedule has to be flexible to be adaptable to the possible disturbance. We can identify a static flexibility as the temporal flexibility (concerning tasks starting date), the sequential flexibility (which authorises the permutation between tasks, and which supposes the temporal flexibility) or the assignment flexibility (which allows changing of resource after a first assignment). There is also the dynamic flexibility which is the scheduling capacity to adapt itself to disturbances [START_REF] Trung | Utilisation d'ordres partiels pour la caractérisation de solutions robustes en ordonnancement[END_REF].

In this paper, we consider that, in a given schedule, task data are subject to more or less variations in order to be representative of the reality. Variations location will depend on the task nature. A preventive maintenance activity is well known and well documented, its face duration will be considered as determinist.

However its release date depend on the current production work order end. The due date of a preventive maintenance will depend on the potential equipment breakdown due to the absence of repair. It can not be known before it occurs. Then release date and the due date, for a preventive task, can be modeled as fuzzy data. Contrary to the preventive activities, corrective maintenance tasks processing time can just be estimated. Their durations depend on a correct diagnosis.

The release dates of this type of task is generally known because corrective maintenance are generally due to a breakdown and the equipment is stopped. Their due dates are also considered as known because from the breakdown, the equipment availability level goes down. Then corrective maintenance task duration can be modeled as a fuzzy data. The fact that tasks treatment required human resource implicate knowledge on their competence levels. This one being estimated (and then considered as fuzzy), the real task duration, for all type of task, will be modeled by a fuzzy duration. Finally, the most delicate disturbance, that may happen, is a new task arrival which has to be inserted in the current schedule. Its parameters are of course subject to estimation, and there precision depend on the diagnosis exactness.

Scheduling using fuzzy logic

Scheduling using deterministic data are useful in context where there is no source of uncertainties. However in an industrial context and especially in a maintenance environment, datas used are often estimated and have a degree of uncertainties. Solutions given by a deterministic scheduler will then not be feasible and far from the real optimum. That is why uncertainties have to consider during the modeling phase.

As in many scheduling context, the main source of uncertainties is the processing time of the different tasks. The nature of each maintenance process task is fuzzy. For example the corrective maintenance tasks depend of a correct diagnosis. The notion of fuzzy is a generalization of the classical set notion where the membership of an element to a set is true or false. Fuzzy logic was introduced by Zadeh, to deal with problems where data are not deterministic [START_REF] Zadeh | Fuzzy sets[END_REF]. Fuzzy set theory uses multi-valuated function to represent the membership of an object in a set rather than true or false in the classical binary theory. It quantifies how an element is considered as being in a set. Guiffrida and Nagi published a survey on fuzzy set theory applications in production [START_REF] Guiffrida | Fuzzy set theory applications in production management research: a literature survey[END_REF]. A great number of work used fuzzification to represent due dates or processing time and makespan. Job earliest/latest starting date in maintenance being dependent of a fuzzy release date are of course fuzz. The tasks completion time depending of tasks predecessor are then also fuzzy. Many works had been done concerning job-shop and flow-shop problems in fuzzy environment (Petrovic et al. 2006) [START_REF] Petrovic | A new approach to two-machine flow shop problem with uncertain processing times[END_REF].

MODEL

Tasks

Tasks characteristics are modeled as follow : if the task j is a preventive maintenance tasks:

• p p j : face duration of the preventive maintenance task j.

• rp j : fuzzy release date of the preventive task j. Uncertain release date of operation j is modeled by a fuzzy set rj with a triangular membership function given by a triplet (r 1 j , r 2 j , r 3 j ). • dp j : fuzzy due date of the preventive task j. Uncertain due date of operation j is modeled by a fuzzy set dj with a triangular membership function given by a triplet (d 1 j , d 2 j , d 3 j ).

If the task j is a corrective maintenance tasks: • pc j : fuzzy face duration of the corrective maintenance task j. Uncertain processing time of operation j is modeled by a fuzzy set pj with a 4 points shape membership function given by a quadruplet (p 1 j , p 2 j , p 2 j , p 3 j ). • r c j : release date of the corrective maintenance task j. Generally equal to the corresponding breakdown date.

• d c j : due date of the task j (this value is estimated in function of the current availability of the equipment concerned), And for each maintenance tasks:

• w j : penalty which could be claimed if the treatment of the task j is not performed on time.

Human resources

The maintenance service is composed by m human resources (i = 1...m), characterized by a skill profile. Relative speeds do not depend only on the tasks. Each resource has a fuzzy corresponding qualification level for each task. Operators will perform them more or less quickly. The fuzzy duration of the job j, by the human resource i is denoted by pij . With:

pij = f (p j , Comp ik ), ∀i ∈ {1, ..., m} (1)
Where Comp ik is the fuzzy skill rate set of resource i in the competence which is required to achieve the type of task k. Comp ik has a triangular membership function given by a triplet (Comp 1 ik , Comp 2 ik , Comp 3 ik ). It can be represented with a matrix in which, for each different kind of job, where the corresponding rate to the required competence can be found.

   Comp 1,1 • • • Comp 1,k . . . . . . . . . Comp m,1 • • • Comp m,k   
Fuzzy membership function of face duration, release date and competence rate are presented on the figure 1.

The treatment duration of two different tasks by two different resources enables observing that for one kind of task, a resource can be more powerful than one other, whereas, for the second task, it is the second one which is the most efficient.

In our problem, we will consider a current schedule (already computerized) which integrates n tasks that had been already assigned to m human resource. The current schedule can be modeled as a graph. The graph is a unit of branches which represent each one a human resource schedule. They are composed of nodes which represent tasks and arcs which are the potential constraint between to tasks (precedence).

The valuations of arcs are the duration of the origin task. Tasks are placed between a fictive beginning task B and fictive end task E. There is no link between branches, because resources work independently.

Variables

The variables of our problem are the following ones for each task j:

• t j (j = 1...n) : Planning date of the task j,

• x ij (j = 1...n and i = 1...m) : 0-1 value representing the tasks assignment. x ij = 1 if the task j is assigned to a resource i, else x ij = 0, • Ci,j (j = 1...n and i = 1...m) : fuzzy completion time of the task j, assigned to a resource i, • T j (j = 1...n) : lateness of the task j, • ES j (j = 1...n) : earliest starting date of the task j, • LS j (j = 1...n) : latest starting date of the task j, • R (S) : Robustness measure of a schedule S,

Constraints

Each task has to be assigned only once to only one resource:

n j=1 x ij = 1, ∀i ∈ {1, ..., m} (2)
A task j cannot be planned before the equipment i is available: ∀j, t j r i (3)

Objectives

In order to consider corrective maintenance, we have to insert dynamically tasks in a current schedule. However it is difficult to insert tasks in a schedule which is subject to variations between the proposed one and Fig. 2. Current planning the reality. In order to find new task insertion solutions, we have to determine which place are the most flexible and consequently propose the most robust schedule (the less sensible to variations). The fact to propose solutions taking into account variations by anticipating them, signify that our scheduling approach is proactive. Tasks which are finished late decreasing the equipment availability ratio imply that we have to minimize the total weighted tardiness.

min n j=1 w j T j , (4)
The aim of our work being to schedule human resources activities, our methodology will take into account their individual performances to find the best resource for each task. But it will also consider the existing workload in order to distribute activities between employees.

ROBUSTNESS MEASURE

The scenario where the robustness measure intervene is a case where a new task has to inserted within a schedule. This one is add to the schedule at each place of this one and the robustness is evaluated through the measure. The schedule which will be conserved will be the one with the highest robustness measure. In case of equality the choice is given to the manager.

In order to obtain the completion time of each job, fuzzy operation have to be used. The fuzzy task duration adds to the fuzzy release date will allow to obtain the fuzzy set representing the completion time computation. As the difference with [START_REF] Song | Handling fuzzy constraints in flow shop problem[END_REF] where there is precedence constraint, here the fuzzy completion time is obtained with:

Ci,j = ∼ max rj , Ci,pred(j) +p i,j (5)
where + is the fuzzy addition operator and max is the fuzzy maximum operator.

Robustness measure is used to show the difference between solutions which are subject to uncertainties. It evaluates the lateness potential of a solution. A task lateness is defined by the fact that its completion date is reached after its due-date. In other words if the task is not finished at the due-date means that it will be late. In classic logic, the fact that a task j is not finished, correspond to the interval (-∞; C j [. If the task is not finished before the interval [D j ; +∞) the task will be late. An intersection between these intervals means that there is a lateness. In fuzzy logic the completion date and due-date will be the fuzzy intervals Cj and Dj . Intervals previously obtained will correspond respectively to (-∞; Cj [ and [ Dj ; +∞). Their membership functions will then be µ (-∞; C[ and µ [ Dj ;+∞) as shown on the figure 3 [START_REF] Dubois | Fuzzy constraints in job-shop scheduling[END_REF]. A robust schedule is defined as being insensitive to disturbances [START_REF] Leon | Robustness measures and robust scheduling for job shops[END_REF]. Wu and al. developed a methodology to measure scheduling robustness and a methodology to realize robust schedule in case of disruption due to control.

An other measure of the schedule robustness had been defined by Chen and Muraki [START_REF] Chen | A fuzzy evaluation of schedule robustness under processing time variations in batch plants[END_REF] for the scheduling in batch processes. An adaptation of this measure is defined as being the average degree of conflict on the individual constraint between a task and it's due date constraint, as observed on the figure 3. Where the fuzzy membership function µ lateness (t) shows the potential lateness.

The fuzzy membership function µ lateness (t) is obtain from the equation 6. However, the robustness represents the fact that his performance is few sensible to data uncertainties and variations. The fuzzy membership function µ in timej (t) is then obtain from the equation 7. Since all constraints have not the same importance we introduce the weight j penalty factor (described in the equation 8) to weight the different conflict in the equation 9. n denote all the different conflict locations within the schedule S and R (S) will then give its robustness level. A robust schedule will have an index R (S) = 1 contrary to a schedule which is sensible to variation which will obtain R (S) = 0.

µ latenessj (t) = min µ Ci,j (t) , µ dj (t) (6) µ in timej (t) = 1 -µ latenessj (t) (7)
weight j = w j / max j (w j ) (8) R (S) = 1 n n j=1
µ in timej * weight j (9)

COMPUTATIONAL RESULTS

In order to compared and evaluated the proposed method, we will used the simulation methodology proposed in [START_REF] Marmier | Dynamic scheduling of maintenance activities under uncertainties[END_REF]. A robustness evaluation of the different insertion possibilities will be given. The different possibilities will be tried by simulation and a correlation between the robustness level and the objective study will be done. Then the observed correlation would allow us to choose the correct insertion place in an existing schedule, without simulating different cases.

CONCLUSION

In this article we developed an approach to evaluate the robustness of a schedule. It is useful when inserting a new task. We compared this approach with a simulation methodology. There is a correlation between simulation results and the robustness evaluation. This correlation signify that the robustness evaluation could give an idea from an eventual simulation result. Then both approaches can give results following the same criteria. Moreover the robustness evaluation is more quickly obtained, only few seconds comparing to simulation duration which is in minutes. A good representation of the reality is not composed of only one criteria. This correlation allow us to imagine to use the robustness evaluation with fuzzy logic as a criteria for a maintenance activities scheduling multi-criteria study.

Fig. 1 .

 1 Fig. 1. Fuzzy membership functions

Fig. 3 .

 3 Fig. 3. Lateness possibility in case of conflict

Fig. 4 .

 4 Fig. 4. Robustness evaluationOn the figure 4, we can observed the comparison between a solution which has been obtained without considering uncertainties and a robust one obtained by simulation. For both solutions we evaluated the robustness level with the methodology presented before. Tests which has been done on the figure4are a new task dynamic insertion in different existing planning with three different workload.


Dr Thoru Shimizu

From saprophytic to toxigenic clostridia, a complex evolution based on multiple diverse genetic transfers and/or rearrangements

Editorial

From saprophytic to toxigenic clostridia, a complex evolution based on multiple diverse genetic transfers and/or rearrangements *

The genus Clostridium, the definition of which is based on four criteria e rod-shaped, spore-forming, Gram-positive and an obligate anaerobic bacteria e comprises an extremely vast and heterogeneous group of bacteria. More than 150 species of clostridial species have been described. Most of them are fermentative bacteria involved in many biochemical transformations of various substrates, and are not associated with pathological processes. However, a few clostridial species, around 15 of them, produce highly potent toxins known to be responsible for severe diseases in man and animals, and are crucial biological threats.

The first evidence of bacterial life in strict anaerobic conditions was provided by Louis Pasteur (1861). He described a microbe that produced butyric acid and butanol and was unable to grow in the presence of oxygen. He named this microorganism Vibrion butyrique due to the major fermentation product, butyrate, and to the fact that it was a mobile rod. Pasteur introduced the term "anaerobic" to define the mode of life without free oxygen. A. Trecul (1867) first used the name "Clostridium", a diminutive form (kloth-ster) of the Greek word "kloth", to designate a small spindle; this was then latinized into Clostridium, corresponding to the shape of the microorganism in its sporulating form. Adam Prazmowski (1880) distinguished straight rods containing a spore (Clostridium) from the sporulated curved rods (Vibrio) and proposed the name Clostridium butyricum for Pasteur's V. butyrique, which was found to be identical to the Bacillus amylobacter of Van Tieghem. Thereby, the term Clostridium was based on the morphology of the bacteria containing a spore, but not on their physiology. The metabolic distinction between Bacillus (aerobic) and Clostridium (anaerobic) was introduced later in 1922, by the Committee on Classification of the Society of American Bacteriologists [START_REF] Bengtson | Studies on organisms concerned as causative factors in botulism[END_REF].

Pasteur's preparation was probably not a pure culture. B. amylobacter of Van Tieghem, renamed C. butyricum by Prazmowski, was the first isolated Clostridium strain and is considered as the type strain of the genus Clostridium.

The first pathogenic Clostridium isolated in pure culture and identified as producing a toxin was Clostridium tetani, by Kitassato in 1889. Then Achalme (1891) obtained the first culture of Clostridium perfringens from a case of rheumatism case. This bacterium was further characterized by Welch and Nuttal (1892), who initially designated it as Bacillus aerogenes capsulatus and showed the importance of this pathogen in gas gangrenes. Bull and Pritchett (1917) found that the cause of death was not related to blood invasion by these bacteria, but to a poisonous substance produced during bacterial growth in the tissues. McFarlane and Knight (1941) showed that the lethal and hemolytic "a-factor" was lecithinase C. It was the first bacterial toxin identified as exhibiting enzymatic activity, and the first described mode of action of a protein toxin. In 1895, van Emmingen identified the causative agent of botulism, Bacillus botulinum, later renamed Clostridium botulinum, which he isolated from ham and from a victim of a severe botulism outbreak in Belgium. Clostridium difficile was first identified as a resident bacteria of the colonic microflora of newborns by Hall and O'Toole in 1935. Although C. difficile was reported to be a toxin producer by Snyder in 1937, it was recognized as an important enteropathogen several decades later, starting with the original observation by Larson et al., in 1977 of a cytotoxin in the stool of a patient with pseudomembranous colitis (rev in [START_REF] Bartlett | Clostridium difficile: history of its role as an enteric pathogen and the current state of knowledge about the organism[END_REF]). In the meantime, additional toxigenic Clostridia, as well as solventogenic Clostridia, have been characterized.

Since the first historical descriptions of clostridial species, an increasing number of techniques and methods have been used to further characterize these bacteria and their metabolism products, including toxins and virulence factors. Among them, whole genome sequencing is one of the most powerful approaches for gaining access to a global understanding of the potential properties of bacteria. However, many genes are still assigned to unknown functions, and gene expression appears to result from ever more complex and diverse regulation networks. In addition, whole genome sequencing has evidenced genetic relatedness and gene exchanges between bacteria, thus leading to a better understanding of bacterial evolution and adaptation to specific environments. Among more than 150 clostridial species described until now, clostridia of medical and industrial interest have been the most thoroughly investigated. This special issue focuses on recent genetic advances in pathogenic clostridia.

The main habitat of clostridia is the environment, where they can survive due to their spores. Sporulation and germination are more complex processes in clostridia than in Bacillus, which are also sporulating bacteria but with an aerobic or aero-anaerobic metabolism. While starvation of carbohydrates is the main signal inducing sporulation in Bacillus, clostridia require a sufficient level of energy and use a more complex and as yet only partially defined signaling pathway for sporulation. These aspects, which are important not only for understanding physiological mechanisms of this bacterial group but also for developing efficient preventive measures in hospital hygiene and the food industry, are discussed in two reviews [START_REF] Olguín-Araneda | Recent advances in germination of Clostridium spores[END_REF][START_REF] Talukdar | Updates on the sporulation process in Clostridium species[END_REF].

An intriguing question is how, among the numerous clostridia which are environmental bacteria, a few species (about 15) have acquired the capacity to produce the most potent toxins known e and to which purpose? Clostridium species are fermentative bacteria which have adapted themselves to diverse ecological niches through specific enzymatic equipment enabling utilization of various substrates. Some clostridial species are autotrophic and obtain their energy from inorganic chemicals, but many others use organic polymers as substrates such as polysaccharides (cellulose, starch, pectin, etc.), proteins, and peptides [START_REF] Bruggemann | Comparative genomics of clostridia: link between the ecological niche and cell surface properties[END_REF]. Thereby, they secrete diverse hydrolytic enzymes that degrade high molecular weight substrates in the surrounding microenvironment of the bacteria and then absorb, through numerous transporters, breakdown monomers required for their metabolism. Clostridia have an essential role in the environment in recycling of various compounds, mainly organic molecules. Indeed, clostridia are the main bacteria involved in animal cadaver decomposition and plant degradation. Most pathogenic clostridia are defective in amino acid biosynthesis pathways and hydrolyze proteins or peptides, then absorbing amino acids. Based on the mechanism of action, most bacterial toxins can be divided into poreforming toxins and toxins active through an enzymatic activity. Genetic and structural analyses support the notion that bacterial toxins have evolved from ancestor genes that are also at the origin of genes for regular structural and/or functional components of bacteria. Indeed, enzymatically active toxins probably derived from ancestral hydrolytic enzymes or enzyme precursors. A likely evolution mechanism might include mutations in enzyme ancestor gene(s) leading to modification of substrate specificity, from non-essential to highly critical molecules in cell survival or physiology, resulting in the emergence of a novel enzymatic toxin or toxin domain. Subsequent combination or fusion of the new enzyme domain with a delivery system able to transport and internalize the catalytic domain into specific target cells might yield highly potent toxin(s) [START_REF] Popoff | Genetic characteristics of toxigenic Clostridia and toxin gene evolution[END_REF]. For example, clostridial neurotoxins retain the proteolysis enzymatic site of zinc-dependent metalloprotease, which is common to many collagenases and proteases produced by various clostridia like Clostridium histolyticum and other bacteria. However, in contrast to collagenases and proteases used by clostridia for utilization of a wide range of protein substrates, clostridial neurotoxins have acquired a binding domain specific of a neuronal cell surface receptor that mediates their entry into only certain neurons, and highly specific proteolytic activity toward SNARE proteins, thus leading to specific inhibition of neurotransmitter release [START_REF] Doxey | Insights into the evolutionary origins of clostridial neurotoxins from analysis of the Clostridium botulinum strain A neurotoxin gene cluster[END_REF][START_REF] Popoff | Genetic characteristics of toxigenic Clostridia and toxin gene evolution[END_REF]. Interestingly, the two main types of clostridial neurotoxins, botulinum neurotoxins (BoNTs) and tetanus neurotoxin (TeNT), have followed distinct evolution pathways, albeit structurally and functionally closely related. BoNTs have sustained numerous genetic rearrangements (mutations, duplication, recombination), resulting in multiple BoNT types and subtypes, whereas only a unique TeNT sequence has been reported until now. Similarly, the genome background of BoNT-producing clostridia is extremely diverse, and only restricted genetic diversity is observed in C. tetani strains (see [START_REF] Bru ¨ggemann | Genomics of Clostridium tetani[END_REF][START_REF] Carter | Genomes, neurotoxins and biology of Clostridium botulinum group I and group II[END_REF][START_REF] Sakaguchi | Genomics of Clostridium botulinum group III strains[END_REF][START_REF] Smith | Historical and current perspectives on Clostridium botulinum diversity[END_REF]).

Genetic variability in toxin genes and genomic background is also prevalent in other pathogenic clostridia, such as C. perfringens, C. difficile and Clostridium sordellii (see [START_REF] Freedman | Clostridium perfringens type A-E toxin plasmids[END_REF][START_REF] Hassan | Genomic analyses of Clostridium perfringens isolates from five toxinotypes[END_REF][START_REF] Janezik | Genomic diversity of Clostridium difficile strains[END_REF][START_REF] Vidor | Antibiotic resistance, virulence factors and genetics of Clostridium sordellii[END_REF]). However, toxin genes are not all equally submitted to genetic variation. For example, in C. perfringens, the genes of enterotoxin, epsilon, beta and iota toxins are highly conserved, whereas other toxin genes, like those of alpha and beta2 toxins, exhibit variable sequences [START_REF] Freedman | Clostridium perfringens type A-E toxin plasmids[END_REF][START_REF] Popoff | Genetic characteristics of toxigenic Clostridia and toxin gene evolution[END_REF]. This raises the question of selective pressures and environmental factors that trigger or control the genetic variability of these pathogens, but differently according to the Clostridium species. Genomic variation might possibly correspond to bacterial adaptation to a new ecological niche, for example, from an environmental site to a host compartment such as the digestive tract or deep tissue subsequently to a wound, which are the most accessible sites for environmental bacteria. But why do certain pathogenic clostridia exploit such extended genetic variation? If the human digestive tract is the preferred host ecological niche for C. difficile, what is the significance of the numerous genetic variants of this opportunistic pathogen? Does genetic diversity represent specific adaptation so as to counterbalance multiple human microbiota, which represent the first line of defense against intestinal colonization? And what is the role of toxin gene variation in this adaptation process?

Genomic variability in clostridia is also mediated by horizontal gene transfer between intra-and inter-Clostridium species, and possibly other bacterial species or eukaryotic cells [START_REF] Moran | Recurrent horizontal transfer of bacterial toxin genes to eukaryotes[END_REF]. Indeed, mobile genetic elements, including plasmids, phages and transposons, are common in the genomes of pathogenic clostridia and are involved in mobilization of toxin genes between bacteria. The digestive tract, which harbors the densest population of bacteria, is a favorable ecosystem for genetic exchanges between bacteria. Thus, pathogenic clostridia, which colonize the intestinal tract, are those which show the greatest genetic variability. Different genetic supports and mechanisms are used by distinct pathogenic clostridia. Plasmids are the preferred support for toxin genes and subsequent genetic transfer and rearrangements in C. perfringens and, to some extent in C. botulinum, whereas in C. difficile, toxin genes are chromosomally located and are submitted to intense genetic variation. These aspects are discussed in [START_REF] Hassan | Genomic analyses of Clostridium perfringens isolates from five toxinotypes[END_REF][START_REF] Janezik | Genomic diversity of Clostridium difficile strains[END_REF][START_REF] Mullany | Mobile genetic elements in Clostridium difficile and their role in genome function[END_REF][START_REF] Sakaguchi | Genomics of Clostridium botulinum group III strains[END_REF][START_REF] Smith | Historical and current perspectives on Clostridium botulinum diversity[END_REF].

It is not clear whether acquisition of toxin genes through horizontal gene transfer or gene evolution provides selective advantages to environmental bacteria such as clostridia. Clostridia are adapted to survive and develop in various environmental niches. Indeed, production of potent toxins leading to host death provides an abundant source of organic materials enabling massive growth of clostridia in cadavers, but bacterial multiplication in the intestinal tract throughout the life of the animal would result in greater Clostridium development over a longer period of time. Diseases due to toxigenic clostridia are an accidental connection between a host and an environmental bacterium which synthesizes a specific toxic compound, rather than resulting from bacterial strategy to invade an organism and subsequently survive in this new environment sheltered from host defenses.

But why is toxin synthesis by clostridia such a strongly regulated process? Toxin gene regulation was intensively analyzed in C. perfringens. Although some mechanisms of toxin gene regulation are conserved in toxigenic clostridia, distinct species such as C. botulinum, C. difficile, C. sordellii and C. tetani have developed specific regulatory pathways apparently triggered by different environmental factors, as discussed in [START_REF] Bouillaut | Integration of metabolism and virulence in Clostridium difficile[END_REF][START_REF] Connan | Two-component systems and toxinogenesis regulation in Clostridium botulinum[END_REF][START_REF] Dahlsten | Mechanisms of food processing and storage-related stress tolerance in Clostridium botulinum[END_REF][START_REF] Ohtani | Regulation of toxin gene expression in Clostridium perfringens[END_REF]. Do clostridial toxins and their different regulation systems, coupled with specific environmental signals, play a role in circumventing the barrier effect of resident microbiota to colonize the host digestive tract, which is the most common organism site invaded by clostridia?

Intestinal and tissue colonization by clostridia also involves additional virulence factors like membrane proteins and other factors for attachment to various substrates. Whole genome sequencing is a powerful tool for revealing potential toxin and virulence factor genes and for estimating the potential pathogenicity of a Clostridium species or isolate. For example, genome sequencing of C. tetani led to identification of an array of cell-surface-associated proteins related to adhesins [START_REF] Bruggemann | Comparative genomics of clostridia: link between the ecological niche and cell surface properties[END_REF]. Recent genome sequencing of Clostridium chauvoei, the agent of severe myonecrosis in cattle, shed light on potential toxins and metabolic pathways possibly involved in pathogenesis due to this microorganism [START_REF] Frey | Patho-genetics of Clostridium chauvoei[END_REF]. A major step was achieved, via whole genome sequencing, in unraveling the genetic evolution of pathogenic clostridia from saprophytic ancestors by highlighting phylogenetic relatedness and DNA exchanges, as well as deciphering putative virulence factors in addition to already known toxin genes. However, functional analysis of each gene possibly involved in pathogenicity, and its regulation network, remain to be performed. While clostridia are potent pathogens, they also provide efficient therapeutic tools, such as spores in transport systems for therapeutic molecules in the treatment of tumors [START_REF] Kubiak | The potential of clostridial spores as therapeutic deliver vehicles in tumour therapy[END_REF], and toxins like BoNT in dystonia therapy.

Editorial / Research in Microbiology 166 (2015) 221e224

Available online 2 March 2015

Acknowledgments

All contributors to this special issue are warmly acknowledged for providing excellent reviews in their domain.

Particular attention is devoted to the memory of Dr. Thoru Shimizu, who passed away just as this special issue was being launched, and to which he had agreed to participate. His scientific contribution, along with his team, unraveled a large amount of knowledge of genetics and toxin gene regulatory pathways in C. perfringens, which were used as paradigms in the other toxigenic clostridia. Dr. Kaori Ohtani courageously agreed to present recent concepts developed in this field by T. Shimizu and his team.

Conflict of interest

None.


P Haurant
email: haurant@univ-corse.frmarc.muselli@univ-corse.fr

M Muselli
email: marc.muselli@univ-corse.fr

P Oberti

MULTICRITERIA DECISION AIDING FOR SELECTION OF PHOTOVOLTAIC PLANTS ON FARMING FIELDS IN CORSICA

Keywords:

Corsica knows an unprecedented photovoltaic plant projects flow since its energetic strategy was turned to renewable energy. Concerned public institutions needed specific tools to select the most relevant projects among numerous one with transparent and advise way. A multicriteria decision aiding method is developed in this aim in order to select projects among sixteen ones (whole PV power: 93.5 MWp) on farming fields in Corsica. The study follows all the multicriteria methodology steps which are criteria and constraints definition, criteria weights sets calculations, thresholds and concordance level determination and the chosen multicriteria model, that is ELECTRE-IS, implementation. Thus, considering different points of view from the ecological to financial one, eight criteria, one of which being optional, have been defined whereas three constraints were determined. The reviewed cards packs methodology applied to the third party allows building six weights sets while the same third party determined a concordance level of 2/3. Thanks to this methodology, based on the criteria sets and according to weights and concordance levels given by the third party, four projects (27.1 MWp) have been selected among the sixteen initial ones, the robustness of these results being tested through all criteria weights sets and different concordance levels applications.

INTRODUCTION

Since Corsica benefits of a high solar potential estimated of 1400 TEP/Ha/yr (Poggi and Notton, 2005) and specific and profitable purchase conditions for photovoltaic electricity : a 20 years guaranteed tariff of 40 cts/kWh against 30 c€/kWh in continental France, the island is one of the most attractive region in France. Thus investing in a photovoltaic plant has a profitability rate of about 6.5% (ADEME, 2006). In this context, the island knows an important photovoltaic plant private project offer, which cumulated potential power attains 257 MW, knowing that the installation potential is 46 MW c . The "Collectivité Territorial de Corse" (CTC) and the "Chambre d'Agriculture Départementale de Haute Corse" (CA2B) are among the public institutions that are solicited for their opinion about each photovoltaic plant project. They have expressed the necessity of a multicriteria evaluation for each plant project. Thus, the CTC has built a photovoltaic development charter and a project evaluation process that have been voted on June the 29 th , 2009 by the Corsica's assembly whereas the CA2B, which has to give her opinion particularly on projects that are susceptible to be implanted on farming fields, ordered university of Corsica an evaluation survey on 16 projects with the view to base her opinion on rigorous arguments.

STUDY PROBLEMATIC AND METHODOLOGY

Institutional actors and decision-makers, who are even more interrogated to judge each project relevance and feasibility, have the aim to give transparent and informed opinions to industrials. This study deals with a concrete selection problematic of photovoltaic plant projects among 16 projects that have been built and submitted by industrials to local decision-makers. Priorities in our case are:

• Use conflict risks have to be evaluated. Indeed, planed installations are supposed to be placed on farm fields and could potentially take up 311 Ha of cultivated ground.

•

A 30% limit of renewable energy sources production has to be respected, resulting from a regional-scaled non interconnected electrical network stability guarantee demand. This ratio corresponds to a 100 MWc renewable production limit in the Corsican's case, but a. recent decree set the renewable production limit at about 83MW c . Existing plants (three wind farmers) produce already 18 MW c , and accepted wind farmer and PV projects represent 19 MW c so that only 46 MW c renewable energy can be integrated by the network nowadays, whereas the projects set represents a 93.5 MW c potential cumulated power only for the Haute-Corse county, in our study's framework, going beyond the maximum calculated for the whole Corsican region.

•

Territorial electricity production overabundance has to be avoided: geographic concentration risk of energetic offer has to be considered to avoid sudden energetic production falls due to climatic or technical factors. The projects set is dispersed on three restricted geographic zones and it concerns only four electrical link posts. The projects intended for being linked to the electrical network through the same link post have been treated simultaneously in order to fulfil the abundance shunning demand, so that recommendations are expressed for each electrical post.

•

Social acceptability has to be taken into account: negative and positive impacts due to such installations on local population must be studied (visual, financial impact).

•

Ecological impact must be evaluated: photovoltaic plants are supposed to represent sustainable alternatives for electrical production, but such important plants have also an ecological cost that must be evaluated to ensure their real ecological benefits. Finally, projects evaluations are based on files, criteria are informed from a simple lecture of the files and without field visit, so that the study is built on mesoevaluations in her main part.

CONSTRAINTS AND EVALUATION CRITERIA

Three pre-selection constraints (Table 1), or "acceptability or eligibility conditions that actions have to satisfy imperatively to candidate for the decision or/and the multicriteria study" (Oberti, 2004) have been defined, translating the third party's and the different actors imperatives. Five criteria among the seven key ones are evaluated from notation obtained thanks to evaluation tables built according to three factors:

• the study third party's priorities ; •

The available information given in the projects files • Indications supplied from the literature.

MULTICRITERIA OUTRANKING AGGREGATION AND PRINCIPAL RESULTS

The performances tables' information aggregation, thanks to outranking multicriteria model, allows the selection of the more restricted alternatives sub-set including the best compromised ones and those that must not to be eliminated.

Thresholds

The two alternatives i a and k a comparison, according to j g criterion, leads to a relation that covers from an indifference situation to a strict preference in one of these alternatives' favor, justifying a pseudo-criteria discrimination thresholds based model use whereas a veto threshold that fixes a bad performance compensation limit of an alternative on a criterion by a good one on other criteria can be defined.

Criteria relative weights

The actors express the relative importance of the

k s i s k s i a R a A a A a , , ' ' ∈ ∀ ∈ ∀ and l s i s i s l a S a A a A a : , ' ' ∈ ∃ ∉ ∀ ) 5 FINAL SELECTION AND PROJECTS RECOMMENDATIONS
A performance table sums up the usefulness information set for a multicriteria calculation, except for a few intern technical or economical parameters that are outranking model's own. This table is usually composed of three informational parts: each alternative evaluation on each criterion, criteria relative weights and thresholds.

The multicriteria model ELECTRE 1-S (Figueira et al., 2005) application leads to determine an outranking final graph kernel, a set composed of selected projects. This model has been applied to 72 cases, combining:

• Four electrical link posts; • six criteria relative weights sets: two aim sets have been depending on the criteria set integration of the eighth criterion or not, from which four other weights sets have been built thanks to ±5% variations of the Z factor.

•

A majority level of 2/3, defined by the CA2B, and two of the nearer values to test the results stability. Finally, four among the sixteen photovoltaic plant projects studied for the Haute-Corse County have been selected thanks to the outranking model ELECTRE 1-S application. Table 3 sums up the selected projects.

CONCLUSION

The ELECTRE-IS model application allows concluding about selection or not of each project in 18 cases, considering two criteria sets, each one is combined with three weights sets, and the three concordance values.

A project is definitively acceptable if it is unanimously selected (Figure 1) whereas some other projects that are accepted only in specific cases are rejected.

Electrical link posts

Selected

Figure 1 :

 1 Figure 1: Initial projects set localization (left) versus final projects set localisation (right)

Table I :

 I Constraints definitions (Roy, 2000), criterion is the central point of a multicriteria decision aiding study. Seven evaluation criteria have been elaborated to compare projects from different points of view: energetic, economic, ecologic visual or territorial use whereas an eighth one, the annual additional incomes for communal budget per inhabitant intervenes, is optional. Table2presents the pertinent criteria built for this specific study and listed by the Haute-Corse chamber of farming.

	Constraints	Definitions
	C 1	Plants dismantling guarantee: plants
		dismantling must be guaranteed in the
		exploitation contracts.
	C 2	Respect of constraints linked to area's
		ecological classification: concerned areas
		must not be classified Natura 2000 or
		wetland
	C 3	Constraints linked to area's
		topography: areas' slopes must not
		exceed 10%
	According to information obtained in the projects files
	that have been studied, the projects filled up all these
	conditions.
	'Tool created to evaluate and compare potential actions
	from a point of view.'

Table II :

 II Criteria for plants projects evaluation

	Point of view	Code	Criteria title	Criteria creation principle	Scale terms	Preference way
	Energetic	g 1	Net production	Energy production	GWh annual	Maximize
				evaluation
	Geo-economic	g 2	Ratio of rent area	Ratio between free area	%	Maximize
			unoccupied by the	of productive land
			installation	and the total
	Ecological	g 3	Ecological	Weighted sum	Points	Maximize
			potential degradation
	Visual Impact	g 4	Relevance of visuaL Weighted sum	Points	Maximize
			impact presentation
			in the files
	Visual Impact	g 5	Observers-plants	Measures from cartography	km	Maximize
			minimum distance
	Territorial use	g 6	Use conflicts risks	Weighted sum	Points	Maximize
	Financial effect	g 7	Economic activity	Weighted sum	Points	Maximize
			and inhabitants' financial
			aid for RES facilities
	Financial effect	g 8	Financial incomes at Ratio between professional	€/yr/inhab	Maximize
			communal level	duties evaluation and
				communal population