Claude-Pierre Jeannerod
email: claude-pierre.jeannerod@ens-lyon.fr

Guillaume Revy
email: guillaume.revy@ens-lyon.fr

Optimizing correctly-rounded reciprocal square roots for embedded VLIW cores

Keywords: reciprocal square root, binary floating-point arithmetic, correct rounding (to nearest), polynomial evaluation, software implementation, VLIW processor core

This paper presents an optimized software implementation of the reciprocal square root function x → x -1/2 , for IEEE binary32 floating-point data and with correct rounding to nearest. The main feature of this implementation is high instruction-level parallelism (ILP) exposure, which results here from an extension of the bivariate polynomial evaluation-based method of [6] as well as from the design of a specific rounding procedure. This implementation proves to be very efficient for some VLIW processor cores like STMicroelectronics' ST231 (used mainly for embedded media processing), for which a low latency of 29 cycles has been measured.

Introduction

Reciprocal square roots frequently appear in digital signal processing and scientific computing [START_REF] Schulte | High-speed inverse square roots[END_REF], and correctlyrounded implementations are recommended in the latest revision of the IEEE 754 standard [1, §9.2]. Our aim here is to present such an implementation, in software, for binary32 data and rounding to nearest even.

The targeted processors are the ST231 four-issue VLIW, 32-bit cores from STMicroelectronics, whose main features are as follows: 4 parallel ALUs, 2 parallel multipliers (giving the first or last 32 bits of a 32 × 32 integer product), a leading-zero counter, 64 general purpose registers and 8 condition registers, partial predication via select instructions, and encoding of immediate operands up to 32 bits.

In order to fully exploit the high degree of parallelism of our target and to avoid using coefficient tables, we extend to reciprocal square roots the high-ILP, polynomial-based square rooting method introduced in [START_REF] Jeannerod | Computing floating-point square roots via bivariate polynomial evaluation[END_REF]. This extension, which is presented in Section 2, seems to allow for more ILP exposure than the Newton-like iterations used for example in [START_REF] Schulte | High-speed inverse square roots[END_REF][START_REF] Piñeiro | High-speed doubleprecision computation of reciprocal, division, square root and inverse square root[END_REF][START_REF] Raina | FLIP: a Floating-point Library for Integer Processors[END_REF]. Section 3 then gives some details about our implementation of this extension for the binary32 format, its validation, and the performances obtained on the ST231 core. In particular, a latency of 29 cycles has been measured, for rounding to nearest even and with subnormal number support.

A typical use of correctly-rounded reciprocal square roots is for 3D vector normalization [x, y, z] → [x/w, y/w, z/w], with w = x 2 + y 2 + z 2 . In the context of the FLIP library,1 our implementation allows to replace one square root (23 cycles) and three divisions (3×32 cycles) by one reciprocal square root (29 cycles) and three products (3×21 cycles). Both cases yield an error of at most 1 ulp but, assuming the sum of squares is available, the latter reduces latency by 9% if the coordinates x/w, y/w, z/w are produced simultaneously, and by over 20% if they are produced sequentially.

Reciprocal square root algorithm

Special operands

For reciprocal square root, special operands are ±0, ±∞, negative numbers, and NaNs. The corresponding special results required by the IEEE 754 standard [1] are shown in Table 1. In this table "< 0" represents -∞ or any negative (nonzero) finite floating-point number, and "qNaN" means any quiet Not-a-Number having the same payload as the operand (that is, only the sign is not specified).

Table 1. Special values of function rsqrt.

x +0 +∞ -0 < 0 NaN rsqrt(x) +∞ +0 -∞ qNaN qNaN
Since here special operands are exactly the same as those of square root, we apply the method described in [6, § 4.1] to detect all of them simultaneously. Then, classically, the special results displayed in Table 1 are computed in parallel with the generic case (described next in Section 2.2), which dominates the cost.

In some implementations the reciprocal square root of -0 is +∞ instead of -∞. This is for example the case in GNU MPFR. 2 An advantage of such a choice is consistency with the specification of the rootn function (x, n) → x 1/n , for which the standard mandates that the value +∞ be returned when x is -0 and n is even and negative.

Positive finite operands

When x is non special, it has the form x = m • 2 e , where, for a binary floating-point system of precision p and extremal exponents e min and e max , m = (m 0 .m 1 . . . m p-1 ) 2 and e min ≤ e ≤ e max .

More precisely, x is either such that m 0 = 1 (normal number) or such that m 0 = 0 and e = e min (subnormal number). We assume as usual that e min is even, e min ≤ e max , e max = 1 -e min , and 2 ≤ p ≤ e max , all these constraints being satisfied by the standard binary formats of [1].

In both subnormal and normal cases one may check that, for example, 2 emin ≤ x -1/2 ≤ 2 emax . This implies that the reciprocal square root of a non special number always lies in the range [2 emin , (2-2 1-p )•2 emax ] of positive normal numbers or, in other words, that neither underflow nor overflow can occur.

It follows that x -1/2 = • 2 d for some real in [1, 2] and some integer d such that e min ≤ d < e max . The correctlyrounded (to nearest even) value of x -1/2 is thus given by

RN(x -1/2 ) = RN( ) • 2 d ,
and, classically, RN( ) and d can be computed in parallel.

First, we provide explicit formulae for and d. Let λ be the number of leading zeros of m, and let m = m • 2 λ and e = e -λ. Let c be 1 if e is even, 0 otherwise. Then one may check that = s 2/(1 + t) and d = -(e + 1)/2 , (1) where s = 2 c/2 and t = m -1, and with • denoting the usual floor function.

2 http://www.mpfr.org/mpfr-current/; see also [START_REF] Fousse | MPFR: A Multiple-Precision Binary Floating-Point Library with Correct Rounding[END_REF][START_REF] Zimmermann | Implementation of the reciprocal square root in MPFR[END_REF].

Second, the above formula for d being already suitable for implementation, we focus on the computation of RN( ).

As in [START_REF] Jeannerod | Computing floating-point square roots via bivariate polynomial evaluation[END_REF] we proceed by correcting "one-sided truncated approximations" similar to those of [3, p. 459]: is approximated from above by v to precision p. Then v is truncated after p fraction bits into a number u. Finally RN( ) is produced by the following rounding algorithm: if u ≥ then return v truncated after p -1 fraction bits else return v + 2 -p truncated after p -1 fraction bits This rounding algorithm is not specific to reciprocal square root and we initially used it in [START_REF] Jeannerod | Computing floating-point square roots via bivariate polynomial evaluation[END_REF] for square root. The correctness proof given in [6, §3.2.1] only uses the fact below.

Fact 1. cannot be exactly halfway between two consecutive floating-point numbers.

