Mohand Lounes Bentaha

Olga Battaïa
email: battaia@emse.fr

Alexandre Dolgui
email: dolgui@emse.fr

Chance Constrained Programming Model for Stochastic Profit-Oriented Disassembly Line Balancing in the Presence of Hazardous Parts

Keywords: Sustainable Manufacturing, Product Recovery, Disassembly, Line Design, Cone and Chance Constrained Programming, Interiorpoint Algorithm

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Disassembly lines play a key role in the selective separation of parts and materials of EOL products. The success of the product recovery depends partially on the economical efficiency of such lines. However, their design presents a complex optimization problem requiring adapted mathematical tools to obtain efficient solutions.

A first study on disassembly line considering task failures was presented by Güngör and Gupta [START_REF] Güngör | A solution approach to the disassembly line balancing problem in the presence of task failures[END_REF]. Later, the deterministic version of the Disassembly Line Balancing Problem (DLBP) was studied in [START_REF] Mcgovern | Combinatorial optimization analysis of the unary NP-complete disassembly line balancing problem[END_REF][START_REF] Mcgovern | Ant colony optimization for disassembly sequencing with multiple objectives[END_REF][START_REF] Mcgovern | A balancing method and genetic algorithm for disassembly line balancing[END_REF][START_REF] Mcgovern | The Disassembly Line, Balancing and Modeling[END_REF]. Several performance criteria were considered including minimization of the number of stations needed and variation in idle times between the stations of the line. The following solution methods were developed and compared: exhaustive search, genetic algorithm, ant colony metaheuristics, a greedy algorithm, greedy/hill-climbing and greedy/2optimal hybrid heuristics. Altekin et al. [START_REF] Altekin | Profit-oriented disassembly line balancing[END_REF] defined and solved the profit-oriented DLBP. The problem was modeled via a mixed-integer programming formulation and its solution simultaneously determined the number of stations and cycle time along with the assignment of the tasks to the stations. Upper and lower bounding schemes were also developed. Koc et al. [START_REF] Koc | Two exact formulations for disassembly line balancing problems with task precedence diagram construction using an AND/OR graph[END_REF] proposed two exact (MIP and DP) formulations to solve DLBP with the objective of minimizing the number of stations. They used an AND/OR graph to model EOL product data and showed that the use of such a graph allowed obtaining better solutions in comparison with a single precedence diagram. Altekin and Akkan [START_REF] Altekin | Task-failure-driven rebalancing of disassembly lines[END_REF] considered task-failure driven rebalancing of disassembly lines. A mixed-integer programming based predictive-reactive approach was proposed. In the first step, a predictive balance was created and then, in the second step, given a task failure, the tasks of the disassembled product with that task failure were reselected and re-assigned to the stations. Agrawal and Tiwari [START_REF] Agrawal | A collaborative ant colony algorithm to stochastic mixed-model U-shaped disassembly line balancing and sequencing problem[END_REF] considered the case of a mixed-model U-shaped disassembly line with stochastic task times. They proposed a collaborative ant colony optimization technique to simultaneously determine the sequencing of the models and assign the tasks to the stations.

The literature exposed above shows that no adequate mathematical model taking into account simultaneously the stochasticity of disassembly task times, the partial disassembly and maximizing the profit produced by the line can be found. To fill this gap, this paper aims to provide such a model where some of disassembled parts are considered hazardous and require a particular treatment incurring a supplementary cost. An adapted solution method to find efficient design solutions is presented. The paper is organized as follows. Section 2 presents the problem formulation. Section 3 describes the solution method. Section 4 analyzes the numerical experiments. Conclusions are given in Section 5.

Problem Statement

The SP-DLBP aims to assign a set of disassembly tasks, I = {1, 2, . . . , N}, N ∈ N * to an ordered sequence of workstations, J = {1, 2, . . . , M}, M ∈ N * under precedence relationships constraints among tasks. Cycle time (C 0 > 0) limitation at each station is satisfied with a certain probability level fixed by the decision maker. Task times are assumed mutually independent random variables with known normal probability distributions, i.e. t i ( ξ) N (µ i , σ i ), t i ( ξ) > 0, i ∈ I; the random variables are modeled by a random vector ξ = ( t1 , t2 , . . . , tN ) varying over a set Ξ ⊂ R N + given a probability space (Ξ, F, P ) introduced by ξ. A disassembly task i ∈ H ⊂ I is called hazardous if its execution generates a hazardous subassembly or component. All possible alternatives for disassembly process and precedence relationships among tasks and subassemblies are modeled by an AND/OR graph [START_REF] Bentaha | A stochastic formulation of the disassembly line balancing problem[END_REF]. An example for such a graph is given in Fig. 1. To simplify the graph, without information loss, subassemblies with one component are not shown. Each subassembly of single type EOL product to be disassembled is represented by a node A k , k ∈ K = {0, 1, . . . , K}, K ∈ N in the graph and each disassembly task gives a node B i , i ∈ I. Two types of arcs define the precedence relations between the subassemblies and tasks: AND-type and OR-type arcs. For instance, if a disassembly task generates two sub-assemblies, or more, then it is related to these subassemblies by AND-type arcs. If, for a given subassembly, one or more disassembly tasks can be performed, but only one must be selected, this subassembly is related to these disassembly tasks by OR-type arcs. In order to consider the case of partial disassembly, where the product is not necessarily disassembled till obtaining single parts, a dummy task s is introduced into the precedence graph as a sink node, as illustrated in Fig. 1. Since the case of partial disassembly is considered, not all existing tasks have to be assigned. The level of the disassembly depends on the profit generated by the corresponding line. The recycling or reuse of certain parts or subassemblies bring its benefit while the line cost is considered as a negative revenue. This cost includes two components: the cost of workstations used and additional cost entailed by the treatment of hazardous parts. For the problem defined, the following stochastic Mixed Integer Program with Joined Probabilistic Constraints (MIPJPC) has been developed. C h : Additional cost for stations handling hazardous parts, C h > 0;

P k : Predecessors index set of A k , k ∈ K, i.e. P k = {i| B i precedes A k }; S k : Successors index set of A k , k ∈ K, S k = {i| A k precedes B i }.
Decision Variables YES

x ij =     
1, if disassembly task B i is assigned to workstation j; 0, otherwise.

z j = C 0 , if x sj = 1; 0, otherwise. x sj =     
1, if dummy task s is assigned to workstation j; 0, otherwise.

h j =     
1, if a hazardous task is assigned to workstation j; 0, otherwise.

Stochastic Program max    i∈I j∈J ℓ∈Li r ℓ • x ij -F c • j∈J j • z j -C 0 C h • j∈J h j    (MIPJPC) s.t. z j = C 0 • x sj , ∀j ∈ J (1)
i∈S0 j∈J

x ij = 1 (2) j∈J x ij 1, ∀i ∈ I (3)
i∈S k j∈J x ij i∈P k j∈J x ij , ∀k ∈ K\{0} (4) i∈S k x iv i∈P k v j=1
x ij , ∀k ∈ K\{0}, ∀v ∈ J (5)

j∈J x sj = 1 (6) j∈J j • x ij j∈J j • x sj , ∀i ∈ I (7) h j x ij , ∀j ∈ J, ∀i ∈ H (8)
P i∈I t i ( ξ) • x ij C 0 , ∀j ∈ J 1 -α (9)
z j 0, ∀j ∈ J (10)

x sj , x ij , h j ∈ {0, 1}, ∀i ∈ I, ∀j ∈ J (11)
The terms of the objective function represent respectively the earned profit of retrieved parts, the cost of operating workstations and the additional cost for handling hazardous parts. If the dummy task s is assigned to workstation j, which defines the number of processed stations, then j∈J j • z j = j • C 0 and workstations operating cost becomes j • (F c • C 0 ). Constraints (1) ensure the value of z j to be C 0 when the dummy task s is assigned to station j. Constraint (2) imposes the selection of only one disassembly task (OR-successor) to begin the disassembly process. Constraint set [START_REF] Altekin | Profit-oriented disassembly line balancing[END_REF] indicates that a task is to be assigned to at most one workstation. Constraints (4) ensure that only one ORsuccessor is selected. Constraint set (5) defines the precedence relations among tasks. Constraint (6) imposes the assignment of the dummy task s to one station. Constraints [START_REF] Koc | Two exact formulations for disassembly line balancing problems with task precedence diagram construction using an AND/OR graph[END_REF] ensure that all the disassembly tasks are assigned to lower or equal-indexed workstations than the one to which s is assigned. Constraints ( 8) ensure the value of h j to be 1 if at least one hazardous task is assigned to a workstation j. Constraints (9) enforce the station operating time to remain within the cycle time, for all opened workstations, with a probability at least (1α) determined by the decision maker. Finally, sets ( 10)-( 11) represent the trivial constraints.

Solution Method

Let (1α) = ᾱ. Sine disassembly task times are assumed mutually independent random variables with known normal probability distributions, then:

P i∈I t i ( ξ) • x ij C 0 , ∀j ∈ J ᾱ ⇐⇒ j∈J P i∈I t i ( ξ) • x ij C 0 ᾱ ⇐⇒ j∈J P i∈I t i ( ξ) • x ij C 0 ᾱ1= j∈J yj , y j 0, ∀j ∈ J ⇐⇒ P i∈I t i ( ξ) • x ij C 0 ᾱyj , ∀j ∈ J, j∈J y j = 1. P i∈I t i ( ξ) • x ij C 0 ᾱyj , ∀j ∈ J ⇐⇒ P i∈I t i ( ξ) • x ij -i∈I µ i • x ij i∈I σ 2 i • x ij C 0 -i∈I µ i • x ij i∈I σ 2 i • x ij ᾱyj ⇐⇒ P Z j C 0 -i∈I µ i • x ij i∈I σ 2 i • x ij ᾱyj , Z j N (0, 1), ∀j ∈ J ⇐⇒ i∈I µ i • x ij + Φ -1 ᾱyj • i∈I σ 2 i • x ij C 0 , ∀j ∈ J ( 12
)
Let v, w ∈ R×R l-1 ; the unit second-order convex cone of dimension l is defined

as Q l = w v v w
where • refers to the standard Euclidean norm.

Since α < 50%, which is justified by the fact that α represents the risk and mostly α 10%, we have Φ -1 ᾱyj > 0, and since x ij ∈ {0, 1} ⇐⇒ x 2 ij ∈ {0, 1}, then, inequality ( 12) is a second-order cone constraint of dimension l = N + 1:

i∈I µ i • x ij + Φ -1 ᾱyj • i∈I σ 2 i • x ij C 0 , ∀j ∈ J ⇐⇒ µ T • x j + Φ -1 ᾱyj • Σ 1 2 • x j C 0 , ∀j ∈ J ⇐⇒ Σ 1 2 • x j 1 Φ -1 ᾱyj • C 0 -µ T • x j , ∀j ∈ J ⇐⇒    Σ 1 2 -µ T Φ -1 ᾱy j x j + 0 C0 Φ -1 ᾱy j    ∈ Q N+1 , ∀j ∈ J where µ = (µ 1 , . . . , µ N ), x j = (x 1j , . . . , x Nj ) T , ∀j ∈ J, Σ 1 2 =    σ 1 0 . . . 0 σ N   is a
diagonal matrix and Φ -1 (•) is the inverse of the standard normal cumulative distribution function Φ(•). Let x be a vector of the decision variables x ij , x sj , h j , z j and X = {x| constraints (1) -( 8), ( 10) -(11) are satisfied}. The Second Order Cone Mixed Integer Program given below represents an equivalent version of problem (MIPJPC) [START_REF] Atamtürk | Conic mixed-integer rounding cuts[END_REF].

