Rudy Romain

Hélène Louis

Philippe Verkerk

Daniel Hennequin

Measuring the re-absorption cross section of a Magneto-Optical Trap

Magneto-Optical Traps have been used for several decades. Among fundamental mechanisms occuring in such traps, the magnitude of the multiple scattering is still unclear. Indeed, many experimental situations cannot be modeled easily, different models predict different values of the reabsortion cross section, and no simple experimental measurement of this cross section are available. We propose in this paper a simple measurement of this cross section through the size and the shape of the cloud of cold atoms. We apply this method to traps with a configuration where theoretical values are available, and show that the measured values are compatible with some models. We also apply the method to configurations where models are not relevant, and show that the re-absorption is sometimes much larger than the usually assumed value.

I. INTRODUCTION

The Magneto-Optical Trap (MOT) is today an essential tool in experimental atomic physics. A MOT produces ultracold atoms which can be used in numerous experiments: MOTs are used -alone or with further cooling steps -to study quantum chaos [1], Anderson localization [2] or plasma instabilities [3,4], to produce ultra precise atomic clocks [5], to obtain cold molecules [START_REF]Cold Molecules: Theory, Experiment, Applications[END_REF], and many other studies.

In most experiments, an accurate knowledge of the detailed physical mechanisms occurring in a MOT is not necessary. For example, it is well known that the atomic cloud produced by a MOT becomes unstable for some parameters, but it is also well known that in most cases, the alignment of the laser beams has just to be adjusted to remove these instabilities. However, recent studies have shown that understanding the detailed physics of the MOT could be interesting, because the MOT appears to belong to the large family of complex systems described by Vlasov-Fokker-Planck (VFP) equations [4]. Because MOT experiments are relatively simple to implement within this family, they appear as a good candidate for a model system in this area. And anyway, understanding in detail the physics of MOT would allow to understand what is observed in the experiments.

The mechanisms allowing to obtain a cloud of cold atoms with a MOT are well known. They result from the interactions of the atoms with the laser light. The basic interaction is the absorption of a photon by an atom, followed by a spontaneous emission process. Depending in particular on the cloud density, the emitted photon can possibly undergo several cycles of absorption/emission before escaping the cloud: it is the multiple scattering. The final cloud of cold atoms is the result of the equilibrium between the trapping force (induced by the exchange of momentum during the diffusion cycle), the shadow effect force (induced by the absorption of the beam through the cloud), and the multiple * Electronic address: daniel.hennequin@univ-lille1.fr scattering force. The amplitude of the forces depends in particular on the absorption cross section σ L and on the re-absorption cross section σ R . Knowing these quantities is thus essential to model accurately a MOT. Moreover these cross sections play a key role in the analogy with plasma physics because the effective charge involved in the coulomb-like interaction between cold atoms depends on their ratio [START_REF] Sesko | [END_REF].

The detailed mechanisms involved in a MOT are rather complex. Taking into account the exact distribution of the atomic levels and the interaction of the atoms with all the laser beams would lead to a very complex set of equations. Thus all the existing models deal with approximations which lead to different predictions of the cross section values. This is not a big deal concerning σ L because simple absorption measurements lead to this quantity. On the contrary, no simple way to measure σ R has been proposed until now. So theoretical predictions have never been validated by experimental measurements, and the σ R values found today in the literature are still questionable.

We propose in this paper a method to measure the reabsorption cross section in a magneto-optical trap. We apply this method to a Cesium trap and obtain values of σ R for different sets of laser parameters. We compare these values to different models.

II. THEORY

We consider here a MOT in the usual σ + -σ -configuration. Each of the three arms of the trap consists in a pair of counter-propagating laser beams characterized by their intensity and their frequency. A pair is obtained by retro-reflection of an incident beam. The beam intensities are respectively I + for the incident beam and I - for the retro-reflected one, while their frequency is given through the detuning ∆ between the laser frequency and the atomic transition. We do not need to detail the energetic structure of the cold atoms in order to understand the steady state of the cloud. Indeed, we adopt a global formalism in term of cross sections.

The stationary cloud of cold atoms results from the equilibrium between three forces acting on the atoms. These forces have been expressed in numerous studies, with more or less approximations [4,[START_REF] Sesko | [END_REF][8][START_REF] Townsend | Phase-space density in the magnetooptical trap[END_REF][10]. However, all these models deal with the same variables and the same parameters. The first force is the trapping force produced by the laser beams and the Zeeman shifts induced by the magnetic field. It is a restoring force, characterized by the spring constant κ. The two other forces are collective forces. The shadow effect force is due to the absorption of the laser beams all along the cloud, leading to a local imbalance of the laser beam intensities. Thus this force depends on the absorption cross section σ L . Finally, the multiple scattering force is induced by additional scattering of photons, and so depends on the re-absorption cross section σ R . The first two forces compress the cloud of atoms, while the latter causes it to expand. The size of the obtained atomic cloud is thus the result of an equilibrium between these three forces.

To study the equilibrium, we use an approach similar to that in [START_REF] Sesko | [END_REF] which assumes that the temperature of the cloud is zero. The main assumption in this model is that a photon is re-scattered at most once before escaping the cloud. Contrary to [START_REF] Sesko | [END_REF], we consider the usual anti-Helmholtz configuration for the coils creating the magnetic field, as mentioned previously. Such a field is zero at the point defined as the center of the trap and it can be assumed to be linear along each direction. We take into account the fact that the magnetic field gradient along the coil axis is twice that along the perpendicular directions. So, the spherical symmetry used in [START_REF] Sesko | [END_REF] is broken, and the cloud shape must be modeled as an ellipsoid.

The determination of the stationary density n does not need the knowledge of the forces. Indeed, the collective forces depend on the shape of the cloud, while their divergences do not. The vanishing of the divergence of the total force (which is zero at equilibrium) gives us a constant atomic density. The results from [11], where a more general anisotropic configuration has been considered, can be applied to the present situation and give:

n = 2cκ 3I + σ 2 L (S -1) (1)
where S = σ R /σ L is the cross section ratio and c is the speed of light. Note that as the quadrupolar magnetic field is taken into account, this expression differs slightly from that in [START_REF] Sesko | [END_REF]8]. We can improve this description of the MOT by calculating the expression of the three forces.

The trapping force has a usual form and takes into account the anisotropy of the magnetic field gradient. The shadow effect force has the same expression as is [START_REF] Sesko | [END_REF], the absorption is assumed to be linear. The net multiple scattering force is calculated as the sum over the cloud of all the coulomb-like atom-atom interactions associated with a scattering process. In [11], it is shown how to calculate this force for an ellipsoidal cloud, with half-widths L and L ⊥ along the coil axis and in the transverse plane respectively. A geometric parameter A, depending only on the ellipticity ε = L ⊥ /L of the cloud, appears in the expression of the force:

A = ε 2 ε 2 -1 β (2) β =            1 - 1 √ 1 -ε 2 ln 1 + √ 1 -ε 2 1 - √ 1 -ε 2 f or ε 2 > 1 1 - 1 ε 2 -1 arcsin ε 2 -1 ε 2 f or ε 2 < 1
The equilibrium of the forces gives another condition on this parameter :