In the case of reciprocal square root, this fact is well known to be true (see for example [5, Table 1]) and can be shown as follows.

Proof. Assume is halfway between two consecutive floating-point numbers. Then = 2 and, since ∈ [1, 2], its binary expansion must have the form 1. 1 . . . p-1 1. Consequently, = (2L + 1) • 2 -p for some integer L such that 2 p-1 ≤ L < 2 p . Similarly, m = K • 2 1-p for some integer K such that 2 p-1 ≤ K < 2 p . The first identity in (1) thus gives K(2L + 1) 2 = 2 3p+c , whose left-hand side has an odd factor and whose right-hand side is an integer power of two. Hence a contradiction and the proof follows.

The main difficulties of the above approach are to compute v as fast as possible, and to evaluate the condition u ≥ in order to decide whether u should be corrected or not:

• To maximize ILP exposure, we compute v by the method of [START_REF] Jeannerod | Computing floating-point square roots via bivariate polynomial evaluation[END_REF], that is, as the value (up to rounding errors) of a bivariate polynomial

P (s, t) = 2 -p-1 + s • a(t) (2)
such that a(t) is a "good enough" polynomial approximation of 2/(1 + t) over [0, 1).

• To decide whether u ≥ or not, we evaluate the equivalent condition

(1 + t)u 2 ≥ 2s 2 , (3)
whose both sides now have finite binary expansions.

Implementation for the binary32 format

The above algorithm has been implemented in C99 for the binary32 format of [1], where p = 24 and e min = -126. The lines of code for handling special operands, computing d, and evaluating the rounding condition (3) have been written and optimized by hand. However, the polynomial a(t) = i a i t i has been computed as a truncated Remez approximant using Sollya, 3 and a parallel and accurate evaluation code for v has been automatically written by a generator under development called CGPE (Code Generation for Polynomial Evaluation [START_REF] Revy | CGPE -Code Generation for Polynomial Evaluation[END_REF]).

For each of these subtasks the goal is to achieve low latency by exposing as much ILP as possible. Sections 3.1 and 3.2 illustrate this for, respectively, special-operand handling and polynomial evaluation. Section 3.3 further details our optimized implementation of the evaluation of condition (3). Section 3.4 concludes with the validation of the resulting code and with performance results obtained on the ST231 core.

Implementation of two specifications for special operands

Our C implementation of the first specification (Table 1) is given below. Here and hereafter X is the 32-bit unsigned integer that carries the standard encoding of the binary32 floating-point operand x. (Also, unless otherwise specified the variables of our C codes are always of type uint32 t.)

1 if ((X + 0xFFFFFFFF) >= 0x7F7FFFFF) 2 { 3 if (X <= 0x7F800000 || X == 0x80000000) 4
return X ˆ0x7F800000; // +-inf or +0 5 return X | 0x7FC00000; // qNaN having the 6 // same payload as X 7 } Line 1 allows to filter out all special inputs, while line 3 further isolates inputs of the form ±0 or +∞; these two conditions are exactly the same as for square root in [6, § 4.1]. The only difference is then the bitwise XOR of X and the hexadecimal constant 0x7F800000, giving an overhead of only one instruction (involving an extended immediate).

To implement the second specification of Section 2.1, it suffices to replace line 4 in the code above with:

Generating an optimized code for polynomial evaluation

The polynomial a(t) used has degree 9, and CGPE found the following scheme for evaluating P (s, t) in (2): In this scheme, all the variables are 32-bit unsigned integers, and addition and multiplication respectively mean (A ± B) mod 2 32 and mul(A, B) := AB/2 32 for two such integers A and B. On the ST231, an addition takes 1 cycle and a multiplication takes 3 cycles. Furthermore, it turns out that the above parenthesization can be evaluated in 14 cycles compared to 38 cycles using Horner's rule. (One of the a i 's is a power of two, which allows to trade off one multiplication against one shift, and eventually to save two cycles. Hence 38 cycles instead of 40 cycles.) The accuracy (rounding errors) of this evaluation scheme has been checked using interval arithmetic from Gappa. 44

Implementing the condition for correct rounding

Assume that t and u are exactly represented by the k-bit unsigned integers T = t • 2 k and U = u • 2 k-2 , respectively. To represent 1 + t exactly, we define a third k-bit unsigned integer

Y = (1 + t) • 2 k-1 . It follows that Y = 2 k-1 + T /2, and condition (3) thus reads Y U 2 ≥ Z, Z = 2 3k-4+c , c ∈ {0, 1}.
Note that Y U 2 is a 3k-bit positive integer that can be seen as a Q5.(3k -5) number. However, since Z is a large power of two, evaluating the condition Y U 2 ≥ Z does not require the knowledge of the full product Y U 2 . Indeed, the property below shows that it suffices to evaluate P ≥ Q, where P and Q are two k-bit unsigned integers.

Property 1. Let P = Y U 2 • 2 -2k and Q = 2 k-4+c . One has Y U 2 ≥ Z if and only if P ≥ Q. Proof. One has Z = Q • 2 2k . From P ≤ Y U 2 • 2 -2k it follows that P ≥ Q implies Y U 2 ≥ Z. Conversely, P < Q implies P ≤ Q -1 and, using Y U 2 • 2 -2k -1 < P , it follows that Y U 2 • 2 -2k < Q, that is, Y U 2 < Z.
It remains to evaluate condition "P ≥ Q" as efficiently as possible in our context. If k = 32 then Q equals 2 28+c and can be implemented simply by shifting left by c:

Q = 0x10000000 << c;
To implement the computation of P = Y U 2 • 2 -2k , we may proceed as follows. Let A hi and A lo be the two k-bit, positive integers such that

U 2 = A hi • 2 k + A lo . Then Y U 2 = Y A hi • 2 k + Y A lo and, defining B hi , B lo , C hi , C lo as the k-bit positive integers such that Y A hi = C hi •2 k +C lo and Y A lo = B hi • 2 k + B lo , we obtain Y U 2 = C hi • 2 2k + (B hi + C lo ) • 2 k + B lo .
Consequently,

P = C hi + carry generated by B hi + C lo . (4)
(The carry is 1 if addition overflows, 0 otherwise.) This is illustrated by Figure 1, where D hi = P and In particular, the lower half B lo of the product A lo Y is not needed, nor is the middle term D mi . All we must know is whether adding B hi to C lo overflows or not. The property below shows how to detect this.

D lo = B lo . Y × A hi A lo B hi B lo + C hi C lo D hi Dmi D lo
Property 2. The carry generated by the sum

B hi + C lo is equal to 1 if and only if (B hi + C lo ) mod 2 k < B hi .
Proof. Recall that B hi , C lo ∈ {0, 1, . . . , 2 k -1}, and let Q and R be the unique non-negative integers such that