max

   i∈I j∈J l∈Li r l • x ij -F c • j∈J j • z j -C 0 C h • j∈J h j    (SOCMIP) s.t.
x ∈ X v j 1

Φ -1 ᾱ 1 M • C 0 -µ T • x j , ∀j ∈ J w ij σ i • x ij , ∀i ∈ I, ∀j ∈ J v j w j , ∀j ∈ J v j 0, w ij 0, ∀i ∈ I, ∀j ∈ J
where v j , w ij , ∀i ∈ I, ∀j ∈ J are intermediate variables, w j = (w 1j , . . . , w Nj ) T , ∀j ∈ J. We consider the case where cycle time constraint is to be satisfied with the same probability for each station of the line, i.e. y j = 1 |J| = 1 M , ∀j ∈ J. The resulted (SOCMIP) is then solved using the interior point algorithm [START_REF] Nesterov | Interior-Point Polynomial Algorithms in Convex Programming[END_REF] of CPLEX 12.4.

Numerical Results

The program (SOCMIP) was implemented in Microsoft Visual C++ 2008 and ILOG CPLEX 12.4 was used to solve the model on a PC with Intel(R) Core(TM) i5-2400 CPU 3.10 GHz and 8Go RAM. It has been applied to the problem instance illustrated in Fig. 1 and to 5 available in the literature benchmark problems containing process alternatives for disassembly. The names of the problem instances were respectively composed of the first letters of authors' names and year of publication, i.e. BBD12 [START_REF] Bentaha | A stochastic formulation of the disassembly line balancing problem[END_REF], KSE09 [START_REF] Koc | Two exact formulations for disassembly line balancing problems with task precedence diagram construction using an AND/OR graph[END_REF], L99a and L99b from [START_REF] Lambert | Linear programming in disassembly/clustering sequence generation[END_REF], MJKL11 [START_REF] Ma | Disassembly process planning algorithms for end-of-life product recovery and environmentally conscious disposal[END_REF]. BBD13 corresponds to the piston and connecting rod product instance, see Fig. 1. The input data for each problem instance is given in Table 1.

The columns 'AND-relations' report the number of disassembly tasks with no successor in column 0, with one AND-type arc in column 1, and with two ANDtype arcs in column 2, column 'arcs' gives the total number of AND-type and OR-type arcs.

The interior-point algorithm of CPLEX was applied to each instance for α = 10%. Cost of operating workstations F c was fixed to 5 and cost for stations handling hazardous parts C h = 3 for all instances. The results obtained are also presented in Table 1 where columns 'obj., tasks, stat., H-stat., CPU time' report respectively the optimal profit of the line, the number of selected tasks, the number of opened stations, the number of hazardous stations and solution time in seconds. All instances were solved in less than 1 second.

Conclusion

In this paper, partial profit-oriented disassembly line balancing problem in the presence of hazardous parts was studied under uncertainty. A second-order cone mixed integer program was developed. Disassembly task times were assumed mutually independent random variables with known normal probability distributions, where cycle time constraints were to be jointly satisfied with at least a probability level fixed by the decision maker. To solve the problem, the interior point algorithm and CPLEX solver were used. The solution method was evaluated on a set of 6 problem instances taken from the literature. All instances were solved in less than 1 second.

Our future objective is to develop an exact solution algorithm for the problem considered based on branch & cut method and compare it to interior point CPLEX algorithm.

Fig. 1 .

 1 Fig. 1. AND/OR graph of the piston and connecting rod

Parameters H :

 : Hazardous disassembly tasks' index set; L: Parts' index set: L = {1, 2, . . . , L}, L ∈ N * ; r ℓ : Revenue generated by part ℓ, ℓ ∈ L; L i : Set of retrieved parts by the execution of disassembly task B i , i ∈ I; F c : Fixed cost per unit time of operating workstations, F c > 0;

Table 1 .

 1 Problem instances and obtained results

		N K, L arcs	AND-relations M C0 obj. tasks stat. H-stat. CPU time 0 1 2
	MJKL11 37 22, 33 68	4	27 6 3 40 20	7	3	1	0.50
	L99a	30 18, 28 56	2	26 2 3 50 75	7	3	1	0.03
	BBD13 25 11, 27 49	4	18 3 2 120 640	3	2	0	0.05
	KSE09 23 13, 20 47	4	5 14 2 20 53	4	2	0	0.05
	L99b	20 13, 23 40	5	9	6 3 10 72	7	3	1	0.22
	BBD12 10 5, 12 18	3	6	1 2 0.51 18.39 2	2	1	0.05


Fatme Makssoud
email: makssoud@emse.fr

Olga Battaïa
email: battaia@emse.fr

Alexandre Dolgui
email: dolgui@emse.fr

An exact method for the assembly line re-balancing problem

Keywords:

In this paper, we propose a mathematical optimisation model to solve the simple assembly line rebalancing problem. This problem arises when an existing assembly line has to be rebalanced in order to meet new production requirements. In this paper, a Mixed Integer Program is proposed for solving this problem with the objective to minimize the number of changes in the initial line. The computational experiments show the efficacy of the proposed method.

Introduction and related literature

The assembly line consists of a number of consecutive workstations. Products are assembled by means of the successive execution of tasks in workstations as shown in Figure 1. The most known formulation of the Simple Assembly Line Balancing Problem (SALBP) aims to find a minimal number of workstations required for assigning a given set V of tasks taking into account precedence and cycle time constraints. The precedence constraints are given by a directed acyclic graph G = (V, E) over this set of tasks, where each edge (i, j) ∈ E indicates that task i is an immediate predecessor of task j and therefore has to be assigned to a prior or the same workstation as task j.

Each task j ∈ V is also characterized by its time, t j . The sum of task times of the tasks assigned to the same workstation has to not exceed a given cycle time denoted by T 0 . This problem is known to be NP-hard. Even if it was introduced in the literature almost 60 years ago [START_REF] Salveson | The assembly line balancing problem[END_REF], many recent studies still address it [START_REF] Battaïa | A taxonomy of line balancing problems and their solution approaches[END_REF][START_REF] Bautista | A dynamic programming based heuristic for the assembly line balancing problem[END_REF][START_REF] Kilincci | Firing sequences backward algorithm for simple assembly line balancing problem of type 1[END_REF][START_REF] Pastor | An improved mathematical program to solve the simple assembly line balancing problem[END_REF][START_REF] Sewell | A branch, bound, and remember algorithm for the simple assembly line balancing problem[END_REF].

However, because of frequent changes in the product characteristics and demand, the problem that arises more frequently than initial line balancing problem is how to reassign the set of the tasks in order to meet new production requirements while minimize the number of modifications to be done in the initial line. We call this problem Simple Assembly Line Rebalancing Problem (SALReBP) and propose an exact method to solve it. Indeed, until now rebalancing problems for production lines have been principally addressed by means of approximate methods. Heuristics and genetic algorithms were used for solving stochastic assembly line rebalancing problem by Gamberini et al. [START_REF] Gamberini | A new multi-objective heuristic algorithm for solving the stochastic assembly line re-balancing problem[END_REF][START_REF] Gamberini | A multiple singlepass heuristic algorithm solving the stochastic assembly line rebalancing problem[END_REF]. For the case of a vehicle assembly line, three heuristic methods have been developed by Grangeon et al. [START_REF] Grangeon | Heuristics for the re-balancing of a vehicle assembly line[END_REF]. A COMSOAL based heuristic for re-balancing of assembly lines that determines a fixed task sequence for a number of different cycle times was proposed by Agpak [START_REF] Agpak | An approach to find task sequence for re-balancing of assembly lines[END_REF].

The remainder of this paper is organized as follows. A formal definition of the SALReBP is presented in the next section. The linearization of the model proposed is described in Section 3. An illustrative example is given in Section 4. A computational study is presented in Section 5 and concluding remarks are given in Section 6.

Formal problem definition and mathematical model

In this section, we present a formal definition of the SALReBP. As mentioned before, we denote by T 0 the cycle time and by m the number of workstations. Let V be the set of tasks to be allocated.

The following notations are used in our mathematical model:

-Indices: i, j for tasks, k for workstations.

-Parameters:

V the new set of tasks, j ∈ V, t j the processing time of task j, j ∈ V , M = {1, 2, ..., m} is the set of workstations in the existing line, L = {1, 2, ..., l} is the set of workstations in the new line, where l is an upper bound on the number of workstations for new line. Q(j) is the interval of workstations in the upgraded line, where task j ∈ V can be assigned. It is calculated using the precedence constraints.

-Decision variables:

x * jk = 1 if task j ∈ V * ⊂ V is assigned to workstation k in the initial configuration, 0 otherwise. Set V * contains tasks j such that for x * jk = 1, k ∈ Q(j); x * jk = 0 for all k > m, constraint 7 in model ( 1) -( 7); y jk = 1 if task j ∈ ∩V is assigned to workstation k in the new solution, 0 otherwise; y jk = 0 for all k / ∈ Q(j), constraint 6 in model ( 1) -( 7).

The following model is used for the presented assembly line rebalancing problem. The objective function (1) consists in minimizing changes in the existing task assignment. Constraint (2) guarantees that every task j is assigned to one and only one workstation. Constraint (3) imposes the precedence constraints. Constraint (4) ensures that the total duration of the tasks assigned to workstation j does not exceed cycle time. Constraint (5) deals with the impossibility of executing certain tasks at the same workstation. Constraint [START_REF] Grangeon | Heuristics for the re-balancing of a vehicle assembly line[END_REF] ensures that the variables outside intervals Q(j) are set to 0.

M inimize

j∈V * k∈L | x * jk -y jk | (1) k∈Q(j)
y jk = 1, ∀j ∈ V (2) k∈L ky ik ≤ k∈L ky jk , ∀(i, j) ∈ A (3)
j∈V t j y jk ≤ T 0 , ∀k ∈ L (4)

y ik + y jk ≤ 1, ∀{i, j} ∈ E, ∀k ∈ L (5)
y jk = 0, ∀j ∈ V, ∀k / ∈ Q(j) (6)
x

* jk = 0, ∀j ∈ V, ∀k > m (7)
3 Linearization of the model

In the following, we propose a method to linearize the proposed model.

Lemma 1 Let x, y, z ∈ {0, 1}. Then the following logical expression if x = 1 and y =1, then z =1 can be modeled as follows:

x + y ≤ z + 1.

Lemma 2 Let x, y ∈ {0, 1}. Then the following non-linear expression z :=| xy | can be linearized using the following inequalities

x + y ≤ (1 -z) + 1, x + (1 -y) ≤ z + 1, (1 -x) + y ≤ z + 1, (1 -x) + (1 -y) ≤ (1 -z) + 1,
It is evident to see that z ∈ {0, 1}. Moreover, only four following cases are possible: if x = 1 and y = 1; then z = 0, if x = 1 and y = 0; then z = 1, if x = 0 and y = 1; then z = 1, if x = 0 and y = 0; then z = 0.

Applying for these four cases Lemma 1, we obtain the necessary inequalities. To linearize the problem (1) -( 5), we introduce a new variable z jk :=| x * jky jk |. Using Lemma 2, we obtain:

M inimize j∈V * k∈L z jk (8)
k∈Q(j)