A = 1 2 1 - 1 3S (3)
For the sake of completeness, the equilibrium of the forces also gives us access to the cloud displacement due to the shadow effect in our asymmetric configuration. This displacement is global, and depends only on the shadow effect: it gives no information about multiple scattering.

From the previous equations, it is easy to find that ε is bounded. First, the atomic density is a positive quantity so that, in eq. 1, σ R has to be larger than σ L (S > 1). It follows from eq. 3 that A > 1/3. From the same equation, we also find that the maximum value of A is 1/2 (when S → +∞). This leads to:

1 < ε < 1.81 (4)
Thus, the atomic cloud shape of a usual MOT appears to be always oblate. A spherical cloud corresponds to a infinite density, and so is not a physical solution. We also point out an upper limit to the ellipticity which corresponds to σ R ≫ σ L . Fig. 1 shows the cross section ratio versus the ellipticity for all possible values: the more elongated the cloud, the more probable the re-absorption. This result is quite

[9] ∆ 2 2Γ 2 3Ω 2 Γ 2
curve fitting / DAP two-level atom

[10] ∆ 2 3Γ 2 Ω 2 2Γ 2
analytical expression / DAP two-level atom

[4] ∆ 2 6Γ 2 Ω 2 2Γ 2
analytical expression / DAP three-level atom different from the one predicted for the temperaturelimited regime in which the ellipticity of the cloud is constant and equal to √ 2 [START_REF] Townsend | Phase-space density in the magnetooptical trap[END_REF]. In the multiple scattering regime, the ratio S and the cloud ellipticity depend a priori on the laser parameters.