B hi + C lo = Q • 2 k + R and 0 ≤ R < 2 k . (5) Since B hi + C lo < 2 k+1 , Q is either 0 or 1. Hence the sum overflows if and only if Q = 1. If Q = 1 then R = B hi + C lo -2 k and, since C lo < 2 k , we obtain R < B hi . Conversely, let us show that R < B hi implies Q = 1. Form (5), R < B hi implies C lo < Q • 2 k . Since C lo ≥ 0 and Q ∈ {0, 1}, we deduce that Q = 1.
Combining (4) and Property 2 leads to the following implementation for computing P . Here, all variables are 32-bit unsigned integers. Furthermore, we assume available + and mul defined in Section 3.2, and as well as * such that A * B := AB mod 2 32 for two 32-bit unsigned integers A and B. On ST231 cores, < has the same latency as + (1 cycle) and * has the same latency as mul (3 cycles). Therefore, the above code yields P in 8 instructions and 9 cycles.

To sum up, we have shown so far that "P ≥ Q" can be evaluated in 10 cycles. Since in (4) getting the carry is 1cycle more expensive than getting C hi (and, of course, than getting Q), we may try to evaluate instead the equivalent condition "carry ≥ Q -C hi ." Unfortunately, how to implement this comparison in fewer than 10 cycles is unclear.

However, on ST231 one can save 1 cycle by using the operation addcg which performs integer addition with carry propagation. More precisely, addcg takes two 32-bit unsigned integers A, B and one bit c in (carry in) as inputs, and produces as outputs the 32-bit unsigned integer C and the bit c out (carry out) such that

A + B + c in = c out • 2 32 + C.
From Figure 1, we can thus obtain P = D hi as follows:

• (D mi , c out ) = addcg(B hi , C lo , 0), • (P, * ) = addcg(0, C hi , c out ).
Notice that the carry * produced by the second call to the addcg instruction is in fact known to be zero.

A first way of implementing this computation of P is to use the intrinsic function st200addcg, whose operands are three 32-bit unsigned integers A, B, c in , and whose output is the 64-bit unsigned integer c out • 2 32 + C. Hence, the lines 7, 8, 9 of the previous code can be replaced with: 7 uint64_t S = __st200addcg(B_hi, C_lo, 0); 8 P = (uint32_t) __st200addcg(0, C_hi, S >> 32);

The assembly code generated by the ST200 compiler (-O3, ST231) on the above piece of code then looks like convib $b0 = $r0;; addcg $r0, $b0 = $r17, $r20, $b0;; addcg $r8, $b0 = $r0, $r21, $b0;;

where reading $r0 returns 0, and where $r8 is a 32-bit register containing the value of P . Since the latency of addcg is of 1 cycle, we finally get P in 8 cycles instead of 9. The main drawback of this approach is the explicit use of an intrinsic function, that makes the C code ST231-dependent.

A second way of getting P in 8 cycles through portable C code is as follows. The above addcg-based approach computes D hi and D mi , that is, performs the addition B hi + C exactly, where C = Y A hi is a full, 64-bit product. Hence P can be computed as follows, with * now denoting the lower half of the exact product of two 64-bit unsigned integers: Interestingly, the assembly generated by the ST200 compiler for this portable C code contains exactly the sequence of two addcg shown above, thus yielding P in 8 cycles. This code is the one we have kept for our implementation.

Validation and performances

Our implementation, called rsqrt, has been compared exhaustively to the power functions of the glibc and MPFR.

We have also compiled it with the ST200 VLIW compiler, in -O3 and for the ST231 core. Without subnormal support, the latency of the generated assembly code is of 28 cycles. For comparison, the previously best available code for the ST231 was an implementation of Goldschmidt's method with initial approximation by a degree-3 polynomial [8, §12] and has a latency of 56 cycles. Our approach is thus twice faster. Also, our code offers full subnormal support at the cost of only 1 extra cycle, the latency then being of 29 cycles.

Finally, the table below shows the advantage of using our specialized operator rsqrt rather than simply compound-ing division/inversion and square root. (Brackets contain the results obtained when subnormals are not supported.) Although each of the operators div, inv, and sqrt used here is highly optimized for the ST231, full specialization yields significantly smaller and faster codes. In fact, such codes are also more accurate since only one rounding error occurs instead of two.

Figure 1 .

 1 Figure 1. Decomposing the exact value of the product Y U 2 into three chunks of k bits each.

1 3 4

 3 A_hi = mul(U, U); A_lo = U * U; 2 B_hi = mul(Y, A_lo); C_lo = Y * A_hi; 5 C_hi = mul(Y, A_hi); 6 7 S = B_hi + C_lo; 8 carry = S < B_hi; 9 P = C_hi + carry;

1

  A_hi B_hi + C; // S and C are of type uint64_t 8 P = S >> 32;

http://flip.gforge.inria.fr/

return ˜X & 0x7F800000; // +inf or +0The bitwise negation of X allows in particular to exchange the exponent fields of zero and infinity. Masking then sets both the sign bit and the fraction field to zero.[START_REF] Ercegovac | Digital Arithmetic[END_REF] http://sollya.gforge.inria.fr/ On ST231, both specifications can be implemented at exactly the same cost using the codes above. This comes from the availability of an instruction andc that complements the input and then applies a bitwise AND, and which has the same latency (1 cycle) as the bitwise XOR instruction.

http://gappa.gforge.inria.fr/ and[START_REF] Daumas | Certification of bounds on expressions involving rounded operators[END_REF].

Acknowledgements

This research was supported by "Pôle de compétitivité mondial" Minalogic and by the ANR project EVA-Flo. Many thanks to Christophe Monat and Philippe Théveny for useful discussions and comments on a draft of this paper.


Fatima Benbouzid-Sitayeb

Ahcène Bendjoudi
email: ahcene.bendjoudi@gmail.com

Samir Benkhallat
email: benkhellat_samir@hotmail.com

Christophe Varnier
email: christophe.varnier@ens2m.fr

Noureddine Zerhouni
email: zerhouni@ens2m.fr

A Study of Maintenance Contribution to a Joint Production and Preventive maintenance Scheduling Problem in the Robustness Framework

Keywords: Production, Preventive maintenance, Flowshop, Joint scheduling, Disruption, robustness, Optimization criteria

In this paper, we deal with a joint production and Preventive Maintenance (PM) scheduling problem in the robustness framework. The contributions of this paper are twofold. First, we will establish that the insertion of maintenance activities during production scheduling can hedge against some changes in the shop environment. Furthermore, we will check if respecting the optimal intervals of maintenance activities guarantees a minimal robustness threshold. Then, we will try to identify from the used optimisation criteria those that allow making predictive schedules more robust. The computational experiments in a flowshop show that joint production and PM schedules are more robust than production schedules and maintenance provides an acceptable tradeoff between equipment reliability and performance loss under disruption