y jk = 1, ∀j ∈ V (9) k∈L ky ik ≤ k∈L ky jk , ∀(i, j) ∈ A ( 10
) j∈V t j y jk ≤ T 0 , ∀k ∈ L (11)
y ik + y jk ≤ 1, ∀{i, j} ∈ E, ∀k ∈ L (12)
y jk = 0, ∀j ∈ V, ∀k / ∈ Q(j) (13)
x * jk = 0, ∀j ∈ V, ∀k > m (14)

x * jk + y jk ≤ (1 -z jk ) + 1, ∀j ∈ V, ∀k ∈ L (15) x * jk + (1 -y jk ) ≤ z jk + 1, ∀j ∈ V, ∀k ∈ L (16) (1 -x * jk ) + y jk ≤ z jk + 1, ∀j ∈ V, ∀k ∈ L (17) (1 -x * jk ) + (1 -y jk ) ≤ (1 -z jk ) + 1, ∀j ∈ V, ∀k ∈ L (18)

Illustrative example

Let us consider the following case study. The initial assembly line is given in Figure 2. This line has to be rebalanced for a modified product where the following tasks {14, 19, 23, 28, 29} have been deleted and new tasks {31, 32, 33, 34, 35} have been introduced. The task times of all tasks are reported in Table 1. The precedence constraints to be respected are given in Figure 3. Exclusion The optimal solution was obtained in 0.36 second and consists to reassign the following tasks: {2, 4, 10, 12, 21, 31, 32, 33, 34, 35}, they are shown in bold in Figure 4 that illustrates the rebalanced line.

Computational results

The proposed method was evaluated on a dataset that consists of 42 instance problems of 25 tasks each. For each initial problem, 3 versions of the modified product were generated: (1) by changing 25% of tasks (five tasks deleted and five added); (2) by changing 50% of tasks (five tasks deleted and eight added);

(3) by changing 75% of tasks (five tasks deleted and fourteen added). The computational results are respectively presented in Tables 234, where the values of the objective function indicating how many tasks were reassigned and the solution time are given. Experiments were carried out on PC Intel(R), 2.20 GHz, with 8 Go RAM. The model was coded in C++ with ILOG CPLEX 12.4.

Conclusion

The problem of assembly line rebalancing was addressed. We have presented a mathematical optimization model that aims at minimizing the number of changes in the initial line. On the basis of an industrial case study, it was shown that the model proposed can be successfully applied in real world environment. The experimentation revealed that the model is capable of solving problems with up to 40 tasks in the precedence diagram.

The further research will undertake a more comprehensive computational experiment in order to evaluate the problem's size limit for which the exact method

Fig. 1 .

 1 Fig. 1. Assembly line

  constraints are : {{1, 4}, {1, 17}, {1, 20}, {2, 11}, {3, 24}, {3, 7}, {4, 15}, {5, 22}, {6, 24}, {8, 21}, {9, 22}, {10, 15}, {11, 31}, {12, 13}, {12, 20}, {13, 28}, {15, 17}, {16, 17}, {22, 26}, {30, 33}, {31, 32}} and the cycle time T 0 = 100.

Fig. 2 .

 2 Fig. 2. Initial line

Fig. 3 .

 3 Fig. 3. The new precedence diagram.

Fig. 4 .

 4 Fig. 4. Rebalanced line

Table 1 .

 1 Set

	)

of tasks V and their times Task Time (s) Task Time (s) Task Time (s) Task Time (s) Task Time (s

Table 2 .

 2 Results for rebalancing :25% Objective function

	Instance tasks	Time(s) Instance tasks	Time(s) Instance tasks	Time(s)
	number Changed		number Changed		number Changed
	1	22	0.45	15	4	0.07	29	17	1.6
	2	22	0.42	16	14	0.92	30	13	1.62
	3	8	0.12	17	6	0.51	31	10	0.98
	4	12	0.04	18	11	0.1	32	21	0.12
	5	13	0.96	19	12	0.2	33	13	0.31
	6	10	0.15	20	5	0.74	34	13	0.07
	7	10	0.09	21	23	0.09	35	24	0.99
	8	14	1.49	22	21	0.12	36	11	0.32
	9	16	0.93	23	19	0.12	37	14	0.10
	10	9	0.09	24	4	0.68	38	12	1.23
	11	24	0.07	25	13	0.43	39	17	0.18
	12	13	0.12	26	10	0.14	40	10	0.17
	13	11	0.6	27	12	0.1	41	12	0.17
	14	22	0.04	28	4	0.06	42	15	0.87

Table 3 .

 3 Results for rebalancing :50% Objective function

	Instance tasks	Time(s) Instance tasks	Time(s) Instance tasks	Time(s)
	number Changed		number Changed		number Changed
	1	23	0.2	15	6	0.45	29	21	0.51
	2	27	0.54	16	14	0.18	30	13	0.18
	3	14	1.04	17	5	0.29	31	10	1.07
	4	13	0.4	18	15	0.2	32	20	0.24
	5	21	0.29	19	12	0.07	33	15	0.14
	6	12	0.51	20	5	0.18	34	16	0.12
	7	11	0.12	21	23	1.31	35	24	0.29
	8	14	0.37	22	20	0.14	36	15	0.14
	9	18	0.67	23	20	0.23	37	15	0.18
	10	12	0.92	24	4	0.21	38	15	0.31
	11	24	0.1	25	12	0.1	39	18	0.2
	12	14	0.2	26	11	0.09	40	10	0.17
	13	14	0.59	27	13	0.17	41	13	0.6
	14	22	0.18	28	10	0.98	42	17	0.53

can be applied and to propose efficient heuristic or metaheuristic methods to obtain sub-optimal solutions for such problems.

Table 4 .

 4 Results for rebalancing :75% Objective function

	Instance tasks	Time(s) Instance tasks	Time(s) Instance tasks	Time(s)
	number Changed		number Changed		number Changed
	1	23	1.07	15	12	0.29	29	27	0.45
	2	23	0.85	16	20	0.23	30	18	0.14
	3	16	0.96	17	5	0.39	31	16	0.23
	4	19	1.09	18	20	0.21	32	26	0.18
	5	27	1.35	19	18	0.14	33	21	0.93
	6	18	0.63	20	11	0.2	34	22	0.26
	7	15	0.18	21	29	0.24	35	29	0.45
	8	20	0.45	22	26	0.12	36	21	0.43
	9	24	0.59	23	26	0.18	37	21	0.35
	10	17	0.15	24	9	1.06	38	21	0.74
	11	30	0.1	25	18	0.1	39	23	0.28
	12	20	0.32	26	17	0.15	40	16	0.17
	13	19	0.99	27	18	0.34	41	19	0.23
	14	27	0.12	28	16	1.13	42	22	1.02


Xavier Moreau

Alain Thiéry

De Jong

Effect of pollutants on cell differentiation, epithelial patterning and animal fertility View project

Many invertebrates are able in tolerating and compensating sublethal stress by involving metabolic pathways and reactions that allow them in surviving under adverse environmental conditions. Therefore, in the ongoing development of new tools for aquatic ecosystem biomonitoring (marine, salt marsh and freshwater), biochemical measurements that can be used as individual biomarkers of impaired biological functions in invertebrates have been proposed. Among these biomarkers, the expression of heat shock proteins (Hsps) has been widely investigated in both natural environmental stress situations (temperature seasonal variations, hypoxia…) and anthropic disturbances as chemical contaminations. Indeed, the heat shock protein family plays a key role: their induction is the signal of exposure to conditions that alter intracellular proteins. The present contribution deals with the actual knowledge in the field of heat shock proteins as biomarker tools in aquatic bioindicator invertebrates for the early detection of environmental changes and ecological risks. The growing emphasis of these biological tools is supported by their interest to complete water quality criteria based on chemical analysis and mortality of species under stress conditions. Steps for the calibration of these chaperone proteins as potential biomarker tools will be discussed. Commentary will focus on actual knowledge and further developments.

Introduction

Heat-shock proteins (Hsps) have been evidenced by [START_REF] Tissières | Protein synthesis in salivary glands of D. melanogaster. Relation to chromosome puffs[END_REF] in salivary glands of the Diptera Drosophila melanogaster submitted to heat shock in laboratory conditions. The name of heat-shock proteins proposed at that time has been conserved even if it has been further demonstrated that these proteins are drastically induced after different physical and chemical treatments, especially those that denature proteins [START_REF] Parsell | The function of heat-shock proteins in stress tolerance: degradation and reactivation of damaged proteins[END_REF][START_REF] Welch | How cells respond to stress[END_REF][START_REF] Freeman | On the path to the heat shock response: destabilization and formation of partially folded protein intermediates, a consequence of protein thiol modifications[END_REF]. The induction of Hsps in cells of organisms exposed to stress represents a rapid and highly conserved response to proteotoxic insult. As this ubiquitous response, observed in all organisms studied from bacteria to human [START_REF] Schlesinger | Heat Shock. From Bacteria to Man[END_REF], can be induced by pathophysiological [START_REF] Morimoto | Heat shock: the role of transient inducible responses in cell damage, transformation, and differentiation[END_REF][START_REF] Jean | Chaetognaths: a useful model for studying heat shock proteins. Effect of wound healing[END_REF] and environmental stresses [START_REF] Feder | Heat-shock proteins, molecular chaperones, and the stress response: evolutionary and ecological physiology[END_REF]Aït-Aïssa et al., 2003), it has been proposed to consider Hsp induction as a biomarker tool for the early detection of environmental changes and ecological risks in aquatic biota [START_REF] Triebskorn | Biomarkers as diagnostic tools for evaluating effects of unknown past water quality conditions on stream organisms[END_REF][START_REF] Yoshimi | Activation of a stress-induced gene by insecticides in the midge, Chironomus yoshimatsui[END_REF][START_REF] Werner | Biomarker responses in Macoma nasuta (Bivalvia) exposed to sediments from northern San Francisco Bay[END_REF][START_REF] Bodin | Seasonal variations of a battery of biomarkers and physiological indices for the mussel Mytilus galloprovincialis transplanted into the northwest Mediterranean Sea[END_REF][START_REF] De | Expression of the heat shock protein Hsp70 in chloride target cells of mayfly larvae from motorway retention pond: A biomarker of osmotic shock[END_REF]. The present contribution is a short review of the actual knowledge on this biomarker tool used in aquatic bioindicator invertebrates, regarded as early warning sentinels in marine salt marsh and freshwater risk assessment.

Biomarker concept & heat-shock proteins

Originally defined by the committee on Biological Markers of the National Council (NCR) in 1987 biomarkers are "indicators signaling events in biological systems or samples following chemical exposure". From the NRC definition, biomarkers have been categorized in an attempt to classify responses. Three different types of markers were recognized: biomarkers of exposure to a toxicant, biomarkers of effects of exposure (Hsps belong to this category) and biomarkers of susceptibility to the effects of exposure. This first definition has been challenged by several authors (see [START_REF] Schlenk | of defining biomarkers for use in ecological risk assessments[END_REF][START_REF] Hyne | Invertebrate biomarkers: links to toxicosis that predict population decline[END_REF][START_REF] Hyne | Invertebrate biomarkers: links to toxicosis that predict population decline[END_REF] for review) and is has been evidenced that some biomarkers can respond to each of these tree categories. Finally, it seems that there is still a little consensus in defining biomarkers and that the definition has to be adapted to the considered biomarker. The major question is: why this biomarker is useful for environmental scientists? The answer is given by [START_REF] Chapman | The "so what?" factor[END_REF] stating that main focus for environmental scientists could be summarized as follow "determining pollution; assessing pollution; and providing decision-markers with the necessary information to address pollution that is adversely affecting the environment in which we live".