As pointed out above, the calculation of the reabsorption cross section as a function of the laser parameters is rather complex. The atom must be modeled with a particular atomic structure from which the overlap between the emission and the absorption spectra of a cold atom can be calculated. Several authors figured out theoretical expressions of σ R in the context of Doppler cooling theory [4,[START_REF] Sesko | [END_REF][8][START_REF] Townsend | Phase-space density in the magnetooptical trap[END_REF][10], but with different approaches. In [START_REF] Sesko | [END_REF], a fit of single cloud size measurements is performed for only one set of parameter values. [8] performs an approximated analytical calculation, while [4,[START_REF] Townsend | Phase-space density in the magnetooptical trap[END_REF]10] use the dressed atom picture (DAP) [START_REF] Cohen-Tannoudji | Atom-Photon Interactions[END_REF]. All consider a two-level atom, except [4] who considers a three-level atom. These calculations take into account the saturation by the two counter-propagating beams, requiring to introduce the total Rabi frequency Ω = Γ (I + + I -) /2I sat , with I sat the saturation intensity (I sat = 1.1 mW/cm 2 for Cs) and Γ the natural width of the transition.

Within the DAP, the secular approximation limits the range of parameter values to Ω 2 + ∆ 2 ≫ Γ 2 . But even with such a simplification, the expression of σ R remains heavy. Table I summarizes the expressions obtained by these previous studies, in the two limit cases where the laser intensity is much larger than the detuning and vice versa. On the one hand, these two situations (|∆| ≫ Ω ≫ Γ and Ω ≫ |∆| ≫ Γ) give simple asymptotic expressions. And on the other hand, they represent usual experimental parameters. Note that the values of parameters in [START_REF] Sesko | [END_REF] do not fit these two limit cases, and the results from [8] do not seem to be relevant. The expressions derived from the DAP give the same dependence on the laser parameters, but with different numerical factors.

III. MEASUREMENTS

Equations 2 and 3 link the cross section ratio with the ellipticity. As ellipticity can be measured experimentally, we have a way to determine experimentally σ R , and to compare this measurement to the theoretical predictions.

Our experimental set-up is described in [START_REF] Di Stefano | [END_REF]: we use a usual MOT in which each arm is formed by the retroreflection of an incident beam. To guarantee repeatability and reproducibility of the measurement, some cares have to be taken. Indeed, the MOT laser beams can create interference patterns on the cloud. So, its shape is not symmetric and its density is not homogenous. Moreover, the beam relative phase fluctuations make the patterns to move randomly in time. To avoid these effects, we modulate the relative phases of the beams at a frequency larger than 1 kHz. This modulation is faster than the collective atomic response timescale. In addition, the shape of the cloud is very sensitive to the alignment of the beams. We improve the beam alignment to better than 0.1 mrad by observing the cloud and adjusting its symmetry.

In order to measure the ellipticity, we record the cloud fluorescence with a CCD camera, the optical axis of which is perpendicular to the coil axis. In that way, we obtain pictures showing a 2D projection of the ellipsoid. The pictures are fitted on a 2D gaussian, giving us the semi-axes L and L ⊥ of the ellipsoid. A typical experimental measurement consists in recording the cloud sizes as a function of ∆, and repeating this sequence for different values of Ω. For each set of parameters, we record 10 pictures in order to improve the precision and to evaluate the standard deviation.

Note that applying this method for very dilute or very dense clouds leads to large measurement uncertainties. Indeed, this method requires a good signal to noise ratio to monitor the cloud with a camera, which is not the case for dilute clouds, i.e. for large detunings or low laser intensities. On the other hand, in an asymmetric configuration, a thick cloud is displaced by the shadow effect. Simple observations show that the shadow effect degrades also the shape of the cloud, typically when the laser is tuned close to resonance. This issue does not exist for a MOT obtained with six independent beams.

We first check the predicted range of ellipticity values. We measure the cloud sizes for almost 120 different values of (∆, Ω). Fig. 2 shows all the measured values and how often they have been measured. The result is in good agreement with the theoretical range: about 90 % (if we consider error bars) of the measured ellipticities are inside the predicted range. No prolate cloud is observed. Furthermore, most of the values over the limit correspond to pictures recorded with a low signal to noise ratio, i.e. for which the measurement uncertainty is probably underestimated.

Fig. 3 shows the typical evolution of the ellipticity as a function of the detuning. In this example, the minimum value of the ellipticity is 1.4 and is measured around ∆ = -6.5Γ. Points over the 1.81 limit are observed for |∆| 3Γ , but as explained above, errors bars have probably been underestimated for these measurements. Strictly speaking, the two limit cases considered in Table I cannot be satisfied with our experimental parameter values. However, for large enough ∆ values, we approach the conditions |∆| ≫ Ω ≫ Γ . Moreover, as the measurement quality is poor for very large detunings, we retain only intermediate values for our determination of ε. For example, in the case of Fig. 3, the estimation of the cross section ratio is done in the range -8.8Γ < ∆ < -5.5Γ. In this case, we have Ω ≃ ΓI + / √ 2I sat ≃ 2.5Γ and |∆| 2Ω. Note that the secular limit is satisfied because Ω 2 + ∆ 2 > 35Γ 2 . In this interval, the ellipticity is quite constant, as predicted, and we get ε = 1.51 ± 0.08, i.e. σ R = 3.2σ L . This value is in good agreement with [4,10] which gives the theoretical value S th of 3.1.

Table II summarizes the measurements obtained in three different configurations. In each case, the measurement and the predicted value of S are very similar, with a relative difference of less than 5 %. Unfortunately, despite the good precision on the ellipticity, the error on the cross section is significant. This is due to the non-linearity of the relation between these two quantities (Fig. 1). Moreover, we get asymmetric errors because the derivative is also non-linear. As a consequence the smaller the ellipticity, the better the precision.

Of course, the possibility to measure σ R is particularly interesting for parameters where no theoretical predictions are available, or where theoretical predictions are questionable because of the approximations. It is in particular the case for smaller detunings and intensities. Fig. 4 shows the evolution of the cross section ratio for -7.5Γ < ∆ < -1.8Γ and I + ≃ 2.8I sat . It is interesting to note that S exhibits a maximum around ∆ = -5Γ, with values larger than 5. These values are rather high compared to those used in the literature but they are consistent with eq. 1. Close to the resonance, the ratio varies between 1 and 2, values which lead to a dense cloud as expected for these detunings. Whereas far from resonance the ratio is a little bit larger than 2 but the density is small due to a weak restoring.

IV. CONCLUSION

In this paper, we propose a method to determine experimentally the re-absorption cross section σ R in a cloud of cold atoms. To our knowledge, it is the first method which allows to measure σ R for a large set of MOT parameter values. The method is non-destructive and based on ellipticity measurements of the atomic cloud. The reabsorption cross section can be measured very easily. The results of the measurements are in good agreement with the calculation done with the dressed atom picture in the limit studied here (large detunings and intermediate intensities). We also make measurements for MOT parameters for which no theoretical predictions have been done. The measurements show that the cross section ratio is underestimated in the literature in this case. The precision of this method can be as high as desired, it requires only more acquisitions. A good precision is needed especially when an important re-absorption is expected.

Measuring the cross section can be very useful to improve our description of the re-absorption in future studies on spatio-temporal dynamics of the atomic cloud.

Figure 1 :

 1 Figure 1: Evolution of the cross section ratio inside the predicted range of ellipticity values.

Figure 2 :

 2 Figure 2: Measurements of the cloud ellipticity for 117 different values of the MOT parameters. The theoretical range is shown in gray.

Figure 3 :

 3 Figure 3: Evolution of the ellipticity ε versus the laser detuning ∆ for I + ≃ 3.6I sat . The dashed lines show the theoretical limits of ellipticity values (1 < ε < 1.81). The error bars represent the standard deviation from the 10 pictures.

Figure 4 :

 4 Figure 4: Evolution of the cross section ratio versus ∆ for I + ≃ 2.8I sat .

Table I :

 I Comparison of theoretical expressions for the cross section ratio for the two limit cases Ω ≫ |∆| ≫ Γ and |∆| ≫ Ω ≫ Γ.

	ref.	Ω ≫ |∆|	Ω ≪ |∆|	method
	[8]	1	2	phenomenological calculation two-level atom

Table II :

 II Comparison of the experimental determination of S with the predictions. For different intensity values, we give the averaged ellipticity ε measured for a range of large detunings, the deduced cross section ratio S and the theoretical value S th from[4,10].

	Ω 2 /Γ 2	detuning domain	ε	S	S th
	4.5	[-7.0Γ, -5.6Γ]	1.39 ± 0.05	2.2 + 0.3 -0.3	2.3
	7.0	[-8.8Γ, -5.5Γ]	1.51 ± 0.08	3.2 + 1.2 -0.7	3.1
	9.4	[-9.2Γ, -5.5Γ]	1.61 ± 0.09	4.9 + 4.1 -1.6	4.7


J Elgueder
email: jawhar.el_gueder@utt.fr

L Roucoules
email: lionel.roucoules@ensam.fr

E Rouhaud

F Cochennec

DFM synthesis approach based on product-process interface modelling. Application to the peen forming process

Keywords: product-process interface, DFM, virtual prototyping, manufacturing process selection, manufacturing data management, peen forming. 1

Engineering design approach are curently CAD-centred design process. Manufacturing information is selected and assessed very late in the design process and above all as a reactive task instead of being proactive to lead the design choices. DFM appraoches are therefore assesment methods that compare several design alternatives and not real design approaches at all. Main added value of this research work concerns the use of a product-process interface model to jointly manage both the product and the manufacturing data in a proactive DFM way. The DFM synthesis approach and the interface model are presented via the description of the DFM software platform.

INTRODUCTION

For almost 30 years CAD systems have been developed and improved to currently provide very powerful features to support product's forms modelling. PLM approaches and systems have also been highly developed for the last decade to manage the entire product lifecycle information. Nevertheless CAD and PLM systems are currently used the central systems that make the design process a geometriccentred process. CAD model is indeed very often proposed by one person and is used as an input for product analyses (CAM, FEA...). The design experts therefore react and ask for changes that are propagated according to several relations either in the CAD or the PLM model. The design process is then a "redo until right" process.

The paper aims at presenting a design approach based on a DFM synthesis by least commitment 1 process. This approach provides a more proactive position of each design expert (particularly manufacturing) involved in the design process in order to set the CAD model as the result of a collaborative decision making process. The design is then based on a "right the first time" process. This approach is based 1 "Least commitment" has to be understood as "including as less design constraints as possible". CAD model is indeed currently defined thinking of the entire lifecycle (ex. manufacturing, assembly...) but this information is not really explicit in CAD product breakdown. The CAD model is then very often over constrained without any explicit design rationale. The paper focuses on the energetic and manufacturing rationale integrated in design.

on a product-process interface modelling implemented in a laboratory-made DFM_Synthesis software. The process planning expert is then really seen as a designer (see [START_REF] Andreasen | Integrated product development[END_REF]

.2.2).

The global context of IT (CAD and PLM) supported design activity is given in section 2. Afterward, sections 3 and 4 give details of specific issues and introduce the DFM approach proposal. Specific breakthroughs are written regarding the design process and the product modelling. The following section 5 focuses on managing manufacturing information based on the product-process interface. This manufacturing information is definitely linked to product data in order to address CAD modelling and product behaviour and manufacturing simulation according to the selected process plan. The DFM_Synthesis software architecture is illustrated in an example of the aeronautic industry (called Wing Cover in the following text). Finally the conclusion and the perspectives for further work are given.

OVERVIEW OF INFORMATION SYSTEMS IN A CURRENT INDUSTRIAL CONTEXT

Most of CAD systems (ex. CATIA, Pro-Engineer, solidworks ...) currently provide very interesting B-Rep or CGS based algorithms to create forms as edges, wires, faces, shells or solids, to seek those form features (ex. topological explorer, ...) and to change those forms (ex. draft angle, radius...). PLM solutions have also been developed to provide advanced functions for information management (ex. files versioning, files maturity, files access rights...) even if they are only able to manage persistent files and not the given specific data contained in it. This design approach based on PLM and CAD systems has shown its great interest in industry to link specific information (i.e. analysis) to a unique geometrical kernel. Figure 1 shows some of those links (ex. CAD-CAM, CAD-FEA). It is therefore possible to propagate the impact of form features modifications to the analyses whenever in the product development process. Actually, this propagation is really effective in specific "integrated" software during the embodiment and detail design phases and. The problem is still open in the requirements specification and conceptual phases.

PLM AND CAD-CENTRED DESIGN PROCESS ISSUES 3.1. Engineering design process

While CAD and PLM solutions are providing very good supports for information management [START_REF] Liu | Product Lifecycle management: a review[END_REF], new design methods and theories have been proposed in the last fifteen years as explained in a recent sate of the arts [START_REF] Tomiyama | Design methodologies: Industrial and educational applications[END_REF].

The first phases of design (requirements specification, conceptual and embodiment design) aims at assessing requirements and functions in order to define the product structure breakdown and the associated CAD models (parts and assembly CAD models). In those phases of design, the process is based on some fundamental concepts such as FBS [START_REF] Gero | Design prototypes: a knowledge representation schema for design[END_REF] and sometime axiomatic design [START_REF] Suh | Applications of Axiomatic Design[END_REF] when the solution tends to provide independent relation among functional and structural parameters. Afterwards (cf. Figure 1), the detail design phase (CAM, FEA...) other "designers" are assessing this first solution and react by giving some new recommendations (i.e. information integration) for improving the design solution. A lot of collaborative decision-making processes are then beginning to finally converge to a common agreement. A lot of interesting concepts with respect to integrated design [START_REF] Andreasen | Integrated product development[END_REF][START_REF] Tichkiewitch | Specification on integrated design methodology using a multi-view product model[END_REF] and advanced product modelling [START_REF] Krause | Product Modelling[END_REF][START_REF]A multiple perspective product modeling and simulation approach to engineering design support[END_REF] have also provided real advances in design methodology and information modelling. They give opportunity to really set relations as soon as possible among the whole product information related to its entire lifecycle. Nevertheless the process is still based on a "redo until right" action and those concepts could have even more benefits through tackling the following issues 2 :

1. How to integrate detail design information by least commitment on a "partially" defined CAD model in order to be more proactive (vs. reactive). 2. How to work with multiple-CAD models in order to really have multiple solutions with respect to every expert's design intents (manufacturing intent, assembly intent...) ; instead of a unique central CAD model which is the support of the decision making process.

Point 2 has already been introduced in [START_REF] Roucoules | Knowledge intensive approach towards multiple product modelling and geometry emergence to foster cooperative design[END_REF] and nevertheless should be discussed in more detail in the future. The present paper only focuses on points 1

2 Those issues are obviously not exhaustive. They are the ones currently treated by the authors.

which has also been discussed in some references that give the fundamental concepts of the research work:

Form features can be generated from detailed FBS information modelled in multiple-perspectives product modelling. It is then very useful to understand the mapping between product's functions and form features [START_REF] Roucoules | CoDE: a Cooperative Design Environment. A new generation of CAD systems[END_REF].

That approach by least commitment is interesting to foster innovation coming from every expert involved in the design process and not only the "designer" that creates the CAD model [START_REF] Tichkiewitch | Methodology for innovative design[END_REF][START_REF] Meyer | Case study of a MEMS switch supported by a FBS and DFM framework[END_REF]. The key issues treated in this paper are the follow up to those references dealt in point 1. The objective is to provide a DFM approach to support manufacturing information synthesis in the design phase. That information is then used to generate part of the product CAD model.

Design For Manufacturing approach and Design synthesis proposal

In most of papers on Design For Manufacturing [START_REF] Boothroyd | Product design for manufacture and assembly[END_REF][START_REF] Swift | Implementation strategies for DFM[END_REF], the objective was to compare several design solutions with respect to various technical or economical criteria. Those results are very interesting to give a global "cost" seen as a weighted global equation to find the "best" solution (Figure 2). Manufacturing information based on rules or guidelines are then given in order to know how the product could be changed to reach a lower "cost".

Manufacturing information: identification vs. integration

As far as manufacturing information is concerned, the DFM approach has to be based on product-process relationships (ID) that aim at linking a vector of product parameters (PD) and a vector of process parameters (PF). {PDi} = [IDij]*{PFj} It is nevertheless important to distinguish: Identification approaches that aims at modelling the relationships matrix ID. The literature provides a lot of results of identification related to specific manufacturing processes (ex. [START_REF] Zhao | Domain independent shell for DfM and its application to sheet metal forming and injection molding[END_REF]).

Integration approaches that aims at using the relationships for information synthesis in design. The main added value of the proposed DFM approach is actually to identify {PD} vector with respect to the choice of {PF} vector.

Since this research work is part of a larger project regarding fatigue analysis of the designed component the authors actually state that product vector {PD} is composed of four parameters:

Dimensional tolerancing

Form quality

Roughness

Residual stress field Obviously, other parameters also impact the fatigue behaviour (ex. micro-structural effect, micro-cracking, voids...) and should be treated in the future. Authors started by studying residual stresses as it is the main parameters involved in peen forming process. Concerning manufacturing vector {PF}, parameters are depending on the selected manufacturing processes. This paper will present the model of the product-process database in which those parameters are defined and on which the ID matrix is based. Authors then assume the existence of such database since references have already presented ways to identify the ID matrix [START_REF] Cochennec | Mechanical Analysis to identify knowledge for a DFM approach. Application to Shot Peen-forming process[END_REF].

Breakthrough of the DFM synthesis proposal

As presented in 3.1, authors clearly assume that currently CAD modelling is then realised by practising designers thinking of manufacturing as any other information (ex. Assembly, recycling...). It is nevertheless modified in a "redo until right" process once manufacturing simulation is done because of some aspects of the model that could be inappropriate for the process. The breakthrough of the proposal lies on the comodelling of Manufacturing plan and CAD model. It then provides a real information support to "think of manufacturing" in design. That means manufacturing activities have to be assessed concurrently to the product development and the CAD modelling activity. This is totally in coherence with computational synthesis methods as defined in [START_REF] Cagan | A Framework for Computational Design Synthesis: Model and Applications[END_REF]. This paper therefore presents an original DFM Synthesis approach for manufacturing information synthesis in design. The originality is related to the proactive and by least commitment characteristic of the DFM method. It gives some results to manage the data of the whole manufacturing process plan and to integrate those data (i.e. knowledge synthesis approach) to generate the CAD model. The CAD model and process parameters are then jointly defined that totally fits with concurrent and integrated design concepts. The main advantages of that design approach are detailed in the following section considering the fact that:

The CAD model is defined taking into account manufacturing information.

The manufacturing simulations do take into account the history of the whole process plan. Since the CAD model is the input of the simulation, it has not to be seen as virgin of any previous manufacturing operation. On the contrary it has to embed manufacturing parameters and productprocess relationships.

FUNDAMENTS OF THE DFM SYNTHESIS APPROACH

The developed model of integration (i.e. product-process interface model) is based on the research work done by Roucoules and Skander [START_REF] Roucoules | A. Manufacturing process selection and integration in product design. Analysis and synthesis approaches[END_REF]. They showed that taking manufacturing information into account as soon as possible in the design process is of great interest for manufacturing process selection. That indeed supports the emergence of product geometry [START_REF] Roucoules | Knowledge intensive approach towards multiple product modelling and geometry emergence to foster cooperative design[END_REF] and goes towards a limited number of iterations between design and manufacturing decisions; the term "right the first time" is used for such approaches versus the approaches "do until right". Considering that the manufacturing domain can be extended to other product lifecycle phases (e.g. assembly, recycling, dismantling, etc.), the assumption is that the design process should then be centred on multiple-views product modelling and expert analyses instead of being CAD-centred. One of the main limits of that CAD-centred approach remains in the unique product breakdown that does not reflect the design intentions of every expert designers involved in the design group. Figure 3 shows the form features breakdown used to obtain the CAD model of a Wing Cover. Obviously, this breakdown gives the way to draw the entire form but does not represent what should or could be the real manufacturing process plan. It does not make any sense for the engineers in charge of the manufacturing activities. For instance, the three slots are designed using the "extrusion" feature based on a 2D sketch while they should be manufactured as three machining operations. The information structure should therefore include both the manufacturing and form breakdowns (i.e. multiple-views).

Design process by least commitment

Product design process usually starts with functional analysis and goes quite quickly to CAD modelling. This CAD model is defining the topological information on the product but this information is very often defined without "thinking" of the manufacturing plan. Moreover, CAD model does not embed tolerancing, roughness... of the product at all. That limit seems obvious since manufacturing processes are not yet selected. Manufacturing information can then be integrated only after the manufacturing process is selected.

Functional specifications modelling

Nevertheless, a better design process would be to select a manufacturing process earlier and to integrate manufacturing information straight to the right product breakdown. In order to know when the manufacturing process selection can be achieved, the authors propose to model the DFM process (cf. Figure 4) and to really look for manufacturing functions identification.

Those functions are seen as specific required energetic surfaces (i.e. skins) connected by specific energetic skeletons. For further details, this Skin and skeleton model is fully detailed in [12 & 18] and is very similar to the skeleton [START_REF] Muh-Cerng Wu | A skeleton approach for modelling assembly products[END_REF] or "Working Pair Surfaces and Channel" concepts given in [START_REF] Albers | Contact and channel modelling to support early design of technical systems[END_REF].

Manufacturing process selection and information synthesis

From that usage Skin and Skeleton manufacturing expert can select the more adequate process plan that obviously have to respect the initial energetic specifications.

Actually, several manufacturing solutions (i.e. alternatives) can be selected. Manufacturing skins and skeletons are then used to model the product-process interface and to generate the CAD models (or CAD alternatives) with respect to the process plan alternatives. Once again this CAD model is co-created using manufacturing information synthesis by least commitment (i.e. only with manufacturing constraints and no other constraint at this time).

PRODUCT-PROCESS INTERFACE TOWARDS ADVANCED CAD MODELLING LINKED TO MANUFACTURING DATA MANAGEMENT

This section gives the details of the product-process interface used in a DFM synthesis approach. As already introduced the added value lies in:

A CAD model created "right the first time" taking into account manufacturing information An advanced product-process breakdown to manage manufacturing data on entire manufacturing process plan.

Product-process interface modelling

The product-process interface model comes from the assumption that every manufacturing operation is based on a material flow called manufacturing skeleton in the following. This flow (or skeleton) (cf. Figure 6) is then defined with:

Sections defining the initial and final surfaces through which the material is going (i.e. transversal surfaces).

A trajectory on which the material is formed.

An envelope surface which is generated. The link between envelopes generated in the process plan will provide manufacturing skins.

Flow trajectory

Transversal initial surface

Envelope surface

Flow trajectory

Transversal initial surface

Envelope surface

Figure 6: Material flow (i.e. manufacturing skeleton) definition for product-process interface. Based on that flow (called manufacturing skeleton) the material can be added (ex: injection), removed (ex: machining) or deformed (ex: forging, peen forming) to obtain the final part surfaces (called manufacturing skin). In the "added" and "removed" categories those surfaces are equal to the envelope surface. Beyond very good results presented in [START_REF] Skander | Design and manufacturing interface modelling for manufacturing processes selection and knowledge synthesis in design[END_REF] which concern the current results of that approach for nominal aspects, figure 7 gives the novelties of that paper. The new results concern the capabilities of that product-process interface:

To manage product tolerances coming from manufacturing operations. Each level of tolerancing features (dimensional tolerances, form tolerances and roughness) is concerned. Figure 7 shows how those features are integrated in the product-process interface (i.e. manufacturing skeleton) characteristics.

To manage material heterogeneity coming from manufacturing operations. It is also obvious that material flows (cf. above assumption) generate some gradients inside the manufactured product. Those gradients (ex: residual stresses) can, for instance, come from: o Thermal phenomena in the skeleton's sections that come from a cooling phase which is not always homogeneous during casting operations.

o Mechanical deformation on the skeleton's trajectory coming from forming processes (ex: forging, peen forming...).

The example of peen forming is given in the following section which is indeed one of the operations used to manufacture the Wing Cover. This example is also very interesting to show the added value of the approach with respect to manufacturing data management (cf. 5).

Figure 7: Example of product information issued from manufacturing process and managed by the productprocess interface.

Generation of advanced CAD model based on product-process interface

Keeping in mind both the CAD model presented in figure 1 and the "by least commitment" CAD model given in figure 5, the generation of an advanced CAD model which takes into account manufacturing plan is presented.

DFM_Synthesis plateform

This generation of the advanced CAD model is currently supported by a DFM_Synthesis platform that can be seen as a KBE application (Figure 8). The architecture of the software is made of:

A DFM_sythesis software that manages the product-process breakdown and the form features algorithms that generate the CAD model from manufacturing skeleton. The skin and skeleton data model of the KBE application is currently implemented using Open CASCADE Application Framework (OCAF) encapsulated in Microsoft Foundation Class objects and Open CASCADE geometric algorithms.

A product-process database that stores information concerning the ID matrix presented in 3.2.1. This ad-hoc database is so far developed with MS Access. The identification is assumed, in this paper, to be already done. Three ways of identification are however treated: analytical models, experimental data, and numerical simulations.

A Finite Elements Analysis software that is used to assess the product topology (cf. 5.3.1). Indeed, as previously presented, the product-process interface model manages the heterogeneity coming from manufacturing operation that created residual stresses. Those residual stresses have to be treated at each step of the manufacturing process to calculate the elastic equilibrium of the entire part.

The "designers" is then using the DFM_Synthesis application which sends requests to the database in order to constrain the product parameters variability. The design is done "thinking of" manufacturing.

CAD model generation scenario

Authors fully assume that the DFM_Synthesis scenario is processed by a manufacturing expert. There is no automatic process selection at all. Nevertheless, as already-introduced, the CAD model is co-generated once the process is selected. This manufacturing expert is then seen in this approach as a "designer".

The expert therefore:

Realises the first mapping between product requirements and manufacturing processes. Shey matrix (cf. Figure 9) [START_REF] Schey | Introduction to manufacturing Processes[END_REF] is used to map initial partial CAD model (as presented in figure 5) to a manufacturing process list.

Selects the first primary process from this list. An extrusion operation as primary process. Extrusion tolerances are given by the productprocess database and are integrated in the section of the extrusion skeleton that provides extra product information. Radius value of the section are also coming from the database to really take into account manufacturing constraints of the extrusion process (Step 1)

Three machining operations are then proposed by the manufacturing expert as secondary processes.

(

So far the final CAD module seems to be equal to a classic CAD model. However, it has been automatically generated while defining manufacturing plan and constraints. That is the main added value of the DFM approach. Other process plan alternatives could have been selected (cf. figure 11) that would then have generated other CAD alternatives.

A third peen forming operation is therefore defined and is presented in the following to focus on the residual stress. That is also one of the major issues tackled by the approach in order to link product and process information. This cannot be done using current commercial CAD software.

Figure 10: Illustration of the proposed DFM approach (from initial form feature to a complete CAD model).

Product-process interface for product and manufacturing data management

The final structure breakdown created actually gives every product alternatives according to the manufacturing alternatives (cf. breakdown tree in Figure 11). The solution is chosen by the manufacturing expert in the KBE application which then provides the respective CAD solution and respective material characteristics.

The evolution of the CAD model according to each manufacturing operation is then managed using the product-process interface. This approach of manufacturing data management is clearly an addedvalue facing the current commercial CAD software.

Product behaviour management

The first interest of managing product-process interface lies in the mechanical analysis of the product. Product behaviour is indeed strongly related to material characteristics that are most often considered as homogeneous in the global volume of the part. Unfortunately, that homogeneity does not exist at all since most of manufacturing processes generate gradients of material characteristics (ex: forging, casting, shot peening, peen forming...).

Figure 11: OCAF structure for product and manufacturing process information management (example of the extrusion operation among several alternatives).

Based on this KBE application it is then possible to know what is the exact initial state of the product (topology, quality, material heterogeneity) regarding each manufacturing operation. This initial state obviously encapsulates the product behaviour issued from previous manufacturing operations. Indeed each manufacturing interface (i.e. manufacturing skeleton) gives that information.

Let us now talk about the Wing Cover part that should actually have a curved surface in order to fit fluid mechanic specifications. It is then possible to create a CAD model with respect to this curved surface but it does not make any sense without thinking of the manufacturing operation that physically generates that deformation. The proposed DFM_Synthesis approach then provides a great benefit for that. The impact of material change (specifically residual stresses) based on manufacturing processes can be taken into account in the product-process interface (cf. Figure 12) and automatically processed to calculate the product deformation (cf. Figure 13). The Finite Element calculation is based on an elastic analysis of the part and the solver has to reach the global equilibrium of the residual stresses in it.

Since the KBE software manage the entire process plan, manufacturing expert acting as a designer can assess the product deformation with respect to each specific manufacturing operation (ex: extrusion, milling, peen forming) or to the entire process plan. As presented in the figure 13, the main difficulty of the calculation currently remains in "summing up" each residual stresses field from every manufacturing operation.

Assuming that meshing is actually only used to solve the Finite Element Analysis, the authors argue the benefit of using the proposed product-process interface (i.e. manufacturing skeleton) to solve that issue. Manufacturing skeletons are, indeed, not based on meshing and the gradient of information can then be linked to the topological parameters that have a strong physical meaning for manufacturing experts. That is not the case of any meshes that are only dedicated to specific simulation models. Keeping the link between manufacturing parameters and product information is very useful to notify every change concerning product definition. They can therefore be quickly propagated to manufacturing information without processing any new FEA.

The proposed solution based on the presented product-process interface is to link residual stresses field to each manufacturing skeleton. This is represented by topological features linked to manufacturing parameters (cf. figure 12); each skeleton being adequate for each material flow of the given manufacturing operation.

Figure 13: KBE and data management supporting field transfer for product deformation analysis.

Finally, once the entire manufacturing process plan is defined and the respective product information (form + residual stresses field) is generated, all this information can be exchanged with fatigue analysis software; which therefore takes into account the heterogeneity of the part to assess the global product behaviour.

Manufacturing data management for manufacturing process simulation

So far we have presented how product-process interface is used in a DFM approach for CAD modelling taking into account information of material heterogeneity (i.e. residual stresses -cf. figure 7) to better simulate product deformation according to the process plan.

Manufacturing data management via product-process interface modelling is actually also used to simulate each manufacturing operation (extrusion, milling, peen forming).

Once again, process simulations very often assume the initial residual stresses as null whereas it is not the industrial and physical situation.

The proposed product-process interface is then also interesting to "chain" every process simulation. Every simulation can indeed integrate an initial state of residual stresses with respect to the history of previous operations of the process plan (ex: stresses coming from forging, casting…).

CONCLUSION AND RECOMMENDATIONS FOR FUTURE WORK

This paper presents a product-process interface model for a DFM synthesis approach. This model based on material flow modelling with respect to skeleton and skin concepts is first used to integrate manufacturing information as soon as possible in the product design process (i.e. "by least commitment design approach"). This integration strongly leads the CAD modelling and by the way centres the design process on expert designers' knowledge and not on form features any more. The second objective of that interface model is to manage manufacturing information linked to product characteristics (ex: topology, tolerances, residual stresses…). It is then profitable to simulate manufacturing processes taking into account the evolution of the product characteristics with respect to the manufacturing plan. The whole history of each manufacturing operation is then linked to the product definition that is not currently the case in CAD-centred design approach. The main recommendations for future work are:

The application of the KBE software to more complicated academic and industrial case studies.

The implementation of product-process relationships database that could further take into account more manufacturing physical and technological phenomenon that are alreadyknown; for instance vibration, or dynamic behaviours during machining operations.

7.

Figure 1 :

 1 Figure 1: Current engineering design process taking into account advanced design concepts (collaboration, integration, PLM...) of the state of the arts.

Figure 2 :

 2 Figure 2: example of global efficiency assessment in DFX approaches.

Figure 3

 3 Figure 3: a) Physical Wing Coverb) Incoherency between CAD model breakdown and manufacturing plan.