Introduction

Production scheduling is one of the most important tasks carried out in manufacturing systems. It is responsible for the scheduling of jobs in machines and the specification of the sequence and time to be carried out of operation. Some productive systems present a special configuration that has been widely studied in the literature. This configuration implies a natural ordering of the machines in the shop in that the jobs go through the same machines in the same order. This type of configuration is called 'flowshop'. In the research literature, production scheduling is usually seen as a function of perfect inputs. The set of orders, capacities of machines, duration of activities and other characteristics of the scheduling problem are assumed to be known and static. Several techniques have been proposed to generate (for a given problem) a unique schedule satisfying shop constraints and providing optimal or nearoptimal performance. However, when this precomputed or predictive schedule is released for execution, continual adaptations are required to take uncertainties into account. These uncertainties are related, for example, to machine breakdowns, staffing problems, the unexpected arrival of new orders, the early or late arrival of raw materials and uncertainties in the duration of processing times [START_REF] Aloulou | An efficient proactive-reactive scheduling approach to hedge against shop floor disturbance[END_REF]. As a result, over the past 20-30 years, one of the most interesting branches of combinatorial optimisation that emerged is robust optimisation. Two new research lines within the operations research community have been initiated with an increasing interest in the use of worst-case optimisation models: disruption management and robust scheduling. In this paper, we deal with the second research line.

Another task closely related to production scheduling in industrial settings is Preventive Maintenance (PM), understood as the operations or techniques that allow the maintenance or restoration of equipment to a specific state and the guarantee of a given service. These activities conflict since PM activities consume potential production time, but delaying PM because of production demands may increase the probability of machine failure.

Usually, scheduling PM operations and production sequencing are dealt with separately in the literature and, therefore, also in the industry. Therefore, little work has been carried out in which PM scheduling and flowshop scheduling are jointly considered [START_REF] Lee | Scheduling jobs and maintenance activities on parallel machines[END_REF][START_REF] Cassady | Minimizing job tardiness using integrated preventive maintenance planning and production scheduling[END_REF][START_REF] Benbouzid | Resolution of joint maintenance/production scheduling by sequential and integrated strategies[END_REF][START_REF] Aggoune | Minimizing the makespan for the flow shop scheduling problem with availability constraints[END_REF][START_REF] Allaoui | Integrating simulation and optimization to scheduling a hybrid flow shop with maintenance constraints[END_REF][START_REF] Ruiz | Considering scheduling and preventive maintenance in the flowshop sequencing problem[END_REF]. There is one account in the literature regarding two joint scheduling strategies [START_REF] Lee | Scheduling jobs and maintenance activities on parallel machines[END_REF] aiming to solve the conflicts between production and maintenance: the sequential strategy that consists of scheduling production jobs, then inserting maintenance tasks, taking production scheduling as a strong constraint, and the integrated strategy that consists of simultaneously scheduling both maintenance and production activities based on their common representation.

In this paper, we develop a model that studies the maintenance contribution to joint production and PM scheduling robustness. In the first step, we build a set of schedules [START_REF] Benbouzid | Resolution of joint maintenance/production scheduling by sequential and integrated strategies[END_REF] restricted to follow a disruption protocol, which allows the comparison of the performances of disrupted joint production and PM schedules to disrupted production ones (without maintenance). Then, we will try to identify from the used optimisation criteria the ones that allow making predictive schedules more robust. The purpose of such a model is to describe the benefits of inserting maintenance activities during production scheduling that can guarantee a minimal robustness threshold.

The rest of the paper is organised as follows. In Section 2, we present a short state-of-the-art concerning both the theoretical and practical aspects of scheduling in the robustness framework. In Section 3, we describe the context of the study: production and maintenance data and the common objective function to optimise. Section 4 introduces our experimental environment through the optimisation criteria used in the tests, then the disruption protocol and disruption algorithm. Section 5 is devoted to the results. Finally, we conclude with some development prospects and extensions to our work.

Literature review

The theory of robustness is a relatively new and fast-developing area of combinatorial optimisation. It deals with the uncertainty of problem parameters. The presence of such parameters in optimisation models is caused by the inaccuracy of initial data, the inadequacy of models to real processes, the errors of numerical methods, rounding-off errors and some other factors. Thus, it appears important to identify the model classes in which small changes on the input data lead to small changes in the results, under the worst possible scenario of problem parameters distribution. During the past 10-20 years, many authors concentrated their work on robust optimisation and related approaches in which one optimises against the worst instances that might arise by using the min-max (or some other) objective.

Robustness in scheduling

In scheduling, it might be important for the disrupted schedule to remain very close to the original one when the release dates are slightly changed and the problem is reoptimised. Two types of robustness are generally mentioned in the literature: quality robustness and solution robustness [START_REF] Sörensen | Tabu searching for robust solutions[END_REF]. A solution is called 'quality robust' if the quality of this solution is relatively insensitive to changes in the problem data. This type of robustness can also be called 'robustness in the objective function space'. A solution is called 'robust' if it remains approximately the same when changes occur in the input data. Many scheduling and rescheduling approaches have been proposed in the literature to take into account the presence of uncertainties (disruptions) in the shop floor [START_REF] Aloulou | An efficient proactive-reactive scheduling approach to hedge against shop floor disturbance[END_REF].