By now, it is clearly established that biomarkers are biological parameters measuring alterations in behaviors, physiology, biochemistry, cell integrity, genomic structure and expression [START_REF] Lagadic | Biomarqueurs en écotoxicologie: principes et définitions[END_REF]. During the past 25 years, many researchers have focused their efforts to develop and apply biomarkers in ecotoxicology and, now, there is a consensus to consider that they provide useful informations in the ecological risk assessment. The main idea is that they will provide early warning detection signal before that irreversible damages occur at the population and/or community levels. Even "opponents" to these biological tools state that "Biomarkers may contribute to ecological risk assessment in two main areas. The first is in exposure assessment of long-lived and/or rare species. The second is in testing hypotheses about mechanism of chemical impacts at different levels of biological organization" [START_REF] Forbes | The use and misuse of biomarkers in ecotoxicology[END_REF]. Despite the pertinent informations collected until now, there is still no standardized protocol developed for of these promising tools in monitoring programs. In fact, with the growing knowledge on biomarker potentialities, researchers have been set against the necessity to define a range of calibration criteria of which the application of a biomarker tool in field studies depends. These criteria could be summarized as follow: (1) the detection method must be simple and sensitive;

(2) the biomarker response must allow discriminating polluted from unpolluted situations; variations in the biomarker response according to xenobiotic dose and time exposures must be considered; (3) the variability due to non-toxic factors (specific variability, abiotic factors as seasonal variations, fluctuating temperature or oxygen levels...) must be understood [START_REF] Mayer | Physiological and non-specific biomarkers[END_REF][START_REF] Engel | Biomarkers, natural variability, and risk assessment: Can they coexist?[END_REF][START_REF] Moreau | Development of an ELISA assay for the detection of Multixenobiotic Resistance transporter induction in indigenous freshwater Chironomidae larvae (Diptera): a step in the calibration of a biomarker for monitoring xenobiotic exposures in the field[END_REF].

As many organisms are able to synthesize proteins that offer some protection from cellular damages, the quantification of their induction, when calibrated, will be a valuable biomarker tool. Among these proteins Hsps, which are involved in cellular protein homeostasis and repair, have been particularly investigated for several reasons: (1) Hsp genes and proteins are present in all organism studied to date; (2) Hsps are induced by numerous stressors. Table 1 sum up major works dealing with Hsps in marine, salt marsh and freshwater invertebrates. Heat-shock proteins are classified and named according to their molecular weight. Extensive studies on model species have revealed four major families of Hsps: Hsp90 (85-90 kDa), Hsp70 (68-73 kDa), Hsp60 and low molecular weight Hsp (16-47 kDa). Unlike other Hsps, low molecular weight Hsps have no known constitutive function and are only induced during stress [START_REF] Ciocca | Biological and clinical implications of heat shock protein 27,000 (Hsp27): A review[END_REF][START_REF] Sharp | Expression of low molecular weight HSP 70 related polypeptides from the symbiotic sea anemone Anemonia viridis forskall in response to heat shock[END_REF]. For example, in Anemonia viridis (marine Cnidarian) differential expression of Hsp28 and Hsp29 is correlated with thermotolerance. These cnidarians induce low molecular Hsps following heat shock but do not express them constitutively [START_REF] Sharp | Expression of low molecular weight HSP 70 related polypeptides from the symbiotic sea anemone Anemonia viridis forskall in response to heat shock[END_REF].

Many studies on Hsps have dealt with thermal stress and especially response to heat shock has been widely investigated in numerous animal species (Table 1). In most cases, induction of Hsp70 and Hsp90 were detected. Expression of Hsps proteins is now considered to confer resistance to organism against global changes and their pattern of expression which is supposed to offer markers to detect general warming is now proposed to be included in international environmental programs [START_REF] Lejeusne | Baseline expression of heat shock proteins (HSPs) of a "thermotolerant" Mediterranean marine species largely influenced by natural temperature fluctuations[END_REF].

Beside to thermal stress as inducers, researchers have also studied the induction of Hsps after xenobitic expositions under laboratory conditions. The complexity of the biological answers (i.e. induction of Hsps) results of the following points:

(1) the expression differs according the species considered even within the same genus, (2) for the same species, the expression differs according the tissue considered (ex: mantle and gills for bivalves),

(3) for the same specie and for the same tissue, the expression may differs according age and sex, (4) different methods of detection have been employed and so results between different studies are often not comparable.

Therefore, the despite fundamental results and findings no real effort of calibration of such ecotoxicological biomarkers have been assay even in marine species such Mytilus edulis or Mytilus galloprovincialis that have been widely investigated. [START_REF] Chapple | Seasonal changes in stress-70 protein levels reflect thermal tolerance in the marine bivalve Mytilus edulis L[END_REF] have shown that thermal seasonal changes are closely related with levels of Hsp70 in Mytilus edulis. In the same species and in polluted area, [START_REF] Bodin | Seasonal variations of a battery of biomarkers and physiological indices for the mussel Mytilus galloprovincialis transplanted into the northwest Mediterranean Sea[END_REF] have demonstrated seasonal variations of Hsp70 expression. They have also shown a relation between Hsp70 expression and heavy metal concentrations.

Hsp expressions in assessment of the global warming effects & species biogeographical distribution

In 2001, Choresh et al. have reported that the sea anemone Anemonia viridis exhibits a seasonal pattern of Hsp60 expression according to changes in seawater temperature, with significantly higher level of Hsp60 in summer. Considering the worldwide degradation of coral reefs, due to global climate change and human perturbations, they have suggested "the development of an early warning system for ambient assessment of the health of marine benthic communities" and proposed Hsp60 as "a possible biomonitor in marine invertebrates to predict their ability to survive future possible short-term and long-term changes in seawater temperature". [START_REF] Sorte | Thermotolerance and heat-shock protein expression in Northeastern Pacific Nucella species with different biogeographical ranges[END_REF] have investigated physiological traits responsible for determining the tide-height and latitudinal distributions of Northeastern Pacific Nucella congeners (Gasteropoda). Their results have shown that the level of total, not stress inducible, Hsp70 was a good predictor of thermotolerance and that there were species-specific differences in the relationship between Hsp70 expression and thermotolerance. They have suggested that "Hsp70 expression may be important in conferring thermotolerance in Nucella species in nature and that higher levels of molecular chaperones may underlie increased thermotolerance between conspecifics."

Recently, a field study, conducted over 4 years, has clearly demonstrated that Hsp responses are extremely fine, when considering specific expressed isoforms, and allow detecting any minor temperature change between seasons or between years in the "thermophilic" marine cave mysid Hemimysis margalefi (Crustacea, Mysidacea) [START_REF] Lejeusne | Baseline expression of heat shock proteins (HSPs) of a "thermotolerant" Mediterranean marine species largely influenced by natural temperature fluctuations[END_REF]. For example, the authors have reported that expression of Hsp60 is closely related to seasonal changes in temperature and that the higher expressions during summer suggest more protein damage at that time. This study, conducted in the Northwestern Mediterranean sea, evidences that Hsps are good biomarkers to study the effects of warming episodes or heat stress in the wild. The influence of secondary factors has been also considered: (i) in H. margalefi, Hsp expression is not sex related; (ii) percentage of immature individuals and percentage of gravid females better explain variability in Hsp45 and Hsp60 amounts, respectively; (iii) abiotic factors (pH, salinity, dissolved O 2 and light intensity variations) usually reported to be rather stable in marine caves may only explain part of the unresolved observed variations; (iv) good and stable water quality of the study site avoid influence of pollutants in the expression of theses stress proteins. The results provide strong background for the use of Hsps as biomarkers of biological and ecological effects of global warming on marine communities. This study also demonstrated that, when well conducted, field research lead to a better understanding of Hsp expression patterns in wild populations and are more informative than laboratory experiments for development and the calibration of biomarkers. Such studies must be especially encouraged and supported as they offer new early warning biological tools for one of the most preoccupant present problem in ecology, the global climate warming. For example, in the Mediterranean sea, a warming trend with a higher frequency of exceptional meteorological-hydrological events has already led to northward migrations of thermophilic species, to diseases and to mortalities inducing local extinctions or species shifts [START_REF] Pérez | Mortalité massive d'invertébrés marins: un évènement sans précédent en Méditerranée nord-occidentale[END_REF][START_REF] Chevaldonné | Regional warming-induced species shift in north-west Mediterranean marine caves[END_REF]. This kind of research could be enlarged to others key species to monitor ecological risk assessment as global warming. It seems now well established that biomarkers of short-term effects reflecting the mechanisms by which the health of organism is altered are relevant to predict the effects of long-term perturbations [START_REF] Lagadic | Biomarkers: useful tools for the monitoring of aquatic environments[END_REF].

Another study, carried out under experimental conditions in two Polychaeta species, Marenzelleria neglecta and M. viridis, shows that acclimation to variations in salinity had no explicit effect on Hsp synthesis, and that M. viridis was thermally more sensitive than its sibling species [START_REF] Blank | Stress protein response in two sibling species of Marenzelleria (Polychaeta: Spionidae): Is there an influence of acclimation salinity?[END_REF]. The authors suggest that temperature, alone or in combination with other abiotic factors, plays a far greater role in the biogeographical distribution in Marenzelleria spp. than has been estimated so far. Thus, according to them, the induction and synthesis of stress proteins in the Polychaeta species will be helpful to understand biogeographical distribution.

Hsp expressions in the assessment of xenobiotic exposure effects

During the last decades, aquatic ecosystems have been subject to increased contamination from both inorganic, e.g. heavy metals, and organic compounds, e.g. polycyclic aromatic hydrocarbons (PAHs) and polychlorinated biphenyls (PCBs), pesticides, medicinal compounds from urine wastes... Pollution caused by these contaminants represents one of the major factors of environmental stress in aquatic environments, where 'environmental stress' define all the external factors that alter the physiological processes of a living organism. Nowadays, most aquatic biota is exposed to moderate and chronic multifactor pollution and adverse effects on these ecosystems are difficult to assess. That is why, during the last 25 years, substantial efforts have focus on development of sensitive biomarkers for ecological risk evaluation. However, [START_REF] Forbes | The use and misuse of biomarkers in ecotoxicology[END_REF] have claimed that the validation process for application of biomarkers in ecotoxicology and ecological risk assessment is extremely difficult, if not impossible. These have also stated that biomarkers "have failed to demonstrate their usefulness, as indicated by their minimal incorporation into national and international risk assessment protocols". [START_REF] Handy | A proposal for the use of biomarkers for assessment of chronic pollution and in regulatory toxicology[END_REF] have already report several important steps before transferring biomarkers technology from research and development framework to a regulatory one. Among them, the need of standard operating procedures, coordinated by central body such as the International Standards Organization (ISO) or Organization for Economic Cooperation and Development (OECD), is a key impediment to the utilization of biomarkers. If it is true that biomarkers are still not used as ecotoxicological tools in the day to day management of aquatic environments, a fundamental question arises: why is it so difficult to used biomarkers in such management programs? An answer could be obtained when considered all previous works (Table 1). It is evident that most studies have been conducted under laboratory controlled experimental conditions and not in situ conditions. Hsp responses to xenobiotics have mostly been studied by laboratory works dealing with acute short-term exposures to single contaminants while long-term responses are often neglected in these experiments. This concern was already pointed out by [START_REF] Depledge | The conceptual basis of the biomarker approach[END_REF] and [START_REF] Handy | A proposal for the use of biomarkers for assessment of chronic pollution and in regulatory toxicology[END_REF] for the global biomarker approach. According to [START_REF] Handy | A proposal for the use of biomarkers for assessment of chronic pollution and in regulatory toxicology[END_REF] "long-term laboratory studies may serve as a reference point for developing biomarkers of chronic exposure or effect in the field". Long-term studies will be more informative on the adverse biological effects of contaminants. They will better reflect the field exposures that are characterized by low levels of diverse array of contaminants via both water and dietary route. As invertebrates play a key role in food webs, biomarker responses in the aquatic invertebrates are pertinent for risk assessment. Laboratory experiments are necessary to understand and to make sure that the expression of Hsps results from the exposition to a specific xenobiotic. However, despite offering clues about their induction following chemical stressors, results obtained in controlled conditions failed to be translated to field studies. As pointed out by [START_REF] Lejeusne | Baseline expression of heat shock proteins (HSPs) of a "thermotolerant" Mediterranean marine species largely influenced by natural temperature fluctuations[END_REF] "most published works study the influence of an acute or repetitive stress on the physiology of organisms raised or stressed in the laboratory. Although such approaches are helpful in providing specific biological responses to a give (controlled) stress, they are less representative and less sensitive than fieldworks. Therefore, they are not sufficient to adequately assess the combination of biotic and abiotic factors found in natural conditions."