Figure 4 :

 4 Figure 4: The DFM activity model.4.1.2. Manufacturing process selection and information synthesisFrom that usage Skin and Skeleton manufacturing expert can select the more adequate process plan that obviously have to respect the initial energetic specifications.Actually, several manufacturing solutions (i.e. alternatives) can be selected. Manufacturing skins and skeletons are then used to model the product-process interface and to generate the CAD models (or CAD alternatives) with respect to the process plan alternatives. Once again this CAD model is co-created using manufacturing information synthesis by least commitment (i.e. only with manufacturing constraints and no other constraint at this time).5. PRODUCT-PROCESS INTERFACE TOWARDS ADVANCED CAD MODELLING LINKED TO MANUFACTURING DATA MANAGEMENT

Figure 5 :

 5 Figure 5: Energetic skin and skeleton of the Wing Cover and respective form features.

Figure 8 :

 8 Figure 8: Overview of the KBE application.5.2.2. CAD model generation scenarioAuthors fully assume that the DFM_Synthesis scenario is processed by a manufacturing expert. There is no automatic process selection at all. Nevertheless, as already-introduced, the CAD model is co-generated once the process is selected. This manufacturing expert is then seen in this approach as a "designer".

o

  The database therefore returns the process parameters and a list of potential manufacturing skeleton features. Selects one of the manufacturing skeletons and gives values to each parameter (i.e. process vector {PF}). o The database returns the product values (i.e. product vector {PD}) with respect to [ID] matrix.o The open CASCADE algorithms generate the CAD model according to the manufacturing skeleton features.