Their aim is to produce schedules that easy recovery or remain feasible after disruption; see, for example, [START_REF] Davenport | A survey of techniques for scheduling with uncertainty[END_REF], [START_REF] Herroelen | Project scheduling under uncertainty -survey and research potentials[END_REF][START_REF] Herroelen | Project scheduling under uncertainty -survey and research potentials[END_REF][START_REF] Jensen | Robust and flexible scheduling with evolutionary computation[END_REF]. These approaches can be classified into four categories: completely reactive scheduling, predictivereactive scheduling, proactive scheduling and proactive-reactive scheduling. Completely reactive approaches are based on up-to-date information regarding the state of the system [START_REF] Davenport | A survey of techniques for scheduling with uncertainty[END_REF]. No predictive schedule is given to the shop floor and decisions are made locally in real time by using priority-dispatching rules. In predictive-reactive approaches, a schedule is generated without considering the possible disruptions. Then, a reactive algorithm is used to maintain the feasibility of the schedule and/or improve its performances [START_REF] Vieira | Rescheduling manufacturing systems: a framework of strategies, policies, and methods[END_REF]. Proactive or robust scheduling takes into account the possible disruptions while constructing the original predictive schedule. This allows making the predictive schedule more robust. A robust schedule is defined by [START_REF] Leon | Robustness measures and robust scheduling for job shops[END_REF] as "a schedule that is insensitive to unforeseen shop floor disruptions given an assumed control policy". This control policy is generally simple. Robust scheduling is appropriate only if, while generating the predictive schedule, uncertainty is known or at least some suspicions about the future are given, thanks to the experience of the decision maker. If uncertainty is completely unknown, a reactive scheduling approach is more suitable. Most of the work related to robustness in the scheduling theory is based on two important factors: the uncertainties taken into account and the used robustness measures. Uncertainties in scheduling may arise from many sources: machine breakdowns, early or late arrival times, uncertainty of processing times, changes in release data, natural and human factors, etc. The most studied uncertainties are related to machine breakdowns [START_REF] Mignon | A framework for investigating schedule robustness under uncertainty[END_REF][START_REF] Sanmarti | Effects of equipment failure uncertainty in batch production scheduling[END_REF][START_REF] Lawrence | Heuristic, optimal, static and dynamic schedules when processing times are uncertain[END_REF][START_REF] Balasubramanian | A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing time[END_REF][START_REF] Alcaide | An approach to solve the minimum expected makespan flowshop problem subject to breakdowns[END_REF]. Nevertheless, some work studying the uncertainty of processing times can be found in [START_REF] Mignon | A framework for investigating schedule robustness under uncertainty[END_REF] and [START_REF] Balasubramanian | A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing time[END_REF]. For robustness measures, authors generally follow one of two classes of experiments: the first uses only one robustness measure and several resolution methods (rescheduling approaches are used), whereas the second class uses one or few resolution methods but relate to several robustness measures. In both classes, the robustness measure is known. No one can guarantee the reliability of input data in the contemporary, dynamic, permanently changing world. This is one reason why almost all modern scheduling techniques try to find a solution (being probably near-optimal, but as close as possible to an optimal one) that is flexible to input data changes.

Robustness and preventive maintenance

In the preceding section, a brief description of the literature concerning both the theoretical and practical aspects of scheduling in the robustness framework was given. Even though production scheduling and PM planning have received considerable attention from manufacturing industries, in practice, these are made independently despite the relationship between them. Therefore, 'preventive maintenance' does not appear in the literature review presented above. All the studied works focus only on production scheduling. PM apparently has a negative impact on the performance of a production system. Given that maintenance affects the available production time and the elapsed production time affects the probability of machine failure, this interdependency seems to be overlooked in the literature. Solving production scheduling and PM planning problems independently ignores these inherent conflicts. Our contention is that manufacturing system productivity would benefit from the integration of these decisions. The goal is to reach a compromise between system performance and equipment reliability. One can measure system reliability without maintenance, knowing that, on the one hand, corrective action never brings the system back to its nominal state and, on the other hand, lots of corrective actions decrease system performance. One can also evaluate the maintenance contribution in the global performance of the system under disruption, which deals with the robustness of the production system. The first proposal has been widely studied in the literature. Some authors studied the impact of maintenance policies on the industrial process [START_REF] Sherwin | A review of overall models for maintenance management[END_REF][START_REF] Vineyard | An evaluation of maintenance policies for flexible manufacturing systems[END_REF]. Others were interested in industrial cases [START_REF] Sanmarti | Effects of equipment failure uncertainty in batch production scheduling[END_REF][START_REF] Ashayeri | A production and maintenance planning model for the process industry[END_REF][START_REF] Alcaide | An approach to solve the minimum expected makespan flowshop problem subject to breakdowns[END_REF]. In this paper, we will investigate the first proposal.

Models and problem statement

In the following subsections, we will first present the production and maintenance data, then the objective functions to optimise.

Formulation of the static permutation flowshop scheduling problem

One of the most frequent production scheduling problems is the Flowshop Problem (FSP), which represents a lot of industrial cases. The FSP can be stated as follows. Each n job 1… n has to be processed on m machines 1… m, in that order. The processing time of job i on machine j is p ij . The processing times are fixed, non-negative and may be 0 if a job is not processed on some machines. Further assumptions are that each job can be processed on only one machine at a time, the operations are not preemptable, the jobs are available for processing at time 0 and set-up times are sequence-independent. Here, we consider the Permutation Flowshop Problem (PFSP), i.e., the same job order is chosen on every machine. The objective is to find a sequence, i.e., a permutation of the numbers 1…n that minimises the completion time C max (makespan) of the last job. In this case, the problem is denoted by F m / /C max following Reeves' (1995) notation. The problem is NP-hard [START_REF] Garey | The complexity of flowshop and jobshop scheduling[END_REF]; only some special cases can be solved efficiently [START_REF] Johnson | Optimal two-and three-stage production scheduling with setup times included[END_REF].

Preventive maintenance and scheduling

Maintenance is understood as any activity carried out on a system to maintain or restore it to a specific state [START_REF] Biroloni | Reliability Engineering, Theory and Practice[END_REF]. Maintenance operations can be classified into two large groups: Corrective Maintenance (CM) and PM. CM is carried out when the failure has already taken place. PM consists of carrying out operations in machines and equipment before the failure or breakdown takes place and at previously established time intervals. The objective of PM is to prevent failures and, therefore, to minimise the probability of failure. The advantage of PM is that the system is always in good condition, thus reducing the risk of unexpected failures. The choice of PM for this study is a consequence of its planned aspect that makes it the most adapted for maintenance scheduling. In this case, the search for a production schedule will be correlated to the search for maintenance planning, which is predefined and easy to implement. PM can be stated as follows. Each machine is maintained periodically at known time intervals. The maintenance tasks are periodic interventions occurring every T periods and each occurrence depends on the one preceding it on the same machine. A maintenance task consists of elementary operations wherein processing time p' is evaluated with more or less certainty. Moreover, the periodicity T of these tasks can vary in a tolerance interval noted [T min , T max ]. This interval gives some flexibility to plan maintenance tasks while respecting the production constraint, disturbing the least possible production schedule and respecting maintenance equipment periodicity. The tolerance interval represents a compromise between the maintenance cost and machine unavailability. If the period is lower than T min (zone 1 in Figure 1), maintenance interventions will be too frequent compared to the machine's real need and, thus, induce a too high maintenance cost. Moreover, if some maintenance tasks are programmed after T max (zone 2 in Figure 1), breakdowns and CM actions are likely to appear. As a result, the machine would be unavailable. This established fact induces a maintenance cost increase and performance loss. However, an intervention planned in interval [T min , T max ] will induce a relatively constant maintenance cost.

Machine j can be subject to several different maintenance tasks which will be repeated periodically. Let:

-M ij : the maintenance task i on the machine j.

-T ij : periodicity of the maintenance task M ij .

-Tmin ij : earliest time separating two consecutive occurrences of M ij ; -Tmax ij : latest time separating two consecutive occurrences of M ij ; -p' ij : processing time of task M ij . It is supposed to be known and constant.