It is known that pollutants interfere with organism integrity at the biochemical level with consequent adverse effects at the individual level such as growth, reproduction and survival. However, these biochemical parameters have a reduced long-term ecological relevance at the population and community levels. Indeed, such early warning biomarkers would be useful for detecting sublethal pollution before changes in community structure or species composition occur. This concept of an early detection of adverse effects is illustrated by [START_REF] Sanders | Relationships between accumulation of a 60 kDa stress protein and scope-for-growth in Mytilus edulis exposed to a range of copper concentrations[END_REF]. They have shown a significant induction of Hsp60 in Mytilus edulis than in controls in response to copper exposure. Their data reveal that Hsp60 induction is detected for substantially lower copper concentrations compared with those leading to physiological injuries, i.e. scope-for-growth. Another example is given by the study of [START_REF] De | Expression of the heat shock protein Hsp70 in chloride target cells of mayfly larvae from motorway retention pond: A biomarker of osmotic shock[END_REF] in which expression of Hsp70 is induced in chloride cells of mayfly larvae collected in highway retention pond during an osmotic shock, resulting from a large increase in Na + and Cl -concentrations after the de-icing road surface. As salinity is obviously a major stress for animals living in freshwater habitats, it was suggested a protective role of Hsp70. The osmotic shock disrupts biochemical processes, modifies cellular homeostasis and can cause stunted growth or death. In this study, NaCl pond concentrations were 30 times lower than those leading to chloride cells ultrastructural damages that result in impaired osmoregulation processes. Therefore, in this case, induction of Hsp70 in these target cells can also be considered as an early biological signal. In addition, the induction of stress proteins is often maximal in target organs and/or cells [START_REF] De | Expression of the heat shock protein Hsp70 in chloride target cells of mayfly larvae from motorway retention pond: A biomarker of osmotic shock[END_REF], and thus, expression pattern of biomarkers would be relevant to better understand cellular mechanisms involved during xenobiotic exposure. So, studies on biomarkers will have given informations about toxicological pathways of pollutants in living organisms.

By integrating multiple endpoints at different ecologically relevant levels of organization within one test organism, it should be possible to gain understanding in how each level within this organism responds to toxic exposure and how responses at these levels are interrelated. [START_REF] Agell | Molecular and organism biomarkers of copper pollution in the ascidian Pseudodistoma crucigaster[END_REF], in a study combining field and laboratory investigations have examined the effect of copper on several endpoints: the production of heat-shock proteins, defense metabolites, growth rates and presence of resistance forms in the colonial ascidian Pseudodistoma crucigaster. They performed a transplant experiment to a copper polluted harbor and laboratory experimental copper exposures. They failed to find any Hsp responses, despite a negative growth, in transplanted animals and in animals exposed to copper levels comparable to those measured in the harbor. They suggest an inhibition of Hsp induction possibly due to a too high stress level related to very high copper concentrations. When exposed to lower copper levels, however, an induction of Hsp78 was observed in P. crucigaster. These results demonstrate that preliminary sensitive analyses are needed to determine the range of pollutant concentrations allowing valuable responses of this biomarker in a given species. They conclude that Hsp expression can be a good biomarker for pollution in these organisms when stress levels are below a threshold.

In risk assessment of chronic multifactor pollution, it is necessary to previously conduct integrated in situ studies that combine biological and physico-chemical markers. This kind of approach has been successful for the calibration step of other stress proteins belonging to the multixenobiotic resistance system (MXR) (Saez et al., 2008). In insect aquatic larvae, MXR protein membrane density was positively correlated with PAH but not with PCB concentrations measured in stream sediments. Such field approach could also be developed for Hsps and positive experimental data already exist to encourage investigations on the relationships between Hsp expression and PCB levels in the field. For example, [START_REF] Wiens | Induction of heat-shock (stress) protein gene expression by selected natural and disturbances in the octocoral Dendronephthya klunzingeri[END_REF] report that PCB118 induces Hsp90 in the octocoral marine species Dendronephthya klunzingeri. PCB congeners, PCB77, PCB118 and PCB153, are also able to induce constitutive Hsp73 in the marine sponge Suberites domuncula [START_REF] Schröder | Induction of DNA damage and expression of heat shock protein HSP70 by polychlorinated biphenyls in the marine sponge Suberites domuncula Olivi[END_REF]. Others laboratory experiments have shown that cadmium exposure induces Hsp70 in Mytilus californianus [START_REF] Eufemia | Induction of the multixenobiotic defense mechanism (MXR), Pglycoprotein, in the mussel Mytilus californianus as a general cellular response to environmental stresses[END_REF] and in Mytilus edulis [START_REF] Tedengren | Heat pretreatment increases cadmium resistance and HSP 70 levels in Baltic Sea mussels[END_REF][START_REF] Radlowska | Stress-70 as indicator of heavy metals accumulation in blue mussel Mytilus edulis[END_REF]. However, in field research, as these proteins seems to be induced by many chemical stressors (Table 1), the Hsp70 response is probably difficult to interpret in the context of chronic multifactor pollution. Further studies that will consider specific isoforms and especially low molecular weight Hsps will probably offer suitable interpretation that could be related to specific class of pollutants [START_REF] Dhainaut | Protéines de choc thermique et résistance multixénobiotique[END_REF]. As the amino-acid sequence of these Hsps is less conserved between species than that of the ubiquitous Hsp70 family, such investigations must be carried out only in pertinent species. A pertinent species, in the present context, is either a species reared in unpolluted conditions and then transplanted in the field (caging) or a species that lives in the considered study area. In marine ecosystems, oysters seem to be good candidates for the Hsp biomarker tool calibration to assess both the global warming and xenobiotic exposure. Indeed, in Ostrea edulis, heat shock (1h exposure at 32°C) induces the appearance of a new Hsp isoform of approximately 69 kDa, which was not present in control animals [START_REF] Piano | Hsp70 expression in thermally stressed Ostrea edulis, a commercially important oyster in Europe[END_REF][START_REF] Piano | Expression of cytoprotective proteins, HSP70 and metallothioneins, in tissues of Ostrea edulis exposed to heat and heavy metals[END_REF]. Moreover, the expression of two constitutive Hsp isoforms, Hsp77 and Hsp72 was not or poorly affected by heat. Field studies are needed to characterize the seasonal variations of Hsp expressions: is induced isoform expression affected by the seasonal variations of physico-chemical parameters? Are constitutive Hsps induced during exposure to specific family of xenobiotics? For all these questions and because oysters could be maintained in laboratory and also kept in cages in the field, further studies on the expression pattern of Hsps must be encouraged in this species. Specific Hsp responses could also be obtained taking in consideration the tissue specificity. This latter and temporal patterns of Hsp induction have therefore been observed in O. edulis [START_REF] Piano | Expression of cytoprotective proteins, HSP70 and metallothioneins, in tissues of Ostrea edulis exposed to heat and heavy metals[END_REF], in agreement with similar observations reported in other organisms in response to stress [START_REF] Sanders | Tissue-Specific differences in accumulation of stress proteins in Mytilus edulis exposed to a range of copper concentrations[END_REF][START_REF] De | Expression of the heat shock protein Hsp70 in chloride target cells of mayfly larvae from motorway retention pond: A biomarker of osmotic shock[END_REF].

Conclusion

In marine ecosystems, many studies, including pertinent field research, have pointed out the possibility to use Hsp induction in the monitoring of global warming changes. Considering these investigations, a better knowledge of the mechanisms of Hsp induction in sentinel organisms will certainly lead to the development of valuable tools for ecological risk assessment.

For assessment of xenobiotic exposure effects considerable efforts must be devoted to consider Hsps as a reliable biomarker tool in aquatic biota. Integrated in situ studies that combine biological and physico-chemical markers for evaluation of environmental risks must be developed for the monitoring of aquatic ecosystems. Indeed, as it has been stated by [START_REF] Bodin | Seasonal variations of a battery of biomarkers and physiological indices for the mussel Mytilus galloprovincialis transplanted into the northwest Mediterranean Sea[END_REF], studies involving integrated responses of biomarkers as a function of natural variables and chemical mixtures in specific natural habitats would appear to be the most suitable approach for future monitoring of environmental stress.

To relate an observed biological effect to a specific pollutant or even a class of pollutants remains a very difficult task, due to the usually unknown, complex and often highly variable concentrations of pollutants in aquatic ecosystems. In this context, multimarker tools have to be developed and new biochemical methods will be helpful. Recently, [START_REF] Dondero | Gene transcription profiling in pollutant exposed mussels (Mytilus spp.) using a new low-density oligonucleotide microarray[END_REF] have described the design and implementation of a novel lowdensity oligonucleotide microarray: the "Mytox-chip". It consists of 24 mussel genes involving both normalizing elements and stress response related genes, each represented on the array with one or two different 50-mer oligonucleotide-probe reporters spotted in replicated samples on glass-activated slides. As target genes were selected on the basis of their potential involvement in mechanisms of pollutant and xenobiotic response, this method can represent a valid tool to improve the knowledge in the field of molecular toxicology for mussels. The authors explained that "the integration of biological effects of pollutants with both gene and protein expression profiles will provide a more correct interpretation of how molecular adaptations take place and how a stress syndrome develops in challenged organisms. Furthermore, since transcription patterns were significantly modulated by exposure to pollutants, and since mussels are established sentinel organisms often employed in marine biomonitoring programs, the 'Mytox-chip' appears to be a technology with a high potential." Microarray technology has to be developed for many model species. In this ongoing topic research [START_REF] Hansen | Suppression subtractive hybridization library prepared from the copepod Calanus finmarchicus exposed to a sublethal mixture of environmental stressors[END_REF] have proposed an expressed sequence tags library from the marine copepod Calanus finmarchicus exposed to different oil-industry related environmental stressors, as a tool for future toxicogenomic studies.

To assess water quality and pollution in field conditions, transplanted organisms or field collected organisms must be used. In situ exposures will provide some insights into understanding and predicting effects of chemicals on natural communities under realistic exposure conditions and would, thereby, contribute towards improving the interpretation of laboratory to in situ extrapolation. To recognize biomarkers as monitoring tools, it is important to find a complementary suite of and to use multivariate analysis for response interpretations that could combine biological responses and physico-chemical field parameters, including priority contaminant concentrations. [START_REF] Handy | A proposal for the use of biomarkers for assessment of chronic pollution and in regulatory toxicology[END_REF] propose to "take advantage of techniques developed for human epidemiology in using a suite of biomarker responses to describe "syndromes" that are diagnostic of a particular pollution scenario".