Figure 9 :

 9 Figure 9: Shey matrix for form features classification.

Figure 10

 10 Figure 10 presents the manufacturing plan with regard to the Wing Cover already shown:

[Figure 12 :

 12 Figure 12: illustration of manufacturing skeleton of a peen forming operation to embed residual stresses information.

Figure 14

 14 Figure14illustrates how product-process interfaces with respect to former manufacturing operation are used as input information in the following simulation of the peen forming process. The simulation is currently processed with Zebulon as Finite Elements solver. The first manufacturing operation consists in extruding material that create the parallelepiped CAD model, attached tolerances and residual stresses as previously presented. The second operation is a peen forming operation. The ball impacts all the upper face and generates plastic deformations. This simulation of the peen forming operation solves the elastic spring-back of the entire part and provides the curve part. The final residual stresses gradient is integrated in the manufacturing interface model to be used for potential further manufacturing operations as milling or drilling for instance.

Figure 14 :

 14 Figure 14: Illustration of transferring residual stresses embedded in skeleton from first manufacturing simulation to the next one.

ACKNOWLEDGMENTS

This research work is partly supported by SNECMA industry. It is part of the MAIA project. The experimental peen forming process on the Wing Cover part has been carried out in the Sisson Lehmann (Wheelabrator group) industry.

8.


Ganggang Niu
email: ganggang.niu@hotmail.com

Shudong Sun
email: sdsun@nwpu.edu.cn

Pascal Lafon
email: pascal.lafon@utt.fr

Lionel Roucoules
email: lionel.roucoules@ensam.eu

A Predictive-reactive Approach for JSP with Uncertain Processing Times

Keywords: Job-shop, Predictive-reactive scheduling, Time-cost tradeoff, Uncertainty 1-Introduction

JSP with discretely controllable processing times (JSP-DCPT) that are perturbed in a turbulent environment is formulated, based on which, a time-cost tradeoff based predictive-reactive scheduling approach is proposed for solving the problem. In the predictive scheduling process, on the basis of a proposed three-step decomposition approach for solving JSP-DCPT, a solution initialization algorithm is presented by incorporating a hybrid algorithm of tabu search and simulated annealing and a fast elitist non-dominated sorting genetic algorithm; in the reactive scheduling process, Pareto-optimal schedules are generated, among which every schedule that is not dominated by any initial schedule can be selected as the responding schedule so as to maintain optimality of the objective that is to minimize both the makespan and the cost. Experimental simulations demonstrate the effectiveness of the proposed approach.

Job-shops with uncertainties are provided with dynamic and complexity. Various kinds of perturbations, such as order alteration, raw materials delay, machine breakdown, processing time fluctuation, and process defects, etc., emerge during the scheduling process. Usually, perturbations cause current schedules suboptimal, non-effective, or even unfeasible. Studies on scheduling with uncertainties can be classified into three classes based on the problem formulation used: completely reactive scheduling, robust scheduling, and predictive-reactive scheduling, among which predictivereactive scheduling is widely used [AL1]. Predictive-reactive scheduling is presented as a two step process. First, a predictive schedule representing the desired behavior of the shop floor over the considered time horizon is generated. Then, the schedule is modified during execution in response to unexpected disruptions. The two main questions for predictive-reactive scheduling are when to initiate a rescheduling action and what that rescheduling action should be. While in this paper, we focus primarily on the latter. Several different scheduling approaches encountered at a specific rescheduling point have been presented. In the match-up scheduling approach (see [AG1] for e.g.), the objective is for the realized schedule to return to the predictive schedule within a certain time after the disruption occurring. This approach will clearly yield high-quality schedules if there is sufficient idle time in the original predictive schedules. A considerable number of researchers have viewed the rescheduling as that of selecting an appropriate action from among a suite of options in the face of different disruptions (see [JE1] for e.g.), which is essentially the rule-based heuristic procedure. One tool for this has been case-based reasoning (see [O1] for e.g.). Since measures of both the schedule performance that must be maintained and the disruption caused by rescheduling are needed to be taken into account, which automatically leads to the formulation of the rescheduling problem as a multiobjective scheduling problem, a naturally adopted approach is the multi-objective optimization approach, which is to generate Pareto-optimal schedules. [TU1] considered a static rescheduling problem in which a number of new jobs must be inserted into an existing schedule so as to minimize the total completion time of the new jobs without causing existing jobs to miss their deadlines. [AA1] investigated the problem of rescheduling identical parallel machines with disruptions and provide heuristic algorithms to minimize the number of rescheduled jobs subject to optimizing the total completion time of all jobs in the system. In real-life job-shops, the operation processing time could be controllable by allocating resources, such as additional money, overtime, energy, fuel, catalysts, subcontracting, or additional manpower, to the operation. Therefore the operation processing time can have a finite number of possible durations [SS1]. JSP with discretely controllable processing times (JSP-DCPT) is a generalization of JSP, to which operation processing times can be reduced by allocating additional resource that is limited and discretely divisible. In this paper, the discretely controllable processing time is taken into account, and a time-cost tradeoff based predictive-reactive scheduling approach is investigated in order to deal with the processing time uncertainty in job-shops. The remainder of this paper is organized as follows: Section 2 gives the formulation of JSP-DCPT with processing time perturbations. In Section 3, a time-cost tradeoff based predictive-reactive scheduling approach is proposed for solving the problem. Experimental simulations are implemented in Section 4. Finally in Section 5, conclusions are presented.

2-Formulation

A feasible solution of JSP-DCPT is specified by a JSP schedule that indicates job sequences on each machine and a mode selection vector that ascertains the mode selection for processing each operation. In order to formulate JSP-DCPT with processing time perturbations, notations used in this paper are given as follows:

O , ij ij ij ij ij μμ εμμ εμ ⎡ ⎤ ∈- + ⎣ ⎦ , where [ ] 0,1 ε ∈ .
The objective is to minimize both the time and the cost criterion, that is to minimize the bicriteria (,) T σ δ and

ε ≥+ = =≠ …… (3) [ ] ,, ,, ,1 , 2 , (, ) , ,
for all 1, ; 1, ; 1, 2, , 0, 1 , and 0

ij ij ij ij ij ij ij ij x ij x ij x ij x ij ij ij ij ij l tx in jm xl εμε μ μ ε μ ε μμ μ ⎡ ⎤ ∈- + ⎣ ⎦ == =∈ >> > ≥ …… … (4)
Equation (1) indicates that the objective is to minimize both the makespan (that is max( ( , ))

3-Approach

Predictive scheduling

The fact that a feasible solution of JSP-DCPT is specified by a JSP schedule and a mode selection vector inspires a decomposition approach for solving JSP-DCPT. JSP-DCPT, which is denoted by , can be solved by using a three-step decomposition approach. P Firstly, all JSP schedules are obtained by solving the corresponding JSP (denoted by

) that is transformed from the JSP-DCPT problem by setting all operations in the most crash mode. Secondly, for each JSP schedule Step2: Ascertain one solution from the initial solutions, and implement the solution.

Step3: When perturbations occur, decide whether to respond to perturbations or not.

Step4: In the case when perturbations are responded, execute reactive scheduling:

Step4.1: Ascertain all operations waiting to be processed.

Step4.2: Apply algorithm 1 to generate the new Pareto-optimal solution collection (denoted by ) for JSP-DCPT scheduling.

2

C

Step4.3: Seek in solutions that are not dominated by any solution in ; all sought solutions consist collection .

2

C 1 C 3 C
Step4.4: if 3 0 C > , then return ; else, go to Step5.

3

C

Step5: Procedure terminates. Any solution in the returned collection can be selected as the new schedule that could keep the optimality of objectives in the face of processing time perturbations.

3

C

In order to illustrate the proposed predictive-reactive scheduling approach, an illustrative case is given as follows: Let 1 s , 2 s , 3 s , and 4 s denote the initial Pareto-optimal JSP-DCPT tradeoffs. On a time-cost phase plane as shown in Fig. 2,points , , , and correspond to 1

P 2 P 3 P 4 P 1 s , 2 s , 3 s
and 4 s , respectively. In addition, it is assumed that the tradeoff selected and applied to the process control is 3 s . After processing time perturbations occur, the new Paretooptimal JSP-DCPT tradeoffs are 1 s ′ , 2 s ′ , 3 s ′ and 4 s ′ , which is separately denoted by 1 P ′ , , , and 2 P ′ In Figure 1, 11 PP ′ and , hence , , s ′ can be selected as the new tradeoff that is to be implemented in order to maintain optimality of the objective that is to minimize both the makespan and the cost.

4-Simulation study

To simplify a JSP-DCPT instance for simulation, it is assumed that each operation can only be processed in two modes, namely the normal mode (in such case, 1 ij x = ) and the most crash mode (in such case,

). For operation , the nominal operation processing time in the normal mode (denoted by

2 ij x = ij O ,1 ij
μ ) is twice as much as that in the most crash mode (denoted by ,2 ij μ ). In addition, the compression cost is assumed to be equal to the time shortened. and are the compression costs for in the normal mode and in the most crash mode, respectively. The processing data for the JSP-DCPT instance is given in Table 1.

μ , ,2 ij μ ), ( , ) ,1 ij c ,2 ij c J1
M1,(6,3),(0,3) M2,(4,2),(0,2) M3,(10,5),(0,5) J2 M1,(6,3),(0,3) M3,(10,5),(0,5) M2,(2,1),(0,1) J3 M2,(4,2),(0,2) M1,(10,5),(0,5) M3,(6,3),(0,3)

In addition, the actual processing time of an operation with perturbations varies randomly in a given range. According to Equation (4) in Section 2, the actual processing time of processed in the normal and the most crash mode is expressed by

ij O (1, ) ij t ε and (2, ) ij t ε , respectively. (1, ) ij t ε ∈ ,1 ,1 ,1 ,1 , ij ij ij ij με μ με μ ⎡ -+ ⎣ ⎤ ⎦ , and (2, ) ij t ε ∈ , where ,2 ,2 ,2 ,2
,

ij ij ij ij με μ με μ ⎡⎤ -+ ⎣⎦ [ ] 0,1 ε ∈ .
To verify the effectiveness of the proposed predictive-reactive scheduling approach under various uncertainty degrees, 10 groups of simulations are implemented, and for each group ε is set to be a different value from 10% to 100%. Each group includes 50 simulations, during which processing time perturbations occur. The computational results for the 50 simulations of each of the 10 groups are given in Table 2. Notes : ε is the uncertainty degree ; is the number of initial Pareto-optimal tradeoffs; is the number of tradeoffs that can be implemented in order to maintain the optimality of the objective that is to minimize both the makespan and the cost. approach is proposed for solving the problem. Simulations for the illustrative JSP-DCPT case demonstrate the effectiveness of the proposed approach, which hence could be an approach of potentiality for dealing with other kinds of uncertainties in job-shops.

6-Acknowledgments

The paper is supported by the Asia-Link project funded by the European Commission (CN/ASIA-LINK/024 (109093)), the National Natural Science Foundation of China (50705076, 50705077), and the National Hi-Tech R&D Program of China (2007AA04Z187).

  uncertain degree of processing time is defined by its variety range, for example, if ij μ is the nominal processing time of the operation , then the actual processing time can by expressed by ij

  only be a value from a variety range that is determined by the nominal value and the uncertain degree, ij ij x μ ε .

PP

  Let A denote the collection of all JSP schedules that are obtained by solving the corresponding JSP problem PI . A = { | 1, 2,..., ,..., the size of collection A . i t σ is the makespan for () i PII σ at the tradeoff where all operations are set in the most crash mode. On the basis of the proposed three-step decomposition approach for solving JSP-DCPT, a solution initialization algorithm for predictive scheduling is presented by incorporating a hybrid algorithm of tabu search and simulated annealing (TSSA, see [ZL2]) and a fast elitist non-dominated sorting genetic algorithm (NSGA-II, see [DA1]), so as to effectively and efficiently solve the two kinds of sub problems (i.e., JSPs and the discrete time-cost tradeoff problems) decomposed from JSP-DCPT. Algorithm 1. Solution initialization for predictive scheduling Step1: For JSP-DCPT, set each operation in the most crash mode and solve the corresponding JSP problem PI by using TSSA. A collection A = { } v | 1, 2,...,

  Solve discrete time-cost tradeoff sub-problem () i PII σ by using NSGA-II. All dominant tradeoffs derived from solving () i PII σ are then added to collection . B Step3.3: Sort B in a descending order by using the point dominance defined in definition 1. Step3.4: Truncate all non-dominant tradeoffs in collection . B Until . iv = Step4: Return B , which is a collection of all Pareto-optimal solutions of JSP-DCPT.

3. 2

 2 Predictive-reactive schedulingA time-cost tradeoff based predictive-reactive scheduling approach for dealing with processing time perturbations in jobshops is presented as follows: Procedure 1. Predictive-reactive scheduling Step1: Predictive scheduling: apply algorithm 1 to get the initial Pareto-optimal solution collection (denoted by ) for JSP-DCPT scheduling. 1C

PFigure 1 :

 1 Figure 1: Illustrative figure to demonstrate the predictivereactive scheduling approach.

  JSP-DCPT with processing time perturbations is formulated. The time-cost tradeoff based predictive-reactive scheduling

Table 1 : The data for the illustrative JSP-DCPT

 1

	Job	Machine, ( ,1 ij

Table 2 : Computational results for the simulation

 2

	ε	1 n	Average	2 n Best	Worst
	10%	10	2.8	3	1
	20%	11	4.6	5	2
	30%	13	3.8	4	2
	40%	12	3.9	4	3
	50%	15	5.7	6	3
	60%	16	4.8	5	2
	70%	17	3.9	4	2
	80%	16	4.6	5	3
	90%	18	5.7	6	4
	100%	18	4.8	5	2