Ideally, a maintenance task is programmed in interval [T min , T max ]. However, it can be programmed before T min and considered advance (this advance is noted E') or programmed after T max and considered late (this delay is noted L'). The earliness and tardiness of the k-th occurrence of maintenance task M ij are computed as follows:

-t' ijk = execution time of the k th occurrence of the maintenance task M ij .

-E' ijk = earliness execution time of the k th occurrence of the maintenance task M ij. E' ijk = max (0, t' ijk +p' ij +Tmin ij -t' ijk-1 ) -L' ijk : Tardiness execution time of the k th occurrence of the maintenance task M ij . L' ijk = max (0, t' ijk-1 -t' ijk -p' ij -Tmax ij )

Figure 1: Tolerance interval of a maintenance task

Objective functions

The goal of joint scheduling is to propose a method that provides common planning for production jobs and maintenance tasks. Thus, the objective of optimisation is to find a compromise between the target objective maintenance and production functions. The constraints imposed by the customers to their suppliers are often expressed in terms of time, which naturally lead us to the minimisation of the makespan. One will note f 1 , the production objective function:

) ( max 1 ij c =Max =C f 1 [1]
We introduced in the preceding section a cost curve that depends on the period wherein maintenance activities are done (time). This curve can be established on the base of a mathematical model. In this study, we investigate the robustness of an integrated production scheduling and PM planning model considering that the respective maintenance activities' periods can be hedged against some machine failure. The purpose of this work is to optimise time, not cost. From the supplier point of view, the respective maintenance periods influence the constraints of the production system. One will note f 2 , the maintenance objective function:

jk m j Maxj k jk L E f ' ' 1 1 2 + = ¦ ¦ = = 2 [2]
To optimise the two criteria, we take into account the following common global objective function:

2 1 f f f β α + = [3]
1 cij is the completation time of task i on the machine j 2 Maxj represents the effective occurrence number of the maintenance task Mj. (˞,˟) are weights that will measure the respective contributions of production and maintenance in the global objective function. The goal is not to study multicriteria optimisation, but only to measure the impact of production or maintenance on the global objective function. For that, parameters ˞ and ˟ can depend on the number of tasks, processing time or problem size. They are independent and noncomplementary.

Experimental environment

The aim of this study is to evaluate the maintenance contribution to the robustness of joint production and maintenance scheduling. For that, we will try to answer the following questions: 1. Does maintenance contribute to scheduling robustness?

The answer to this question will determine if maintenance contributes to joint scheduling robustness. In static environments, the insertion of maintenance tasks in the schedule decrease some optimisation criteria such as makespan because of the delay of some production jobs. But in dynamic environments, where disruptions can occur, it can improve it by optimising machine reliability (a recently maintained machine will have a weak probability of performance degradation).

In this paper, we do not propose robust joint scheduling, but rather to register the generation of joint production and PM schedules as a robust approach. Our goal is to establish that the performance decrease of joint production and PM scheduling after the insertion of maintenance activities is lower than the decrease of production scheduling performance under disruptions.

Do some optimization criteria have any influence on scheduling robustness?

The answer to this question implies the study of the influence of some classical optimisation criteria on scheduling robustness. This question is very important if robust schedules exist, but we can show that neither the maintenance nor scheduling methods influences this robustness. At this time, the goal consists of searching the optimisation criteria under this improvement.

In the following, we will first present the selected optimization criteria for this study. Then, we will introduce our disruption protocol and the disruption algorithm;

Optimization criteria

To answer the second question of this study, we chose the following criteria in the production objective function (Section 3.3) [START_REF] Pinedo | Scheduling: Theory, Algorithms, and Systems, Series in Industrial and Systems Engineering[END_REF]: C max , flow time, idle time, Ti and, for maintenance, the sum of the advances and delays in maintenance (Section 3.3). The global objective function takes into consideration the production optimisation criteria and the maintenance one. The criteria to be optimised in the production objective function were chosen because of the bound existing between them. Of course, if C max varies, the others vary in the same direction.

Disruption protocol

The shop environment is subject to disruptions related to production jobs. We model a disruption as an increase of processing times according to levels and classes. This classification refers to the study of [START_REF] Lawrence | Heuristic, optimal, static and dynamic schedules when processing times are uncertain[END_REF].

In the following subsections, we will first define disruption levels and classes and the concept of overlapping, which is a consequence of tasks disruption. Then, the maintenance effect when disruption occurs is introduced. It is modelled as reliability and disruption intervals.

Definition of disruption levels

A disruption level determines the production job's processing time increase. Ten levels of disruption in processing times were studied. They represent the intervals of possible processing time increases. At each level, the maximum increase of the disturbed task processing time is 10% of the original processing time. This variation is obtained by a coefficient noted CoefPert ij for a task (i,j). This coefficient is generated by a uniform law U. -p ij = processing time -p' ij = new processing time after disruption -t ij : starting time -c ij : completion time.

-CoefPert i: disruption coefficient of the task i.

Definition of disruption classes

A disruption class represents the number of tasks to disturb in the schedule. We define three disruptions classes: weak, average and strong.

Overlapping

The increase of production tasks' processing times can cause overlapping between two or several tasks. An overlap between two tasks is defined as "the interlacing or the superposition of two tasks after the right-shifting of the first one for an unspecified reason". Overlapping can occur between two production jobs or between a production job and a maintenance task. Overlapping can be classified into two large groups (Figure 3): horizontal overlapping, which occurs between two successive tasks on the same machine, and vertical overlapping, which occurs on the same task executed on two successive machines. To solve overlapping, right-shifting rescheduling is applied because it preserves the tasks' execution order. Nevertheless, in the case of joint production and PM scheduling, we will check if the maintenance task is still in its tolerance interval after right shifting. Otherwise, permutations between the production job that caused the overlap and the maintenance one will be done to put it back in its tolerance interval.

Reliability and disruption intervals

After machine maintenance, its reliability will increase and can hedge against several disruptions. We model the maintenance effect on machine reliability by two intervals: a reliability interval (after a PM action on the machine) and a disruption interval that succeeds the reliability one (Figure 4). In the reliability interval, no disruption on the production job's processing time can occur because the machine has been recently maintained and is, therefore, still reliable. This interval is considered maintenance data; it depends only on the machine concerned with maintenance. In the disruption interval, disruptions can occur progressively.

Disruption algorithm

The four steps (generation, disruption, classification and validation) of the algorithm that we propose to study the maintenance contribution to robustness of joint production and PM scheduling under disruption are outlined below. Step 1: Generation We build three sets of near-optimal schedules with a Genetic Algorithm (GA) by following the procedure given by [START_REF] Benbouzid | Resolution of joint maintenance/production scheduling by sequential and integrated strategies[END_REF]. The first set is composed only of production schedules (PGA) resulting from the first step of the sequential strategy. The second one is composed of the joint production and PM schedules resulting from the second step of the sequential strategy (SGA) (after the insertion of maintenance). The last one is also composed of the joint production and PM schedules resulting from the integrated strategy (IGA). The aim of this distinction between the generation strategies of joint scheduling is to see whether the generation method has any influence on schedules' robustness.

Step 2: Disruption A schedule can be disturbed at three different levels, according to the three sets: at the generation of the production schedule (the first step of joint production and PM scheduling generation with the sequential strategy), after the insertion of maintenance tasks (the second step of the sequential strategy) and after the generation of the schedule in the case of the integrated strategy. The schedules of each set are first optimised with the optimisation criteria selected for the study (Section 4.1). As a result, 12 (three sets and four optimisation criteria) primary sets are obtained. Then, all the schedules are disrupted according to the disruption classes and levels defined in Section 4.2. Finally, 12 ⋅ 3 ⋅ 10 sets of disturbed schedules are obtained (12 primary sets disturbed according to the 10 disruption levels and 3 disruption classes). At the end of each disruption process, we compute the differences between the performances of the original schedule and the disturbed one.

In the majority of the experiments in the robustness framework, the loss allowed after disruption is 50% of the original performance. To be able to study the disturbed schedules, we subdivided the loss of performance after the disruptions in intervals and affixed a label to each one. We set 50% as a maximum increase in the objective function. Beyond this value, generating a new schedule will be better. Each interval represents the increase rate of the disturbed schedule performance criterion. The labels and the corresponding performance loss intervals are illustrated in Table 3.

Performance loss Label [0, 5%] Very Good (VG) ] 5%, 15%] Good (G) ] 15%, 35%] Average (A) ] 35%, 50%] Bad (B) > 50%