It is now evident that a calibration of biomarkers is needed before to consider them as interpretable warning signals for ecotoxicological risk assessment. Calibration must focus on the choice of representative species, field studies, and simple reproducible methods offering the ability to investigate a battery of specific biomarkers. In regards to actual knowledge, it seems that Hsp expression could be included among such biomarkers. [START_REF] Sanders | Relationships between accumulation of a 60 kDa stress protein and scope-for-growth in Mytilus edulis exposed to a range of copper concentrations[END_REF], 1994[START_REF] Steinert | Induction of HSP70 proteins in mussels by ingestion of tributyltin[END_REF][START_REF] Chapple | Stress-70 protein induction in Mytilus edulis: tissuespecific responses to elevated temperature reflect relative vulnerability and physiological functions[END_REF][START_REF] Chapple | Seasonal changes in stress-70 protein levels reflect thermal tolerance in the marine bivalve Mytilus edulis L[END_REF]Lawrence & Nicholson, 1998 Tedengren et al.,

Organisms

Table 1 .

 1 2000 List of major works dealing with Hsp induction in response to stressors in marine, salt marsh freshwater invertebrates.

	Perna perna			Zinc		NS	+		LC	Franco et al., 2006
	Bathymodiolus azoricus		Hydrothermal vent extreme conditions		+			LC & FS	Pruski & Dixon, 2007
	Macoma nasuta		Polluted sediments (DDT & metabolites)		Hsp70			LC	Werner et al., 2004
	Ostrea edulis			Cd & Zn		Hsp70			LC	Piano et al., 2004
	Ostrea edulis			Heat shock		Hsp69(I)			LC	Piano et al., 2005
	Argopecten irradians		infection by Vibrio anguillarum: immune		+			LC	Song et al., 2006
				response
	Chlamys farreri		Cd 2+ , Pb 2+ & Cu 2+	+				LC	Gao et al., 2007
	Gasteropoda
	Nucella ostrina & N. canaliculata	Thermotolerance: geographic distribution		Hsp70			LC	Sorte & Hofmann, 2005
	Crustaceans
	Eurytemora affinis (estuarine Copepoda)	Heat shock		+			LC	Bradley et al., 1992
	Calanus finmarchicus (Copepoda)	Heat shock		+			LC	Voznesensky et al., 2004
	Asellus aquaticus		Heat shock			+		LC	Anneli-Korhonen	&
									Lagerspetz, 1996.
	Hemimysis	margalefi	(Peracarida,	Seasonal temperature variations			+	Hsp45	FS	Lejeusne et al., 2006
	Mysidacea)
	Procambarus clarkii		Heat shock	+	+			LC	Rochelle et al., 1991; Sheller et
									al., 1998
	Penaeus monodon		Heat shock	Hsp86			Hsp35, Hsp43	LC	Cimino et al., 2002
								Hsp35, Hsp43
				Hypoosmotical stress	Hsp86,				LC	Cimino et al., 2002
					Hsp100
	Homarus americanus (larvae)	Heptachlor exposure		+			Snyder & Mulder, 2001
	Cherax quadricarinatus		Heat shock	Hsp86,			Hsp25	LC	Cimino et al., 2002
					Hsp97
	Echinoderms
	Paracentrotus lividus (embryo)	Cadmium exposure	+	Hsp70, Hsp72	Hsp56	Hsp25, Hsp28	LC	Roccheri et al., 2004
	Ascidian
	Pseudodistoma crucigaster		Copper		Hsp78			Agell et al., 2004
	Salt marsh organisms
	Crustaceans
	Artemia sp (larvae)		Heat shock		Hsp68		Hsp31	LC	Miller & McLennan, 1988
	Artemia franciscana		Heat shock		HSC70, Hsp67			LC	Frankenberg et al., 2000
	Freshwater organisms
	Sponges
	Ephydatia fluviatilis		Organic micropollutants extracted from		+			LC	Müller et al., 1995
				polluted water & high temperature
	Endemic Baikalian sponges		Heat stress		+			LC	Efremova et al., 2002
	Baikalospongia intermedia		Wastewater from Paper Plant		+			LC	Efremova et al., 2002

(C) : constitutive form; (I): inducible form; + : Induction of Hsp but molecular weight not given; -: Non induced Note: Given references are not exhaustive but are representative of current Hsp researches in aquatic invertebrates DDE: 1-1 dichloro-2,2-bis(p-chlorophenyl)ethylene, PCP: pentachlorophenol; NS: Non significant.

[START_REF] Radlowska | Stress-70 as indicator of heavy metals accumulation in blue mussel Mytilus edulis[END_REF][START_REF] Lyons | Variability of heat shock proteins and glutathione S-transferase in gill and digestive gland of blue mussel, Mytilus edulis[END_REF][START_REF] Pruski | Heat shock protein expression pattern (HSP70) in the hydrothermal vent mussel Bathymodiolus azoricus[END_REF][START_REF] Eufemia | Induction of the multixenobiotic defense mechanism (MXR), Pglycoprotein, in the mussel Mytilus californianus as a general cellular response to environmental stresses[END_REF][START_REF] Minier | Seasonal variation of MXR and stress proteins in the common mussel, Mytilus galloprovincialis[END_REF][START_REF] Bodin | Seasonal variations of a battery of biomarkers and physiological indices for the mussel Mytilus galloprovincialis transplanted into the northwest Mediterranean Sea[END_REF][START_REF] Malagoli | 50 Hz magnetic fields activate mussel immunocyte p38 MAP kinase and induce HSP70 and 90[END_REF][START_REF] Franzellitti | Cytoprotective responses in the Mediterranean mussel exposed to Hg 2+ and CH 3 Hg +[END_REF][START_REF] Franzellitti | Cytoprotective responses in the Mediterranean mussel exposed to Hg 2+ and CH 3 Hg +[END_REF][START_REF] Lesser | Seasonal temperature compensation in the horse mussel, Modiolus modiolus: metabolic enzymes, oxidative stress and heat shock proteins[END_REF]


Philippe Wenger
email: philippe.wenger@irccyn.ec-nantes.fr

Damien Chablat
email: damien.chablat@irccyn.ec-nantes.fr

Design of a Three-Axis Isotropic Parallel Manipulator for Machining Applications: The Orthoglide

The orthoglide is a 3-DOF parallel mechanism designed at IRCCyN for machining applications. It features three fixed parallel linear joints which are mounted orthogonally and a mobile platform which moves in the Cartesian x-y-z space with fixed orientation. The orthoglide has been designed as function of a prescribed Cartesian workspace with prescribed kinetostatic performances. The interesting features of the orthoglide are a regular Cartesian workspace shape, uniform performances in all directions and good compactness. A small-scale prototype of the orthoglide under development is presented at the end of this paper.

Introduction

Parallel kinematic machines (PKM) are interesting alternative designs for high-speed machining applications and have been attracting the interest of more and more researchers and companies. Since the first prototype presented in 1994 during the IMTS in Chicago by Gidding&Lewis (the Variax), many other prototypes have appeared.

However, the existing PKM suffer from two major drawbacks, namely, a complex Cartesian workspace and highly non linear input/output relations. For most PKM, the Jacobian matrix which relates the joint rates to the output velocities is not constant and not isotropic. Consequently, the performances (e.g. maximum speeds, forces accuracy and rigidity) vary considerably for different points in the Cartesian workspace and for different directions at one given point. This is a serious drawback for machining applications [START_REF] Kim | Performance Analysis of Parallel Manipulator Architectures for CNC Machining Applications[END_REF]; [START_REF] Treib | Similarity laws of serial and parallel manipulators for machine tools[END_REF]; [START_REF] Wenger | A Comparative Study of Serial and Parallel Mechanism Topologies for Machine Tools[END_REF]). To be of interest for machining applications, a PKM should preserve good workspace properties, that is, regular shape and acceptable kinetostatic performances throughout. In milling applications, the machining conditions must remain constant along the whole tool path [START_REF] Rehsteiner | Putting Parallel Kinematics Machines (PKM) to Productive Work[END_REF]; [START_REF] Rehsteiner | Putting Parallel Kinematics Machines (PKM) to Productive Work[END_REF]). In many research papers, this crite-rion is not taking into account in the algorithmic methods used for the optimization of the workspace volume [START_REF] Luh | Working Capability Analysis of Stewart platforms[END_REF]; [START_REF] Merlet | Dertemination of 6D Workspace of Gough-Type Parallel Manipulator and Comparison between Different Geometries[END_REF]).

The orthoglide optimization is conducted to define a 3-axis PKM with the advantages a classical serial PPP machine tool but not its drawbacks. Most industrial 3-axis machine-tool have a serial PPP kinematic architecture with orthogonal linear joint axes along the x, y and z directions. Thus, the motion of the tool in any of these directions is linearly related to the motion of one of the three actuated axes. Also, the performances are constant in the most part of the Cartesian workspace, which is a parallelepiped. The main drawback is inherent to the serial arrangement of the links, namely, poor dynamic performances.

The orthoglide is a PKM with three fixed linear joints mounted orthogonally. The mobile platform is connected to the linear joints by three articulated parallelograms and moves in the Cartesian x-y-z space with fixed orientation. Its workspace shape is close to a cube whose sides are parallel to the planes xy, yz and xz respectively. The optimization is conducted on the basis of the size of a prescribed cubic workspace with bounded velocity and force transmission factors. Two criteria are used for the architecture optimization of the orthoglide, (i) the conditioning of the Jacobian matrix of the PKM [START_REF] Golub | Matrix Computations[END_REF]; Salisbury et al. (1982); Angeles (1997)) and (ii) the manipulability ellipsoid [START_REF] Yoshikawa | Manipulability of Robot Mechanisms[END_REF]).

The first criterion leads to an isotropic architecture and to homogeneous performances in the workspace. The second criterion permits to optimize the actuated joint limits and the link lengths of the orthoglide with respect to the aforementioned two criteria.

Next section presents the orthoglide. The kinematic equations and the singularity analysis is detailed in Section 3. Section 4 is devoted to the optimization process of the orthoglide and to the presentation of the prototype.

Description of the Orthoglide

Most existing PKM can be classified into two main families. The PKM of the first family have fixed foot points and variable length struts and are generally called "hexapods". They have a Stewart-Gought parallel kinematic architecture. Many prototypes and commercial hexapod PKM already exist like the Variax-Hexacenter (Gidding&Lewis), the CMW300 (Compagnie Mécanique des Vosges), the TORNADO 2000 (Hexel), the MIKROMAT 6X (Mikromat/IWU), the hexapod OKUMA (Okuma), the hexapod G500 (GEODETIC). In this first family, we find also hybrid architectures with a 2-axis wrist mounted in series to a 3-DOF tripod positioning structure (the TRICEPT from Neos Robotics).

The second family of PKM has been more recently investigated. In this category we find the HEXAGLIDE (ETH Zürich) which features six parallel (also in the geometrical sense) and coplanar linear joints. The HexaM (Toyoda) is another example with non coplanar linear joints. A 3-axis translational version of the hexaglide is the TRIGLIDE (Mikron), which has three coplanar and parallel linear joints. Another 3-axis translational PKM is proposed by the ISW Uni Stuttgart with the LINAPOD. This PKM has three vertical (non coplanar) linear joints. The URANE SX (Renault Automation) and the QUICK-STEP (Krause & Mauser) are 3-axis PKM with three non coplanar horizontal linear joints. The SPRINT Z3 (DS Technology) is a 3-axis PKM with one degree of translation and two degrees of rotations. A hybrid parallel/serial PKM with three parallel inclined linear joints and a two-axis wrist is the GEORGE V (IFW Uni Hanover).

PKMs of the second family are more interesting because the actuators are fixed and thus the moving masses are lower than in the hexapods and tripods.

The orthoglide presented in this article is a 3-axis translational parallel kinematic machine with variable foot points and fixed length struts. Figure 1 shows the general kinematic architecture of the orthoglide.

The orthoglide has three parallel P RP aR identical chains (where P , R and P a stands for Prismatic, Revolute and Parallelogram joint, respectively). The actuated joints are the three orthogonal linear joints. These joints can be actuated by means of linear motors or by conventional rotary motors with ball screws. The output body is connected to the linear joints through a set of three parallelograms of equal lengths L = B i C i , so that it can move only in translation. The first linear joint axis is parallel to the x-axis, the second one is parallel to the y-axis and the third one is parallel to the z-axis. In figure 1, the base points A 1 , A 2 and A 3 are fixed on the i th linear axis such that

A 1 A 2 = A 1 A 3 = A 2 A 3 , B i
is at the intersection of the first revolute axis i i and the second revolute axis j i of the i th parallelogram, and C i is at the intersection of the last two revolute joints of the i th parallelogram. When each B i C i is aligned with the linear joint axis A i B i , the orthoglide is in an isotropic configuration (see 4.4) and the tool center point P is located at the intersection of the three linear joint axes. In this configuration, the base points A 1 , A 2 and A 3 are equally distant from P . The symmetric design and the simplicity of the kinematic chains (all joints have only one degree of freedom, Fig. 2) should contribute to lower the manufacturing cost of the orthoglide.

The orthoglide is free of singularities and self-collisions. The workspace has a regular, quasi-cubic shape. The input/output equations are simple and the velocity transmission factors are equal to one along the x, y and z direction at the isotropic configuration, like in a serial P P P machine [START_REF] Wenger | Kinematic Analysis of a new Parallel Machine Tool: the Orthoglide[END_REF]).

B 1 i 1 P x z y j 1 A 1 C 1 A 2 B 2 C 2 A 3 C 3 B 3 Figure 1: Orthoglide kinematic architecture i i j i r i P q i b i B i A i C i L Figure 2: Leg kinematics

Kinematic Equations and Singularity Analysis

Static Equations

Let θ i and β i denote the joint angles of the parallelogram about the axes i i and j i , respectively (fig. 2). Let ρ 1 , ρ 2 , ρ 3 denote the linear joint variables, ρ i = A i B i . In a reference frame (O, x, y, z) centered at the intersection of the three linear joint axes (note that the reference frame has been translated in Fig. 1 for more legibility) , the position vector p of the tool center point P can be defined in three different ways:

p =   a + ρ 1 + cos(θ 1 ) cos(β 1 )L + e sin(θ 1 ) cos(β 1 )L -sin(β 1 )L   (1a) p =   -sin(β 2 )L a + ρ 2 + cos(θ 2 ) cos(β 2 )L + e sin(θ 2 ) cos(β 2 )L   (1b) p =   sin(θ 3 ) cos(β 3 )L -sin(β 3 )L a + ρ 3 + cos(θ 3 ) cos(β 3 )L + e   (1c)
where a = OA i , e = C i P and we recall that

L = B i C i , ρ i = A i B i .

Kinematic Equations

Let ρ be referred to as the vector of actuated joint rates and ṗ as the velocity vector of point P :

ρ = [ ρ1 ρ2 ρ3 ] T , ṗ = [ ẋ ẏ ż] T
ṗ can be written in three different ways by traversing the three chains A i B i C i P :

ṗ = n 1 ρ1 + ( θ1 i 1 + β1 j 1 ) × (c 1 -b 1 ) (2a) ṗ = n 2 ρ1 + ( θ2 i 2 + β2 j 2 ) × (c 2 -b 2 ) (2b) ṗ = n 3 ρ3 + ( θ3 i 3 + β3 j 3 ) × (c 3 -b 3 ) (2c)
where b i and c i are the position vectors of the points B i and C i , respectively, and n i is the direction vector of the linear joints, for i = 1, 2,3.

Singular configurations

We want to eliminate the two idle joint rates θi and βi from Eqs. (2a-c), which we do upon dot-multiplying Eqs. (2a-c) by c ib i :

(c 1 -b 1 ) T ṗ = (c 1 -b 1 ) T n 1 ρ1 (3a) (c 2 -b 2 ) T ṗ = (c 2 -b 2 ) T n 2 ρ2 (3b) (c 3 -b 3 ) T ṗ = (c 3 -b 3 ) T n 3 ρ3 (3c)
Equations (3a-c) can now be cast in vector form, namely

A ṗ = B ρ
where A and B are the parallel and serial Jacobian matrices, respectively:

A =   (c 1 -b 1 ) T (c 2 -b 2 ) T (c 3 -b 3 ) T   (4a) B =   η 1 0 0 0 η 2 0 0 0 η 3   (4b) with η i = (c i -b i ) T n i for i = 1, 2, 3.
The parallel singularities [START_REF] Chablat | Working Modes and Aspects in Fully-Parallel Manipulator[END_REF]) occur when the determinant of the matrix A vanishes, i.e. when det(A) = 0. In such configurations, it is possible to move locally the mobile platform whereas the actuated joints are locked. These singularities are particularly undesirable because the structure cannot resist any force. Eq. (4a) shows that the parallel singularities occur when:

(c 1 -b 1 ) = α(c 2 -b 2 ) + λ(c 3 -b 3 )
that is when the points B 1 , C 1 , B 2 , C 2 , B 3 and C 3 are coplanar (Fig. 3). A particular case occurs when the links B i C i are parallel (Fig. 4): Serial singularities arise when the serial Jacobian matrix B is no longer invertible i.e. when det(B) = 0. At a serial singularity a direction exists along which any cartesian velocity cannot be produced. Eq. (4b) shows that det(B) = 0 when for one leg i,

(c 1 -b 1 ) // (c 2 -b 2 ) and (c 2 -b 2 ) // (c 3 -b 3 ) and (c 3 -b 3 ) // (c 1 -b 1 ) x z y
(b i -a i ) ⊥ (c i -b i ).
The optimization of the orthoglide will put the serial and parallel singularities far away from the workspace (see 4.4).

Design and Performance Analysis of the Orthoglide

For usual machine tools, the Cartesian workspace is generally given as a function of the size of a right-angled parallelepiped. Due to the symmetrical architecture of the orthoglide, the Cartesian workspace has a fairly regular shape in which it is possible to include a cube whose sides are parallel to the planes xy, yz and xz respectively (Fig. 5).

The aim of this section is to define the dimensions of the orthoglide as a function of the size L W orkspace of a prescribed cubic workspace with bounded transmission factors. We first show that the orthogonal arrangement of the linear joints is justified by the condition on the isotropy and manipulability: we want the orthoglide to have an isotropic configuration with velocity and force transmission factors equal to one. Then, we impose that the transmission factors remain under prescribed bounds throughout the prescribed workspace and we deduce the link dimensions and the joint limits.

Condition Number and Isotropic Configuration

The Jacobian matrix is said to be isotropic when its condition number attains its minimum value of one (Angeles (1997)). The condition number of the Jacobian matrix is an interesting performance index which characterises the distortion of a unit ball under the transformation represented by the Jacobian matrix. The Jacobian matrix of a manipulator is used to relate (i) the joint rates and the Cartesian velocities, and (ii) the static load on the output link and the joint torques or forces. Thus, the condition number of the Jacobian matrix can be used to measure the uniformity of the distribution of the tool velocities and forces in the Cartesian workspace.

Isotropic Configuration of the Orthoglide

For parallel manipulators, it is more convenient to study the conditioning of the Jacobian matrix that is related to the inverse transformation, J -1 . When B is not singular, J -1 is defined by: ρ = J -1 ṗ with J -1 = B -1 A Thus:

J -1 =   (1/η 1 )(c 1 -b 1 ) T (1/η 2 )(c 2 -b 2 ) T (1/η 3 )(c 3 -b 3 ) T   (5)
with

η i = (c i -b i ) T n i for i = 1, 2, 3. The matrix J -1 is isotropic when J -1 J -T = σ 2 1 3×3
, where 1 3×3 is the 3 × 3 identity matrix. Thus, we must have,

1 η 1 ||c 1 -b 1 || = 1 η 2 ||c 2 -b 2 || = 1 η 3 ||c 3 -b 3 || (6a) (c 1 -b 1 ) T (c 2 -b 2 ) = 0 (6b) (c 2 -b 2 ) T (c 3 -b 3 ) = 0 (6c) (c 3 -b 3 ) T (c 1 -b 1 ) = 0 (6d)
Equation (6a) states that the orientation between the axis of the linear joint and the link B i C i must be the same for each leg i.

Equations (6b-d) mean that the links B i C i must be orthogonal to each other. Figure 6 shows the isotropic configuration of the orthoglide. Note that the orthogonal arrangement of the linear joints is not a consequence of the isotropy condition, but it stems from the condition on the transmission factors at the isotropic configuration (see next section).

Manipulability Analysis

For a serial P P P machine tool, Fig. 7, a motion of an actuated joint yields the same motion of the tool (the transmission factors are equal to one). In the purpose on our study, this factor is calculated from linear joint to the end-effector. For a parallel machine, these motions are generally not equivalent. When the mechanism is close to a parallel singularity, a small joint rate can generate a large velocity of the tool. This means that the positioning accuracy of the tool is lower in some directions for some configurations close to parallel singularities because the encoder resolution is amplified. In addition, a velocity amplification in one direction is equivalent to a loss of rigidity in this direction.

The manipulability ellipsoids of the Jacobian matrix of robotic manipulators was defined several years ago [START_REF] Salisbury | Articulated Hands: Force Control and Kinematic Issues[END_REF]). This concept has then been applied as a performance index to parallel manipulators [START_REF] Kim | Performance Analysis of Parallel Manipulator Architectures for CNC Machining Applications[END_REF]). Note that, although the concept of manipulability is close to the concept of condition number, these two concepts do not provide the same information. The condition number quantifies the proximity to an isotropic configuration, i.e. where the manipulability ellipsoid is a sphere, or, in other words, where the transmission factors are the same in all the directions, but it does not inform about the value of the transmission factor.

The manipulability ellipsoid of J -1 is used here for (i) justifying the orthogonal orientation of the linear joints and (ii) defining the joint limits of the orthoglide such that the transmission factors are bounded in the prescribed workspace.

We want the transmission factors to be equal to one at the isotropic configuration like for a P P P machine tool. This condition implies that the three terms of Eq. ( 6) must be equal to one:

1 η 1 ||c 1 -b 1 || = 1 η 2 ||c 2 -b 2 || = 1 η 3 ||c 3 -b 3 || = 1 (7)
which implies that (b ia i ) and (c ib i ) must be collinear for each i. Since, at this isotropic configuration, links B i C i are orthogonal, Eq. ( 7) implies that the links A i B i are orthogonal, i.e. the linear joints are orthogonal. For joint rates belonging to a unit ball, namely, || ρ|| ≤ 1, the Cartesian velocities belong to an ellipsoid such that:

ṗT (JJ T ) ṗ ≤ 1