Very Bad (VB) Table 3

: labels and corresponding intervals

Step 3: Classification The classification process makes it possible to evaluate the maintenance effect on the robustness of joint scheduling and identify the criteria that are likely to improve schedule robustness. For each set, we establish a schedule classification based on their original performance.

Step 4: Validation This step aims to confirm the results of the preceding step. The validation process is applied only when some criteria emerge from the classification process. This validation will be done as follows: we build sets of schedules that will be optimised according to the robust criteria deduced from the validation step. If we obtain the same criteria after the disruption and classification steps, then we can affirm that these criteria are able to improve robustness.

Computational results and discussions

In this section, we present some of the obtained results. The first type of experiments concerns the maintenance effects on robustness of joint production and PM scheduling and their ability to provide to joint production and PM schedules a good tradeoff between reliability and performance under disruption. The experiments show that joint production and PM schedules are more robust than production ones. In the second type, we test the emergence of performance criteria that can improve robustness under disruption. We show that none of the four tested performance criteria are able to improve scheduling robustness. In the following subsections, the generation scheme of the studied problems and the disruptions protocol are detailed. The two types of experiments done for this study are then introduced.

Problem's generation scheme.

The tested problems are generated by following the procedure given by [START_REF] Taillard | Benchmarks for basic scheduling problems[END_REF], [START_REF] Reeves | A genetic algorithm for flowshop sequencing[END_REF] and [START_REF] Carlier | Ordonnancements a contraintes disjonctives[END_REF] for permutation flowshop scheduling problems. These problems have different sizes (from 5 to 100 jobs and from 3 to 20 machines), but do not include maintenance data. For those, we developed a generator of random maintenance tasks to generate benchmarks in PM. The used parameters are the number of machines and the maintenance task parameter (T, T min and T max ). Each parameter is limited by a minimal and a maximum value to avoid having identical values. To carry out our tests, we generated only one maintenance task per machine for each problem. Moreover, the processing time of a maintenance task is identical for all its occurrences. For the search of robustness criteria, production objective function f 1 consists of [START_REF] Pinedo | Scheduling: Theory, Algorithms, and Systems, Series in Industrial and Systems Engineering[END_REF]: makespan (C max ), flow time, Ti and idle time. Maintenance objective function f 2 is the minimisation of the sum of the delays and advances in maintenance (Section 3.1). The contributions of the production and maintenance objective functions in the global objective function f are equal to 1 (˞ = 1 and ˟ = 1). The proposed common-weighted global objective function will allow tackling the problem in a simplified way. Each schedule was generated with a GA. The results of the GA are obtained after 100 executions of the method. The best result and the associated parameters are saved.

Problem's disruption scheme.

In this study, we consider production jobs' processing time disruption. We used two types of reliability intervals (Section 3.4.2) that represent a percentage of maintenance task periodicity T: 5 and 25% of T. The disruptions are generated according to levels and classes. We generated 20 schedules per set. For each set, all the schedules were optimised with the four optimisation criteria selected for this study (3 sets ⋅ 20 schedules ⋅ 4 criteria). Then, the schedules were disturbed according to the defined classes and levels (10 ⋅ 3). For each disruption scheme (a specified schedule optimised with a specified criterion, then disrupted according to a class and a level), we did 100 tests and took the average performance into account. To ease the classification step, we qualify as an acceptable schedule any schedule whose deviation of its original performance remains in an acceptable interval after experimentation. Its labels are then either Very Good (VG), Good (G) or Average (A). It is rejected if the obtained label after experimentation is Bad (B) or Very Bad (VB). In the following subsections, we present the results of the two experiments carried out. We notice that the joint production and PM schedules perform better than the production one. That confirms the maintenance contribution to joint schedules' robustness. For all the benchmarks studied, we notice that the performance loss of disturbed joint schedules is less than the production ones. Approximately 75% of the disturbed production schedules (all levels and classes were considered) are rejected. Moreover, 25% of the remaining cases have only A or G labels. On the other hand, in the case of joint production and PM schedules, approximately 55% of the cases for SGA and 64% of the cases for IGA are acceptable. The performance of joint disturbed schedules decreases starting from a high disruption protocol (high disruption class and level) compared to the production disturbed ones. Therefore, there is an increase in the percentage of acceptable joint schedules compared to the production ones.

Maintenance contribution to joint scheduling robustness

The results for the second reliability interval (25% of T) are better than the first one (5% of T) because the first interval is larger and so is the period where no disruptions are allowed after maintenance. For the reliability interval 5% of T, the distributions of SGA and IGA sets are almost similar. For the second interval, the IGA set gives the best results for small benchmarks and the SGA set, for large ones. Finally, it is important to note that the results of the small benchmarks (SGA and IGA) are better than those of large ones. The reason for this good performance is related to the number of machines and tasks. Even for the lowest disruption levels and classes, the large benchmark disruption (lots of tasks) decreases in a significant way. The percentage of average acceptable cases for small benchmarks is 65% against 55% for the largest acceptable cases.