The eigenvectors of matrix (JJ T ) -1 define the direction of its principal axes of this ellipsoid and the square roots ξ 1 , ξ 2 and ξ 3 of the eigenvalues of (JJ T ) -1 are the lengths of the aforementioned principal axes. The velocity transmission factors in the directions of the principal axes are defined by ψ 1 = 1/ξ 1 , ψ 2 = 1/ξ 2 and ψ 3 = 1/ξ 3 . To limit the variations of this factor in the Cartesian workspace, we impose

ψ min ≤ ψ i ≤ ψ max (8)
throughout the workspace. This condition determines the link lengths and the linear joint limits. To simplify the problem, we set ψ min = 1/ψ max .

Design of the Orthoglide for a Prescribed Workspace

The aim of this section is to define the position of the fixed point A i , the link lengths L and the linear actuator range ∆ρ with respect to the limits on the transmission factors defined in Eq. ( 8) and as a function of the size of the prescribed workspace L W orkspace .

Our process of optimization is divided into three steps.

1. First, we determine two points Q 1 and Q 2 in the prescribed cubic workspace such that if the transmission factor bounds are satisfied at these points, they are satisfied in all the prescribed workspace.

2. The points Q 1 and Q 2 are used to define the leg length L as function of the size of the prescribed cubic workspace.

3. Finally, the positions of the base points A i and the linear actuator range ∆ρ are calculated such that the prescribed cubic workspace is fully included in the Cartesian workspace of the orthoglide.

Step 1: The transmission factors are equal to one at the isotropic configuration. These factors increase or decrease when the tool center point moves away from the isotropic configuration and they tend towards zero or infinity in the vicinity of the singularity surfaces. It turns out that the points Q 1 and Q 2 defined at the intersection of the workspace boundary with the axis x = y = z (figure 8) are the closest ones to the singularity surfaces, as illustrated in figure 9 which shows on the same top view the orthoglide in the two parallel singular configurations of figures 3 and 4. Thus, we may postulate the intuitive result that if the prescribed bounds on the transmission factors are satisfied at Q 1 and Q 2 , then these bounds are satisfied throughout the prescribed cubic workspace. Although we could not derive a simple formal proof, we have verified numerically that this result holds. Step 2: At the isotropic configuration, the angles θ i and β i are equal to zero by definition. When the tool center point P is at Q 1 , ρ 1 = ρ 2 = ρ 3 = ρ min (Fig. 10). When P is at Q 2 , ρ 1 = ρ 2 = ρ 3 = ρ max (Fig. 11).

x z y Q 2 Q 1 Figure 8: Points Q 1 and Q 2 x y B 1 B 2 A 1 A 2 C 1 C 2 C' 1 C' 2 B' 1 B' 2 P P' Parallel singularities Parallel singularities Workspace Q 1 Q 2 Serial singularities
We pose ρ min = 0 for more simplicity.

On the axis

(Q 1 Q 2 ), β 1 = β 2 = β 3 and θ 1 = θ 2 = θ 3 . We note, β 1 = β 2 = β 3 = β and θ 1 = θ 2 = θ 3 = θ (9)
Upon substitution of Eq. ( 9) into Eqs. (1a-c), the angle β can be

C 1 C 2 x y Q 2 B 1 B 2 A 1 A 2 Q 1 Figure 10: Q 1 configuration x y Q 2 B 1 C 1 B 2 A 2 C 2 Q 1 A 1 Dr Dr Figure 11: Q 2 configuration written as a function of θ, β = -arctan(sin(θ)) (10)
Finally, by substituting Eq. ( 10) into Eq. ( 5), the inverse Jacobian matrix J -1 can be simplified as follows

J -1 =   1 -tan(θ) -tan(θ) -tan(θ) 1 -tan(θ) -tan(θ) -tan(θ) 1  
Thus, the square roots of the eigenvalues of (JJ T ) -1 are,

ξ 1 = |2 tan(θ) -1| and ξ 2 = ξ 3 = | tan(θ) + 1|
And the three velocity transmission factors are,

ψ 1 = 1 |2 tan(θ) -1| and ψ 2 = ψ 3 = 1 | tan(θ) + 1| (11)
Figure 12 depicts ψ 1 , ψ 2 and ψ 3 as function of θ along the axis

(Q 1 Q 2 ). 0 1 2 3 4 5 -180°y 1 y 2 q 0°180°Q 2 Q 1 Isotropic configuration
(Q 1 Q 2 )
The joint limits on θ are located on both sides of the isotropic configuration. To calculate the joint limits, we solve the following inequations,

1 ψ max ≤ 1 |2 tan(θ) -1| ≤ ψ max (12a) 1 ψ max ≤ 1 | tan(θ) + 1| ≤ ψ max (12b)
where the value of ψ max depends on the performance requirements. Two sets of joint limits ([θ Q1 β Q1 ] and [θ Q2 β Q2 ]) are found. The detail of this calculation is given in the Appendix.

The position vectors q 1 and q 2 of the points Q 1 and Q 2 , respectively, can be easily defined as a function of L (Figs. 10 and 11), q 1 = [q 1 q 1 q 1 ] T and q 2 = [q 2 q 2 q 2 ] T (13a)

with

q 1 = -sin(β Q1 )L and q 2 = -sin(β Q2 )L (13b)
The size of the Cartesian workspace is,

L W orkspace = |q 2 -q 1 |
Thus, L can be defined as a function of L W orkspace .

L = L W orkspace | sin(β Q2 ) -sin(β Q1 )|
Step 3: We want to determine the positions of the base points, namely, a. When the tool center point P is at Q ′ 1 defined as the projection onto the y-axis of Q 1 , ρ = 0 and, (Fig. 13)

OA 2 = OQ ′ 1 + Q ′ 1 C 2 + C 2 A 2 with OA 2 = a, OQ ′ 1 = q 1 , Q ′ 1 C 2 = P C 2 = -e and since ρ = 0, C 2 A 2 = C 2 B 2 -L. Thus, a = q 1 -e -L C 1 x y Q 2 B 1 B 2 A 1 A 2 Q' 1 a C 2 Q 1 e L Figure 13: The point Q ′ 1 used for the determination of a
Since q 1 is known from Eqs. ( 13a) and (19b), a can be calculated as function of e, L and ψ max . Now, we have to calculate the linear joint range ∆ρ = ρ max (we have posed ρ min =0).

When the tool center point P is at Q 2 , ρ = ρ max . The equation of the direct kinematics (Eq. ( 1b)) written at Q 2 yields,

ρ max = q 2 -a -cos(θ Q2 ) cos(β Q2 )L -e

Prototype

Using the aforementioned two kinetostatic criteria, a small-scale prototype is under development in our laboratory. The mechanical structure is now finished, (Fig. 14). The actuated joints used for this prototype are rotative motors with ball screws. The prescribed performances of the orthoglide prototype are a Cartesian velocity of 1.2m/s and an acceleration of 14m/s 2 at the isotropic point. The desired payload is 4kg. The size of its prescribed cubic workspace is 200 × 200 × 200 mm. We limit the variations of the velocity transmission factors as,

1/2 ≤ ψ i ≤ 2 (14)
The resulting length of the three parallelograms is L = 310 mm and the resulting range of the linear joints is ∆ ρ = 257 mm. Thus, the ratio of the range of the actuated joints to the size of the prescribed Cartesian workspace is r = 200/257 = 0.78. This ratio is high compared to other mechanisms. The three velocity transmission factors are depicted in Fig. 15. These factors are given in a z-cross section of the Cartesian workspace passing through Q 1 .

Figure 14: The orthoglide prototype Presented in this paper is a new kinematic structure of a PKM dedicated to machining applications: the Orthoglide. The main feature of this PKM design is its trade-off between the popular serial PPP architecture with homogeneous performances and the parallel kinematic architecture with good dynamic performances. The workspace is simple, regular and free of singularities and self-collisions. The Jacobian matrix is isotropic at a point close to the center point of the workspace. Unlike most existing PKMs, the workspace is fairly regular and the performances are homogeneous in it. Thus, the entire workspace is really available for tool paths. In addition, the orthoglide is rather compact compared to most existing PKMs. A small-scale prototype of this mechanism is under construction at IRCCyN. First experiments with plastic parts will be conducted. The dynamic analysis has not been reported in this article. A rigid dynamic model has been proposed in [START_REF] Guegan | Dynamic Modeling of the Orthoglide[END_REF] and an elastic dynamic model is now being developed with the software package Meccano.

0,0 -1,0 1,0 2,0 0,0 -1,0 1,0 2,0 -1,0 1,0 2,0 0,0 1 , 0 1 , 0 1 , 1 1 ,2 1 , 1 1 , 2 1 ,1 1,2 x y 0,0 -1,0 1,0 2,0 -1,0 1,0 2,0 0,0 1 , 2 1 , 2 1 ,3 1 , 3 1 ,4 1 , 4 1 ,5 1 , 5 1 , 6 x y Q 1 Q 1 y 2 y 3 -1,0 1,0 2

Appendix

To calculate the joint limits on θ and β, we solve the followings inequations, from the Eqs. 12, |2 tan(θ) -1| ≤ ψ max (15a)

1 |2 tan(θ) -1| ≤ ψ max (15b)
Thus, we note,

f 1 = |2 tan(θ) -1| f 2 = 1/|2 tan(θ) -1| (16a)
The isotropic configuration is located at the configuration where θ = β = 0. The limits on θ and β are in the vicinity of this configuration. Along the axis (Q 1 Q 2 ), the angle θ is lower than 0 when it is close to Q 2 , and greater than 0 when it is close to Q 1 .

To find θ Q1 , we study the functions f 1 and f 2 which are both decreasing on [0 arctan(1/2)]. Thus, we have,

θ Q1 = arctan ψ max -1 2ψ max (19a)
β Q1 = -arctan ψ max -1 5ψ 2 max -2ψ max + 1

(19b)
In the same way, to find θ Q2 , we study the functions f 1 and f 2 on [s 1 0]. The three roots s 1 , s 2 and s 3 define two intervals. If ψ max ∈ [f 1 (s 1 ) f 1 (s 2 )], we have,

θ Q2 = -arctan ψ max -1 ψ max (20a) β Q2 = arctan ψ max -1 2ψ 2 max -2ψ max + 1 (20b) otherwise, if ψ max ∈ [f 1 (s 2 ) f 1 (s 3 )],
θ Q2 = -arctan ψ max -1 2 (20c)

β Q2 = arctan ψ max -1 ψ max 2 -2ψ max + 5 (20d)

Figure 3 :Figure 4 :

 34 Figure 3: Parallel singular configuration when B i C i are coplanar

Figure 6 :

 6 Figure 5: Cartesian workspace

Figure 7 :

 7 Figure 7: Typical industrial 3-axis P P P machine-tool

Figure 9 :

 9 Figure 9: Points Q 1 and Q 2 and the singular configurations (top view)

Figure 12 :

 12 Figure 12: The three velocity transmission factors as function of θ along the axis (Q 1 Q 2 )

Figure 15 :

 15 Figure 15: The three velocity transmission factors in a z-cross section of the Cartesian workspace passing through Q 1

Figure ( 16 )Figure 16 :

 1616 Figure (16) shows f 1 and f 2 as function of θ along(Q 1 Q 2 ). The four roots of f 1 = f 2 in [-π π] are, s 1 = -arctan (1 + √ 17)/4 (17a) s 2 = -arctan (1/2) (17b) s 3 = 0 (17c) s 4 = arctan (-1 + √ 17)/4 (17d)

Acknowledgments

The authors would like to acknowledge the financial support of Région Pays-de-Loire, Agence Nationale pour la Valorisation de la Recherche, and École des Mines de Nantes.