As a conclusion, according to the experiments presented in this part of our study, joint production and PM schedules (SGA and IGA) generate more acceptable cases than production ones (PGA) without considering the benchmark size. The insertion of maintenance tasks in production schedules decreases its performance (while remaining in acceptable limits), but it also brings an unquestionable profit in terms of robustness.

As joint production and PM schedules perform better than production schedules, we will restrict the second experiment to joint production and PM sets. We notice that the flow time and idle time are the criteria that obtain the best results. C max and Ti are the two most unfavourable criteria with regard to robustness. The disruption process acts on the increase of jobs' processing time. To solve the conflicts that disruptions generate, we use right-shifting rescheduling. It consists of shifting tasks to the right until the conflict generated by disruption is solved. The criteria whose performance worsens more with this technique are C max and Ti.

Criterion whose optimization makes schedules robust

Two points are to be noted:

• The first relates to the reliability interval. On the one hand, we notice an improvement in the percentage of acceptable cases without modifying the general distribution. On the other hand, in the case of the reliability interval of 25% of T, one notes a clear deterioration of Ti.

• The second one relates to benchmark size. For small benchmarks, the flow time and idle time are most favourable to robustness. For large benchmarks, the distribution of the four criteria is similar and unfavourable to robustness. We obtain the same conclusions for the IGA set. Even though the flow time and idle time give the best results, they remain completely dependent on the disruption protocol and benchmark size. It explains the result of 100% acceptable cases for small benchmarks. The robustness criteria emerge only for the first levels of disruption and weak or average classes. Indeed, there are two tendencies in Figure 7. The first shows that the results of small benchmarks are better than those of large benchmarks. For the second tendency, one notes a clear deterioration of certain criteria (C max and Ti).

Finally, the results with a reliability interval of 25% of T are better however it do not have any influence on the general tendency of the distribution. The flow time and idle time obtain the greatest number of acceptable labels because in the majority of the cases, they have VG and G labels regardless of disruption levels and classes.

The large benchmarks are sensitive to disruptions because the important number of tasks limits schedule flexibility under disruptions. Moreover, as the disruption level and the number of disturbed tasks grow, schedule performance becomes worse. However, if the benchmark is small (few machines and few tasks), the flow time and idle time become important because they represent the flexibility suitable for hedging against some disruptions, making the schedule more robust. As a conclusion, for the second experiment, there is no robust criterion among the selected ones. We cannot confirm the emergence of a criterion that ensures a robustness threshold for joint production and PM scheduling. There will be no validation process for this classification.

The studied criteria remain completely dependent on the disruption protocol and benchmark sizes. We can only note that the flow time and idle time obtained the best labels for the two studied sets. Also, the results of the IGA set are better than those of the SGA set.

For the reliability interval, the results for interval 25% T are better for the flow time and idle time. But there is a clear deterioration of C max and Ti.

Conclusion

We considered in this paper the joint production and PM scheduling problem in the permutation flowshop and some optimisation criteria as production objective functions. The shop environment is subject to disruptions related to production jobs' processing time.

We proposed a proactive approach to study the maintenance effect on the robustness of joint production and PM scheduling. We used three different sets of schedules generated with GAs in the permutation flowshop: a set of production schedules and two sets of joint production and PM schedules. The first was generated by the sequential strategy and the second, by the integrated strategy. We defined disruption classes and levels to study the variation of the schedules' performances under disruptions. Four performance criteria have been used to study their influence on the schedules' robustness.

Several tests were performed to evaluate the maintenance effect on joint production and PM schedules under disruptions and the use of the proposed approach in permutation flowshop conditions.

The first type of experiment concerned the maintenance effects on the robustness of joint production and PM schedules and their ability to provide to a good tradeoff between reliability and performance.

The experiments showed that joint production and PM schedules are more robust than production schedules and maintenance allows providing an acceptable trade-off between equipment reliability and performance loss under disruption.

In the second type of experiment, we tested the emergence of performance criteria that can improve robustness under disruption. We showed that none of the four tested performance criteria are able to improve scheduling robustness. However, by making distinctions during simulations between the results obtained by large and small benchmarks, the results showed that for small benchmarks, the flow time and idle time gave the best results. For this work, several improvements can be made at the level of the implemented methods and at the level of the considered constraints:

• Future researches can study the impact of the weights on the obtained results and how sensitive the results are with regard to the chosen weights. We can investigate a bicriteria optimisation choosing ˞ + ˟ = 1. • The results obtained for flowshop scheduling problems gave us some insight to extend our approach to more complex scheduling problems.

Figure 2 :

 2 Figure 2: Processing time of a disturbed job

Figure 3 :

 3 Figure 3: Horizontal and Vertical overlapping between two tasks

Figure 4 :

 4 Figure 4: Reliability and disruption intervals

Figure 5 Figure 5 :

 55 Figure5presents the distribution of acceptable cases for the three studied sets: PGA, SGA and IGA.

Figure 6 Figure 6 :

 66 Figure6presents the distribution of the percentage of acceptable cases by performance criterion and reliability interval for SGA sets, regardless of the disruption levels and classes.5% of T*

Figure 7 Figure 7 :

 77 Figure7presents the distribution of the percentage of acceptable cases by performance criterion and reliability interval for IGA sets, regardless of disruption levels and classes.

  Table 1 defines the disruptions levels and the uniform variable associate with each level.

					Level	Interval	Variation
					1				] 0%, 10%]	CoefPert 1 Î U [0, 0.1]
					2				] 10%, 20%]	CoefPert 2 Î U [0.1, 0.2]
					.				.
					.				.
					.				.
					9				] 80%, 90%]	CoefPert 9 Î U [0.8, 0.9]
					10			] 90%, 100%]	CoefPert 10 Î U [0.9, 1]
										Table 1: Disruption levels
	Figure 2 illustrates the new processing time (P' i ) of a disturbed job defined as:
	i P	'	=	i P	×	1 (	+	i CoefPert	)
	With:

Table 2 :

 2 Table 2 gives the number of disturbed tasks in the schedule for each class. Disruption classes

	Class	Interval of variation	Number of disturbed tasks
	Weak	[0%, 40%]	u Î U [0, 0.4] / n x u disturbed tasks
	Average	] 40%, 70%]	u Î U] 0.4, 0.7] / n x u disturbed tasks
	strong	] 70%, 100%]	u Î U] 0.7, 1] / n x u disturbed tasks
			n: number of tasks

Acknowledgements

I would like to thank Dr. Ing Mouloud Koudil and Dr. Ing Karima Benatchchba, associate professors at Ecole nationale Supérieure (ESI ex INI) of Algiers (Algeria), for their contributions and help.