Nicolas Dutertre
email: dutertre@cmi.univ-mrs.fr

Nivaldo G Grulha

L Ê-GREUEL TYPE FORMULA FOR THE EULER OBSTRUCTION AND APPLICATIONS

Lê-Greuel type formula for the Euler obstruction and applications

Introduction

Let f : (C n , 0) → (C, 0) be an analytic function defined in a neighborhood of the origin. The Milnor fiber is the set f -1 (δ) ∩ B ε , where δ is a regular value of f , B ε is the euclidian ball in C n of radius ε and where 0 < |δ| ≪ ε ≪ 1. Many research works have been devoted to the study of the topology of the Milnor fiber. When f has an isolated critical point at the origin, Milnor [START_REF] Milnor | Singular points of complex hypersurfaces[END_REF] proved that f -1 (δ) ∩ B ε had the homotopy type of a wedge of spheres of dimension n -1. The number of spheres appearing in this wedge is called the Milnor number of f and is denoted by µ(f ). Milnor showed that µ(f ) was equal to the topological degree of the map ∇f ∇f : S ε → S 1 , where S ε and S 1 are the euclidian spheres in C n of radius ε and 1. Therefore µ(f ) is equal to the dimension of the C-algebra

O C n ,0 ( ∂f ∂x 1 ,..., ∂f ∂xn )
, where O C n ,0 is the algebra of holomorphic germs at the origin, and also to the number of critical points of a Morsification of f . Milnor's results were extended to the case of a complete intersection with isolated singularity F = (f 1 , . . . , f k ) : (C n , 0) → (C k , 0), 1 < k < n, by Hamm [START_REF] Hamm | Lokale topologische Eigenschaften komplexer Raume[END_REF], who proved that the Milnor fiber F -1 (δ) ∩ B ε , 0 < |δ| ≪ ε ≪ 1, had the homotopy type of a wedge of µ(F ) spheres of dimension nk. Lê [START_REF]Calcul du nombre de Milnor d'une singularité isolée d'intersection complète[END_REF] and Greuel [START_REF] Greuel | Der Gauss-Manin Zusammenhang isolierter Singularitäten von vollständingen Durschnitten[END_REF] proved the following formula:

µ(F ′ ) + µ(F ) = dim C O C n ,0 I ,
Mathematics Subject Classification (2010) : 14B05, 32C18, 58K45 N. Dutertre is supported by Agence Nationale de la Recherche (reference ANR-08-JCJC-0118-01) N. G. Grulha Jr. is supported by Fundação de Amparo à Pesquisa do Estado de São Paulo (reference 2009/08774-0).

where F ′ : (C n , 0) → (C k-1 , 0) is the map with components f 1 , . . . , f k-1 and I is the ideal generated by f 1 , . . . , f k-1 and the (k × k)-minors ∂(f 1 ,...,f k ) ∂(x i 1 ,...,x i k ) . If we denote by Γ F the set of points where all these minors vanish then the above formula can be reformulated as follows:

µ(F ′ ) + µ(F ) = I C n ,0 ({F ′ = 0}, Γ F ),
where I C n ,0 (-, -) is the intersection multiplicity at the origin in C n . When F ′ = f : (C n , 0) → (C, 0) and F = (f, l), where l is a generic linear function, the above formula is also called Teissier's lemma [START_REF] Teissier | Introduction to equisingularity problems[END_REF]. Note also that in this situation µ(f, l) is equal to the first Milnor-Teissier number µ ′ (f ), namely the Milnor number of f restricted to a generic hyperplane. Using Teissier's lemma and tools from integral geometry, Langevin [START_REF] Langevin | Courbure et singularités complexes[END_REF] gave an integral formula for the sum µ(f )+µ ′ (f ). In [START_REF] Kennedy | Integral formula for the Milnor number[END_REF], Kennedy carried on Langevin's work and established an integral formula for the Milnor number µ(f ) (see also [START_REF] Loeser | Formules intégrales pour certains invariants locaux des espaces analytiques complexes[END_REF] for other integral formulas).

Our aim in this paper is to generalize some of the previous results to the singular case, namely to replace C n with an equidimensional reduced complex analytic space X. There exist several generalizations of the Milnor number of a function defined on a singular space. We will use the local Euler obstruction of a function defined in [START_REF] Brasselet | Euler obstruction and defects of functions on singular varieties[END_REF].

Let us recall first that the local Euler obstruction at a point p of an algebraic variety X, denoted by Eu X (p), was defined by MacPherson. It is one of the main ingredients in his proof of Deligne-Grothendieck conjecture concerning existence of characteristic classes for complex algebraic varieties [START_REF]Chern classes for singular algebraic varieties[END_REF]. An equivalent definition was given in [START_REF] Brasselet | Sur les classes de Chern d'un ensemble analytique complexe[END_REF] by J.-P. Brasselet and M.-H. Schwartz, using stratified vector fields.

The computation of local Euler obstruction is not so easy by using the definition. Various authors propose formulae which make the computation easier. Lê D.T. and B. Teissier provide a formula in terms of polar multiplicities [START_REF] Teissier | Variétés polaires Locales et classes de Chern des variétés singulières[END_REF].

In the paper [START_REF] Brasselet | Euler obstruction and indices of vector fields[END_REF], J.-P. Brasselet, Lê D. T. and J. Seade give a Lefschetz type formula for the local Euler obstruction. The formula shows that the local Euler obstruction, as a constructible function, satisfies the Euler condition relatively to generic linear forms. A natural continuation of the result is the paper by J.-P. Brasselet, D. Massey, A. J. Parameswaran and J. Seade [START_REF] Brasselet | Euler obstruction and defects of functions on singular varieties[END_REF], whose aim is to understand what is the obstacle for the local Euler obstruction to satisfy the Euler condition relatively to analytic functions with isolated singularity at the considered point. That is the role of the so-called local Euler obstruction of f , denoted by Eu f,X (0).

In this paper we introduce the number B f,X (0) = Eu X (0) -Eu f,X (0). When f is linear and generic, it gives Eu X (0), hence B f,X (0) can be viewed as a generalization of the Euler obstruction, as it was first remarked by Jean-Paul Brasselet. Using the number B f,X (0), we give a version of the Lê-Greuel formula for germs f : (X, 0) → (C, 0) and g : (X, 0) → (C, 0) of analytic functions with isolated singularity at the origin (Theorem 6.1).

Namely we prove:

B f,X (0) -B f,X g (0) = (-1) d I X,0 (X f , Γ q f,g ),
where

X f = X ∩ f -1 (0), X g = X ∩ g -1 (0) and I X,0 (X f , Γ q f,g
) is the intersection multiplicity at the origin of X f and the following polar set:

Γ q f,g = x ∈ V i | rank(df |Vq (x), dg |Vq (x)) < 2 . Here V q = X reg is the set of smooth points of X.
When g is a generic linear function, we obtain a singular version of Teissier's lemma (Theorem 6.5). As a corollary of this singular Teissier's lemma, we express B f,X (0) in terms of relative polar multiplicities (Theorem 6.6), in the spirit of the formula of Lê and Teissier mentioned above.

Then, using this last result and results of Loeser [START_REF] Loeser | Formules intégrales pour certains invariants locaux des espaces analytiques complexes[END_REF], we also present an integral formula for B f,X (0), generalizing the formula of Kennedy (Corollary 6.7) and a Gauss-Bonnet formula for the Milnor fiber of f (Corollary 6.8).

The paper is organized as follows : in Section 2, we recall some facts about the Euler obstruction, the Euler obstruction of a function and the Euler obstruction of a 1-form. In Section 3, we give the definition of the complex link, the definition of the radial index of a 1-form and a useful relation due to Ebeling and Gusein-Zade between these two notions and the Euler obstruction of a 1-form (Theorem 3.6). Section 4 is devoted to the proof of an auxiliary lemma in subanalytic geometry. In Section 5, we present two versions of the Lê-Greuel formula (Theorem 5.2 and Corollary 5.3) that we will use in the proof of our main results. We also give an application to 1-parameter deformations (Corollary 5.6). Section 6 contains the main results mentioned above.

Our result concern functions with isolated singularities, it would be interesting to try to generalize them to the non-isolated singularity case, using for instance technics of D. Massey [START_REF] Massey | Lê cycles and hypersurface singularities[END_REF].

The authors are grateful to M.A.S Ruas for suggesting them the application to 1-parameter deformations, and to J.-P. Brasselet for his careful reading and for suggesting some improvements in this paper.

The Euler obstruction

The Euler obstruction was defined by MacPherson [START_REF]Chern classes for singular algebraic varieties[END_REF] as a tool to prove the conjecture about existence and unicity of the Chern classes in the singular case. Since that the Euler obstruction was deeply investigated by many authors as Brasselet, Schwartz, Sebastiani, Lê, Teissier, Sabbah, Dubson, Kato and others. For an overview about the Euler obstruction see [START_REF] Brasselet | Local Euler obstruction, old and new[END_REF][START_REF] Brasselet | Local Euler obstruction, old and new II[END_REF]. Let us now introduce some objects in order to define the Euler obstruction.

For all this paper, let us consider the following setting. Let (X, 0) ⊂ (C N , 0) be an equidimensional reduced complex analytic germ of dimension d in an open set U ⊂ C N . We consider a complex analytic Whitney stratification {V i } of U adapted to X and we assume that {0} is a stratum. We choose a small representative of (X, 0) such that 0 belongs to the closure of all the strata. We will denote it by X and we will write X = ∪ q i=0 V i where V 0 = {0} and V q = X reg , the set of smooth points of X. We will assume that the strata V 0 , . . . , V q-1 are connected and that the analytic sets V 0 , . . . , V q-1 are reduced. We will set d i = dimV i for i ∈ {1, . . . , q} (note that d q = d).

Let G(d, N ) denote the Grassmanian of complex d-planes in C N . On the regular part X reg of X the Gauss map φ : X reg → U ×G(d, N ) is well defined by φ(x) = (x, T x (X reg )).

Definition 2.1. The Nash transformation (or Nash blow up) X of X is the closure of the image Im(φ) in U × G(d, N ). It is a (usually singular) complex analytic space endowed with an analytic projection map ν : X → X which is a biholomorphism away from ν -1 (Sing(X)) .

The fiber of the tautological bundle T over G(d, N ), at the point P ∈ G(d, N ), is the set of the vectors v in the d-plane P . We still denote by T the corresponding trivial extension bundle over U × G(d, N ). Let T be the restriction of T to X, with projection map π. The bundle T on X is called the Nash bundle of X.

An element of T is written (x, P, v) where x ∈ U , P is a d-plane in C N based at x and v is a vector in P . We have the following diagram:

T ֒→ T π ↓ ↓ X ֒→ U × G(d, N ) ν ↓ ↓ X ֒→ U.
Let us recall the original definition of the Euler obstruction, due to Mac-Pherson [START_REF]Chern classes for singular algebraic varieties[END_REF]. Let z = (z 1 , . . . , z N ) be local coordinates in C N around {0}, such that z i (0) = 0. We denote by B ε and S ε the ball and the sphere centered at {0} and of radius ε in C N . Let us consider the norm z

= √ z 1 z 1 + • • • + z N z N .
Then the differential form ω = d z 2 defines a section of the real vector bundle T (C N ) * , cotangent bundle on C N . Its pull back restricted to X becomes a section denoted by ω of the dual bundle T * . For ε small enough, the section ω is nonzero over ν -1 (z) for 0 < z ≤ ε. The obstruction to extend ω as a nonzero section of

T * from ν -1 (S ε ) to ν -1 (B ε ), denoted by Obs( T * , ω) lies in H 2d (ν -1 (B ε ), ν -1 (S ε ); Z). Let us denote by O ν -1 (Bε),ν -1 (Sε) the orientation class in H 2d (ν -1 (B ε ), ν -1 (S ε ); Z).
Definition 2.2. The local Euler obstruction of X at 0 is the evaluation of Obs( T * , ω) on O ν -1 (Bε),ν -1 (Sε) , i.e:

Eu X (0) = Obs( T * , ω), O ν -1 (Bε),ν -1 (Sε) .
An equivalent definition of the Euler obstruction was given by Brasselet and Schwartz in the context of vector fields [START_REF] Brasselet | Sur les classes de Chern d'un ensemble analytique complexe[END_REF].

We will need in this paper some results about the Euler obstruction where this invariant is computed using hyperplane sections. The idea of studying the Euler obstruction using hyperplane sections appears in the works of Dubson and Kato, but the approach we follow here is that of [START_REF] Brasselet | Euler obstruction and indices of vector fields[END_REF][START_REF] Brasselet | Euler obstruction and defects of functions on singular varieties[END_REF]. Theorem 2.3 ([3]). Let (X, 0) and {V i } be given as before, then for each generic linear form l, there is ε 0 such that for any ε with 0 < ε < ε 0 and t 0 = 0 sufficiently small, the Euler obstruction of (X, 0) is equal to:

Eu X (0) = q i=1 χ V i ∩ B ε ∩ l -1 (δ) • Eu X (V i ),
where χ denotes the Euler-Poincaré characteristic, Eu X (V i ) is the value of the Euler obstruction of X at any point of V i , i = 1, . . . , q, and 0 < |δ| ≪ ε ≪ 1.

We define now an invariant introduced by Brasselet, Massey, Parameswaran and Seade in [START_REF] Brasselet | Euler obstruction and defects of functions on singular varieties[END_REF], which measures in a way how far the equality given in Theorem 2.3 is from being true if we replace the generic linear form l with some other function on X with at most an isolated stratified critical point at 0. So let f : X → C be a holomorphic function which is the restriction of a holomorphic function

F : U → C. A point x in X is a critical point of f if it is a critical point of F |V (x)
, where V (x) is the stratum containing x. We will assume that f has an isolated singularity (or an isolated critical point) at 0, i.e that f has no critical point in a punctured neighborhood of 0 in X. In order to define the new invariant the authors constructed in [START_REF] Brasselet | Euler obstruction and defects of functions on singular varieties[END_REF] a stratified vector field on X, denoted by ∇ X f . This vector field is homotopic to ∇F | X and one has ∇ X f (x) = 0 unless x = 0.

Let ζ be the lifting of ∇ X f as a section of the Nash bundle T over X without singularity over ν

-1 (X ∩S ε ). Let O( ζ) ∈ H 2n ν -1 (X ∩B ε ), ν -1 (X ∩ S ε ) be the obstruction cocycle to the extension of ζ as a nowhere zero section of T inside ν -1 (X ∩ B ε ). Definition 2.4. The local Euler obstruction Eu f,X (0) is the evaluation of O( ζ) on the fundamental class of the pair (ν -1 (X ∩ B ε ), ν -1 (X ∩ S ε )).
The following result compares the Euler obstruction of the space X with that of a function on X [START_REF] Brasselet | Euler obstruction and defects of functions on singular varieties[END_REF].

Theorem 2.5. Let (X, 0) and {V i } given as before and let f : (X, 0) → (C, 0) be a function with an isolated singularity at 0. For 0 < |δ| ≪ ε ≪ 1 we have:

Eu f,X (0) = Eu X (0) - q i=1 χ V i ∩ B ε ∩ f -1 (δ) • Eu X (V i ) .
Using the notation defined in the introduction, we have:

B f,X (0) = q i=1 χ V i ∩ B ε ∩ f -1 (δ) • Eu X (V i ).
In [START_REF] Seade | Milnor Numbers and Euler obstruction[END_REF], J. Seade et al. show that the Euler obstruction of f is closely related to the number of Morse points of a Morsification of f , as it is stated in the next proposition.

Proposition 2.6 ([29]

). Let f : (X, 0) → (C, 0) be the germ of an analytic function with isolated singularity at the origin. Then:

Eu f,X (0) = (-1) d n reg ,
where n reg is the number of Morse points in X reg in a stratified morsification of f .

Let us consider the Nash bundle T on X. The corresponding dual bundles of complex and real 1-forms are denoted, respectively, by T * → X and T * R → X. Definition 2.7. Let (X, 0) and {V α } as before. Let ω be a (real or complex) 1-form on X, i.e., a continuous section of either

T * R C N | X or T * C N | X .
A singularity of ω in the stratified sense means a point x where the kernel of ω contains the tangent space of the corresponding stratum.

This means that the pull back of the form to V α vanishes at x. Given a section η of

T * R C N | A , A ⊂ V , there is a canonical way of constructing a section η of T * R | Ã, Ã = ν -1
A, such that if η has an isolated singularity at the point 0 ∈ X (in the stratified sense), then we have a never-zero section η of the dual Nash bundle

T * R over ν -1 (S ε ∩ X) ⊂ X. Let o(η) ∈ H 2d (ν -1 (B ε ∩X), ν -1 (S ε
∩X); Z) be the cohomology class of the obstruction cycle to extend this to a section of T * R over ν -1 (B ε ∩ X). Then we can define (c.f. [START_REF] Ebeling | Radial index and Euler obstruction of a 1-form on a singular variety[END_REF]):

Definition 2.8. The local Euler obstruction of the real differential form η at an isolated singularity is the integer Eu X,0 η obtained by evaluating the obstruction cohomology class o(η) on the orientation fundamental cycle

[ν -1 (B ε ∩ X), ν -1 (S ε ∩ X)].
MacPherson's local Euler obstruction Eu X (0) corresponds to taking the differential ω = d z 2 of the square of the function distance to 0.

In the complex case, one can perform the same construction, using the corresponding complex bundles. If ω is a complex differential form, section of T * C N | A with an isolated singularity, one can define the local Euler obstruction Eu X,0 ω. Notice that, as explained in [START_REF] Brasselet | Vector fields on singular varieties[END_REF] p.151, it is equal to the local Euler obstruction of its real part up to sign:

Eu X,0 ω = (-1) d Eu X,0 Re ω.
This is an immediate consequence of the relation between the Chern classes of a complex vector bundle and those of its dual. Remark also that when we consider the differential of a function f , we have the following equality (see [START_REF] Ebeling | Radial index and Euler obstruction of a 1-form on a singular variety[END_REF]):

Eu X,0 df = (-1) d Eu f,X (0). We note that the idea to consider the (complex) dual Nash bundle was already present in [START_REF] Sabbah | Quelques remarques sur la géométrie des espaces conormaux[END_REF], where Sabbah introduces a local Euler obstruction Eǔ X (0) that satisfies Eǔ X (0) = (-1) d Eu X (0). See also [28, sec. 5.2].

The complex link and the radial index

In this section, we recall the definition of the complex link and of the radial index. We also present a formula of Ebeling and Gusein-Zade which expresses the radial index of a 1-form in terms of Euler characteristics of complex links and Euler obstructions.

The complex link is an important object in the study of the topology of complex analytic sets. It is analogous to the Milnor fibre and was studied first in [START_REF]Vanishing cycles on complex analytic sets[END_REF]. It plays a crucial role in complex stratified Morse theory (see [START_REF] Goresky | Stratified Morse theory[END_REF]) and appears in general bouquet theorems for the Milnor fibre of a function with isolated singularity (see [START_REF]Complex analytic functions with isolated singularities[END_REF][START_REF] Siersma | A bouquet theorem for the Milnor fibre[END_REF][START_REF] Tibar | Bouquet decomposition of the Milnor fibre[END_REF]). It is related to the multiplicity of polar varieties and also the local Euler obstruction (see [START_REF] Dubson | Classes caractéristiques des variétés singulières[END_REF][START_REF] Dubson | Calcul des invariants numériques des singularités et applications[END_REF][START_REF] Teissier | Variétés polaires Locales et classes de Chern des variétés singulières[END_REF][START_REF] Teissier | Cycles évanescents, sections planes et conditions de Whitney II, Singularities[END_REF]). Let us recall briefly its definition. Let M be a complex analytic manifold equipped with a Riemannian metric and let Y ⊂ M be a complex analytic variety equipped with a Whitney stratification. Let V be a stratum of Y and let p be a point in V . Let N be a complex analytic submanifold of M which meets V transversally at the single point p. By choosing local coordinates on N , in some neighborhood of p we can assume that N is an Euclidian space C k . Definition 3.1. The complex link of V in Y is the set denoted by lk C (V, Y ) and defined as follows:

lk C (V, Y ) = Y ∩ N ∩ B ε ∩ l -1 (δ),
where l : N → C is a generic linear form and 0 < |δ| ≪ ε ≪ 1.

The fact that the link of a stratum is well-defined, i.e independent of all the choices made to define it, is explained in [START_REF] Teissier | Cycles évanescents, sections planes et conditions de Whitney II, Singularities[END_REF][START_REF] Dubson | Calcul des invariants numériques des singularités et applications[END_REF][START_REF] Goresky | Stratified Morse theory[END_REF]. It is also independent of the embedding of the analytic variety Y (see [START_REF] Teissier | Cycles évanescents, sections planes et conditions de Whitney II, Singularities[END_REF]). Now let H be a smooth analytic hypersurface of M transverse to Y . The intersections of H with the stratum of Y give a Whitney stratification of Y ∩ H. We will need the following lemma.

Lemma 3.2. Let V be a stratum of Y such that V ∩ H = ∅. We have lk C (V, Y ) = lk C (V ∩ H, Y ∩ H). Proof. Let p be a point in V ∩ H. Let N ⊂ H be a complex analytic manifold of dimension dim H-dim(V ∩H) that intersects V ∩H transversally at p in H. Since H intersects V transversally, we have: dim H -dim(V ∩ H) = dim M -1 -(dim V -1) = dim M -dim V.
Hence N intersects V transversally at p in M as well. We conclude remarking that

Y ∩ N = Y ∩ H ∩ N because N ⊂ H.
In [START_REF] Ebeling | Radial index and Euler obstruction of a 1-form on a singular variety[END_REF], Ebeling and Gusein-Zade established relations between the local Euler obstruction of a 1-form, its radial index and Euler characteristics of complex links. The radial index is a generalization to the singular case of the Poincaré-Hopf index. In order to define this index, let us consider first the real case. Let Z ⊂ R n be a closed subanalytic set equipped with a Whitney stratification {S α } α∈Λ . Let ω be a continuous 1-form defined on R n . We say that a point P in Z is a zero (or a singular point) of ω on Z if it is a zero of ω |S , where S is the stratum that contains P . In the sequel, we will define the radial index of ω at P , when P is an isolated zero of ω on Z. We can assume that P = 0 and we denote by S 0 the stratum that contains 0. Definition 3.3. A 1-form ω is radial on Z at 0 if, for an arbitrary nontrivial subanalytic arc ϕ : [0, ν[→ Z of class C 1 , the value of the form ω on the tangent vector φ(t) is positive for t small enough.

Let ε > 0 be small enough so that in the closed ball B ε , the 1-form has no singular points on Z \ {0}. Let S 0 , . . . , S r be the strata that contain 0 in their closure. Following Ebeling and Gusein-Zade, there exists a 1-form ω on R n such that :

(1) The 1-form ω coincides with the 1-form ω on a neighborhood of S ε .

(2) The 1-form ω is radial on Z at the origin.

(3) In a neighborhood of each zero

Q ∈ Z ∩ B ε \ {0}, Q ∈ S i , dim S i =
k, the 1-form ω looks as follows. There exists a local subanalytic diffeomorphism h

: (R n , R k , 0) → (R n , S i , Q) such that h * ω = π * 1 ω1 + π * 2 ω2
where π 1 and π 2 are the natural projections π 1 : R n → R k and π 2 : R n → R n-k , ω1 is a 1-form on a neighborhood of 0 in R k with an isolated zero at the origin and ω2 is a radial 1-form on R n-k at 0. Definition 3.4. The radial index ind R Z,0 ω of the 1-form ω on Z at 0 is the sum:

1 + r i=0 Q|ω |S i (Q)=0 ind P H (ω, Q, S i ),
where ind P H (ω, Q, S i ) is the Poincaré-Hopf index of the from ω|S i at Q and where the sum is taken over all zeros of the 1-form ω on (Z \ {0}) ∩ B ε . If 0 is not a zero of ω on Z, we put ind R Z,0 ω = 0. A straightforward corollary of this definition is that the radial index satisfies the law of conservation of number (see Remark 9.4.6 in [START_REF] Brasselet | Vector fields on singular varieties[END_REF] or the remark before Proposition 1 in [START_REF] Ebeling | Radial index and Euler obstruction of a 1-form on a singular variety[END_REF]).

Let us go back to the complex case. As in Section 2, (X, 0) ⊂ (C N , 0) is an equidimensional reduced complex analytic germ of dimension d in an open set U ⊂ C N . Let ω be a complex 1-form on U with an isolated singular point on X at the origin. Definition 3.5. The complex radial index ind C X,0 ω of the complex 1-form ω on X at the origin is (-1) d times the index of the real 1-form given by the real part of ω.

Let us denote n

i = (-1) d-d i -1 χ lk C (V i , X) -1 ,
where {V i } is the Whitney stratification of (X, 0) considered in Section 2. In particular for a open stratum V i of X, lk C (V i , X) is empty and so n i = 1. Let us define the Euler obstruction Eu Y,0 (ω) to be equal to 1 for a zero-dimensional variety Y . Under this conditions Ebeling and Gusein-Zade proved in [START_REF] Ebeling | Radial index and Euler obstruction of a 1-form on a singular variety[END_REF] the following result which relates the radial index of a 1-form to Euler obstructions. Theorem 3.6. Let (X, 0) ⊂ (C N , 0) be the germ of a reduced complex analytic space at the origin, with a Whitney stratification {V i }, i = 0, . . . , q, where V 0 = {0} and V q is the regular part of X. Then

ind C X,0 ω = q i=0 n i • Eu V i ,0 ω.

A lemma in subanalytic geometry

Let Y ⊂ R n be a closed subanalytic set equipped with a locally finite subanalytic Whitney stratification {S i } α∈Λ : Y = ∪S i . Let ρ : R n → R be a smooth subanalytic function such that ρ -1 (a) intersects Y transversally (in the stratified sense). Then the following partition: Let ρ : R n → R be defined by ρ

Y ∩ {ρ ≤ a} = S i ∩ {ρ < a} ∪ S i ∩ {ρ = a},
(x) = x 2 1 + • • • + x 2 n .
It is known that for ε > 0 small enough, the sphere S ε = ω -1 (ε 2 ) intersects Y transversally. Let p ε be a critical point of θ |Y ∩Sε . This means that there exists λ(p ε ) such that:

∇θ |S (p ε ) = λ(p ε )∇ρ |S (p ε ),
where S is the stratum containing p ε . Note that λ(p ε ) = 0 since θ has no critical point on U \ {0} ∩ S.

Lemma 4.2. If ε is small enough then θ(p ε ) = 0. Furthermore p ε is outward-pointing (resp. inward-pointing) for θ |Y ∩Bε if and only if θ(p ε ) > 0 (resp. θ(p ε ) < 0).

Proof. If for ε small enough, there is a critical point p ε of θ |Y ∩S ε such that θ(p ε ) = 0 then by the Curve Selection Lemma, there is a smooth subanalytic curve p : [0, ν[→ Y , p(0) = 0, such that p(t) is a critical point of θ |Y ∩S p(t) and g(p(t)) = 0. Since the stratification is locally finite, we can assume that p(]0, ν[) is included in a stratum S. Hence, we have:

0 = (θ • p) ′ (t) = ∇θ(p(t)), p ′ (t) = λ(p(t)) ∇ρ |S (p(t)), p ′ (t) ,
because p ′ (t) lies in T p(t) S. Therefore (ρ • p) ′ (t) = 0 and ρ • p is constant. But ρ(p(t)) tends to 0 as t tends to 0 so ρ • p is zero everywhere, which is a contradiction. Now let us assume that λ(p ε ) > 0. By the Curve Selection Lemma, there exists a smooth subanalytic curve p : [0, ν[→ Y passing through p ε such that p(0) = 0, p(]0, ν[) is included in a stratum S and for t = 0, p(t) is a critical point of θ |S∩S p(t) with λ(p(t)) > 0. Therefore we have:

(θ • p) ′ (t) = λ(p(t)) ∇ρ |S (p(t)), p ′ (t) = λ(p(t))(ρ • p) ′ (t).
But (ρ•p) ′ > 0 for otherwise (ρ•p) ′ ≤ 0 and ρ•p would be decreasing. Since ρ(p(t)) tends to 0 as t tends to 0, this would imply that ρ • p(t) ≤ 0, which is impossible. Hence we can conclude that (θ • p) ′ > 0 and θ • p is strictly increasing. Since θ • p(t) tends to 0 as t tends to 0, we see that θ • p(t) > 0 for t > 0. Similarly if λ(p ε ) < 0 then θ(p ε ) < 0.

Critical points and topology of Milnor fibres

In this section we show Lê-Greuel type formulae (Theorem 5.2 and Corollary 5.3) and we give applications for sets with isolated singularity.

As in section 2, (X, 0) ⊂ (C N , 0) is an equidimensional reduced complex analytic germ of dimension d in an open set U , equipped with a Whitney stratification {V i } such that 0 belongs to the closure of all the strata. We write X = ∪ q i=0 V i where V 0 = {0} and V q = X reg . We assume that the strata V 0 , . . . , V q-1 are connected and that the analytic sets V 0 , . . . , V q-1 are reduced. We set d i = dimV i for i ∈ {1, . . . , q}. Let f : X → C be a holomorphic function which is the restriction of a holomorphic function F : U → C. We assume that f has an isolated singularity (or an isolated critical point) at 0, i.e that f has no critical point in a punctured neighborhood of 0 in X. This implies that X f = X ∩ f -1 (0) is a Whitney stratified set of dimension d -1, equipped with the stratification ∪ q i=0 V i ∩ f -1 (0) = ∪ q i=0 V f i . Let us consider another holomorphic function g : X → C, restriction of a holomorphic function G : U → C. We also assume that g has an isolated singularity at 0 so that X g = X ∩ g -1 (0) = ∪ q i=0 V i ∩ g -1 (0) = ∪ q i=0 V g i is a Whitney stratification of X g . Lemma 5.1. The function g : X f → C has an isolated singularity at 0 if and only if the function f : X g → C has an isolated singularity at 0.

Proof. Let Σ g |X f denote the critical set of g : X f → C. By the Curve Selection Lemma, it is easy to prove that Σ g |X f lies in g -1 (0). Let x be a point in Σ g |X f different from 0. Then if V (x) denotes the stratum of X that contains x, we have:

dG |V (x) (x) = λ(x)dF |V (x) (x).
Since x is not a critical point of g, λ(x) is different from 0 and:

dF |V (x) (x) = 1 λ(x) dG |V (x) (x).
This last equality means that x is a critical point of f |X g . For all i ∈ {1, . . . , q}, we denote by Γ i f,g the following relative polar set:

Γ i f,g = x ∈ V i | rank(dF |V i (x), dG |V i (x)) < 2 ,
and we make the assumption that I X,0 (X f , Γ i f,g ) < +∞, where I X,0 (-, -) denotes the intersection multiplicity at the origin. This implies that the only critical point of g |X f is 0 and, by the previous lemma, that f |X g has also an isolated singularity at 0. Furthermore, it also implies that the number of critical points of g |X∩f -1 (δ)∩ Bε is finite for 0 < |δ| ≪ ε ≪ 1. Let us denote by p i1 , . . . , p in i the critical points of g |V i ∩f -1 (δ)∩ Bε and for each j ∈ {1, . . . , n i }, let us denote by µ ij the Milnor number of g |V i at p ij . Our aim is to relate the µ ij 's to the topology of the Milnor fibres X∩f -1 (δ)∩B ε and X g ∩f -1 (δ)∩B ε . Theorem 5.2. For 0 < |δ| ≪ ε ≪ 1, we have:

χ X ∩ f -1 (δ) ∩ B ε -χ X g ∩ f -1 (δ) ∩ B ε = q i=1 (-1) d i -1 n i j=1 µ ij 1 -χ lk C (V i , X) .
Proof. Let us consider first the case when X is a curve. In this situation, X has two stratum {0} and X \ {0} and there is only one polar set Γ q f,g which is exactly the stratum X \ {0}. The critical points of g |X∩f -1 (δ)∩Bε are exactly the points in X ∩ f -1 (δ) ∩ B ε and they have Milnor number 1. Since X g ∩ f -1 (δ) ∩ B ε is empty as well as lk C (X \ {0}, X), the result is easy.

For the general case, we apply stratified Morse theory to the real and imaginary parts of g. Let us write g = g 1 + √ -1g 2 . Using the Cauchy-Riemann equations and local coordinates, it is not difficult to see that g 1|X f : X f → R and g 2|X f : X f → R have the same critical points as g |X f : X f → C. Hence g 1|X f and g 2|X f have an isolated singularity at 0. Similarly, g 1 |X∩f -1 (δ)∩ Bε and g 2 |X∩f -1 (δ)∩ Bε have the same critical points as

g |X∩f -1 (δ)∩ Bε .
Let us study the critical points of g 1 on the stratified set X ∩ f -1 (δ) ∩ B ε . We can distinguish between two kinds of critical points : those lying in X ∩ f -1 (δ) ∩ Bε and those lying in X ∩ f -1 (δ) ∩ S ε . Applying Lemma 4.2 to g 1|X f and taking δ sufficiently close to 0, we can say that the critical points of the second type satisfy the following properties:

(1) they lie outside {g 1 = 0}, (2) they are outward-pointing for g 1|X∩f -1 (δ)∩Bε in {g 1 > 0}, (3) they are inward-pointing for

g 1|X∩f -1 (δ)∩Bε in {g 1 < 0}. Let g1 : X ∩ f -1 (δ) ∩ B ε → R be a stratified Morse function close to g 1 . Applying Theorem 2.3 of [11] to the submersion R N × R N → R N × R N , (x, v) → G 1 (x) + N i=1 x i v i , where G = G 1 + √ -1G 2 ,
we can take g1 to be the restriction of a real-analytic function.

For each i ∈ {1, . . . , q}, j ∈ {1, . . . , n i }, let {q k ij }, k ∈ {1, . . . , m ij }, be the set of critical points of g1|V i lying close to p ij . For each critical point q k ij , let M g1 (q k ij ) be the local negative Milnor fibre of g1 at q k ij . It is defined as follows:

M g1 (q k ij ) = X ∩ f -1 (δ) ∩ B ε(q k ij ) ∩ g1 -1 g1 (q k ij ) -ν ,
where 0 < ν ≪ ε ≪ 1 and B ε(q k ij ) is the ball of radius ε centered at q k ij . Let α be a regular value of g1 close to 0. Applying Theorem 3.1 in [START_REF] Dutertre | On the topology of semi-algebraic functions on closed semialgebraic sets[END_REF], we have:

χ X ∩ f -1 (δ) ∩ B ε ∩ { g1 ≥ α} -χ X ∩ f -1 (δ) ∩ B ε ∩ { g1 = α} = q i=1 n i j=1 k: g1 (q k ij )> α 1 -χ M g1 (q k ij ) .
Here we remark that the critical points of g1 lying in { g1 > α} ∩ S ε do not appear in the above equality. This is due to the fact that, since g1 is close to g 1 and α close to 0, these critical points are outward-pointing g1|X∩f -1 (δ)∩Bε . For such critical points, the local negative Milnor fibre has Euler characteristic 1, as explained in [9, Lemma 2.1].

For each critical point q k ij , let λ k ij be the Morse index of g1|V i at q k ij . Since X ∩ f -1 (δ) is complex analytic, the normal Morse data of g1 at q k ij does not depend on g1 nor on q k ij and has the homotopy type of the pair Cone(lk [11, Corollary 1, p. 166]). Moreover, since g1|X∩f -1 (δ)∩Bε is a Morse function, the local Morse data at a critical point is the product of the tangential Morse data and the normal Morse data (see [START_REF] Goresky | Stratified Morse theory[END_REF]Section 3.7,p. 65]). Hence, we can write:

C (V i ∩ f -1 (δ), X ∩ f -1 (δ)), lk C (V i ∩ f -1 (δ), X ∩ f -1 (δ)) (see
1 -χ M g1 (q k ij ) = (-1) λ k ij 1 -χ lk C (V i ∩ f -1 (δ), X ∩ f -1 (δ) .
Therefore, we have:

χ X ∩ f -1 (δ) ∩ B ε ∩ { g1 ≥ α} -χ X ∩ f -1 (δ) ∩ B ε ∩ { g1 = α} = q i=1 n i j=1 k: g1 (q k ij )> α(-1) λ k ij 1 -χ lk C (V i ∩ f -1 (δ), X ∩ f -1 (δ) .
Applying the same method to -g1 and using the fact that the strata have even real dimension, we obtain:

χ X ∩ f -1 (δ) ∩ B ε ∩ { g1 ≤ α} -χ X ∩ f -1 (δ) ∩ B ε ∩ { g1 = α} = q i=1 n i j=1 k: g1 (q k ij )< α(-1) λ k ij 1 -χ lk C (V i ∩ f -1 (δ), X ∩ f -1 (δ) .
Summing these two equalities and applying the Mayer-Vietoris sequence, we get:

χ X ∩ f -1 (δ) ∩ B ε -χ X ∩ f -1 (δ) ∩ B ε ∩ { g1 = α} = q i=1 n i j=1 m ij k=1 (-1) λ k ij 1 -χ lk C (V i ∩ f -1 (δ), X ∩ f -1 (δ) .
But now for each i ∈ {1, . . . , q} and each j ∈ {1, . . . , n i },

m ij k=1 (-1) λ k ij is the Poincaré-Hopf index of the form dg 1|V i ∩f -1 (δ)
. Since g 1 is the real part of g, this index is (-1) d i -1 µ ij (see for instance [10, p. 235]). Hence we have proved:

χ X ∩ f -1 (δ) ∩ B ε -χ X ∩ f -1 (δ) ∩ B ε ∩ { g1 = α} = q i=1 n i j=1 (-1) d i -1 µ ij 1 -χ lk C (V i ∩ f -1 (δ), X ∩ f -1 (δ) ,
and therefore, since g1 is close to g 1 :

χ X ∩ f -1 (δ) ∩ B ε -χ X ∩ f -1 (δ) ∩ B ε ∩ {g 1 = α} = q i=1 n i j=1 (-1) d i -1 µ ij 1 -χ lk C (V i ∩ f -1 (δ), X ∩ f -1 (δ) ,
where α is a regular value of g 1 close to 0. Applying Lemma 3.2 to X and f -1 (δ), we obtain finally:

χ X ∩ f -1 (δ) ∩ B ε -χ X ∩ f -1 (δ) ∩ B ε ∩ {g 1 = α} = q i=1 n i j=1 (-1) d i -1 µ ij 1 -χ lk C (V i , X) ,
Now we are going to study the critical points of g 2|X∩f -1 (δ)∩Bε∩{g 1 =α} . Using the Cauchy-Riemann equations and local coordinates, it is easy to see that g 2|X∩f -1 (δ)∩Bε∩{g 1 =α} has no critical points in Bε . Similarly g 2|X f ∩{g 1 =0} has an isolated singularity at the origin. Applying Lemma 4.2 to g 2 |X f ∩{g 1 =0} and taking δ and α very small, we can control the behaviour of the critical points of g 2|X∩f -1 (δ)∩Bε∩{g 1 =α} lying in S ε . Namely, we know that:

(1) they lie outside {g 2 = 0}, (2) they are outward-pointing forg 2|X∩f -1 (δ)∩Bε ∩{g 1 =α} in {g 2 > 0}, (3) they are inward-pointing for g 2|X∩f -1 (δ)∩Bε∩{g 1 =α} in {g 2 < 0}. Let β be a small regular value of g 2|X∩f -1 (δ)∩{g 1 =α}∩Bε . Applying the same method as above, we find that:

χ X ∩ f -1 (δ) ∩ B ε ∩ {g 1 = α} ∩ {g 2 ≥ β} - χ X ∩ f -1 (δ) ∩ B ε ∩ {g 1 = α} ∩ {g 2 = β} = 0, χ X ∩ f -1 (δ) ∩ B ε ∩ {g 1 = α} ∩ {g 2 ≤ β} - χ X ∩ f -1 (δ) ∩ B ε ∩ {g 1 = α} ∩ {g 2 = β} = 0.
Hence, by the Mayer-Vietoris sequence, we get:

χ X ∩ f -1 (δ) ∩ B ε ∩ {g 1 = α} = χ X ∩ f -1 (δ) ∩ B ε ∩ {g 1 = α} ∩ {g 2 = β} .
Since f |X g has an isolated singularity at the origin, f -1 (δ) intersects X g transversally. Hence, if α + √ -1β is small enough, we have:

χ X ∩ f -1 (δ) ∩ B ε ∩ {g = α + √ -1β} = χ X ∩ f -1 (δ) ∩ B ε ∩ {g = 0} = χ X g ∩ f -1 (δ) ∩ B ε .
We can express this result in terms of intersection multiplicities.

Corollary 5.3. For 0 < |δ| ≪ ε ≪ 1, we have:

χ X ∩ f -1 (δ) ∩ B ε -χ X g ∩ f -1 (δ) ∩ B ε = q i=1 (-1) d i -1 I X,0 (X f , Γ i f,g ) 1 -χ lk C (V i , X) .
Let us apply these results to the case of a complex analytic variety with an isolated singularity. In this case, there are only two stratum {0} and X \ {0} and lk C (X \ {0}, X) is empty. Furthermore there is only one relative polar set:

Γ f,g = x ∈ X \ {0} | rank(dF |X\{0} (x), dG |X\{0} (x)) < 2 .
Corollary 5.4. If X has an isolated singularity at 0 then for 0 < |δ| ≪ ε ≪ 1, we have:

χ X ∩ f -1 (δ) ∩ B ε -χ X g ∩ f -1 (δ) ∩ B ε = (-1) d-1 I X,0 (X f , Γ f,g ).
Corollary 5.5. If X is an ICIS defined by the equations f 1 = . . . = f N -d = 0 such that X ∩ {f = 0} and X ∩ {f = 0, g = 0} are also ICIS then the above equality gives that:

µ(f 1 , . . . , f N -d , f ) + µ(f 1 , . . . , f N -d , f, g) = I X,0 (X f , Γ f,g ).
Proof. We just use the equalities

χ X ∩ f -1 (δ) ∩ B ε = 1 + (-1) d-1 µ(f 1 , . . . , f N -d , f ), and χ X g ∩ f -1 (δ) ∩ B ε = 1 + (-1) d-2 µ(f 1 , . . . , f N -d , f, g).
We recover a particular case of the Lê-Greuel formula.

We can also apply our results to the case of a 1-parameter smoothing. Namely let us assume that X ⊂ C N has an isolated singularity at 0 and let π : X → D ε be a flat morphism such that π -1 (0) = X and X t = π -1 (t) is smooth for t = 0, where X ⊂ C M is a complex analytic set of dimension d + 1 with an isolated singularity at 0 and D ε is a small disk of radius ε in C. Let g : X → C be a holomorphic function, restriction of a holomorphic function G : C M → C. We assume that I X ,0 (X, Γ π,g ) < +∞ where Γ π,g is the relative polar set defined as above. With these conditions, Corollary 5.4 gives:

Corollary 5.6. For 0 < |t 0 | ≪ ε ≪ 1, we have:

(-1) d I X ,0 (X, Γ π,g ) = χ X ∩ π -1 (t 0 ) ∩ B ε -χ X ∩ g -1 (0) ∩ π -1 (t 0 ) ∩ B ε .
When X is a surface, X ∩ g -1 (0) is a curve and so:

χ X ∩ g -1 (0) ∩ π -1 (t 0 ) ∩ B ε = 1 -µ(X ∩ g -1 (0)).
If we define µ(X) to be the second Betti number of X t 0 ∩ B ε then we obtain the following result:

I X ,0 (X, Γ π,g ) + b 1 (X t 0 ∩ B ε ) = µ(X) + µ(X ∩ g -1 (0)),
which was originally proved in [START_REF] Pereira | Codimension Two Determinantal Varieties with Isolated Singularities[END_REF].

Lê-Greuel type formula and applications to curvatures

In this section, we prove a Lê-Greuel formula for the difference of the Euler obstruction and the Euler obstruction of a function, B f,X (0) = Eu X (0) -Eu f,X (0), and we give applications to curvature integrals on the Milnor fibre. We work with the objects and the assumptions of the previous section. Theorem 6.1. Assume that f : X → C and g : X → C have an isolated singularity at 0 and that for all i ∈ {1, . . . , q}, I X,0 (X f , Γ i f,g ) < +∞. Then we have:

B f,X (0) -B f,X g (0) = (-1) d I X,0 (X f , Γ q f,g
). In order to prove the theorem, we need some lemmas relating Euler obstructions to complex links of strata. Lemma 6.2. We have:

Eu X (0) = 1 + q-1 i=0 χ lk C (V i , X) -1 Eu V i (0).
Proof. Let us consider (x 1 , x 2 , . . . , x N ) as complex coordinates of C N , where x k = u k + √ -1v k . This implies that (u 1 , v 1 , . . . , u N , v N ) are real coordinates of R 2N . Let ω be a 1-form defined by ω =

x k dx k , it means that:

ω = (u k - √ -1v k )(du k + √ -1dv k ),
and so that:

ω = (u k du k + v k dv k ) + √ -1 (u k dv k -v k dv k ).
In this case, the real 1-form Re ω = (u k du k + v k dv k ) is also a radial 1-form, and ind R X,0 Re ω = 1. Since ind C X,0 ω = (-1) d ind R X,0 Re ω, we find that:

ind C X,0 ω = (-1) d ind R X,0 Re ω = (-1) d . As it was remarked before, Eu X,0 ω = (-1) d Eu X,0 Re ω.

Using this information and the definition of n i given in Section 3, we have the next equality:

n i Eu V i ,0 ω = (-1) d-d i -1 χ lk C (V i , X) -1 (-1) d i Eu V i (0).
Therefore, by Theorem 3.6 we conclude that:

(-1) d = (-1) d q-1 i=0 1 -χ lk C (V i , X) Eu V i (0) + Eu X (0) ,
and so: [START_REF] Brasselet | Local Euler obstruction, old and new[END_REF] Eu

X (0) = 1 + q-1 i=0 χ lk C (V i , X) -1 Eu V i (0).
We have a similar result for the Euler obstruction of the function f . Lemma 6.3. We have:

1 -χ(f -1 (δ) ∩ X ∩ B ε ) = q i=0 1 -χ lk C (V i , X) Eu f,V i (0).
Proof. On the one hand, applying the Theorem 3.6 to the form df , we have:

ind C X,0 df = q i=0 n i Eu V i ,0 df = (-1) d-d i -1 χ lk C (V i , X) -1 (-1) d i Eu f,V i (0).
On the other hand, by Theorem 3 of [START_REF] Ebeling | Radial index and Euler obstruction of a 1-form on a singular variety[END_REF] we have:

ind C X,0 df = (-1) d 1 -χ(f -1 (δ) ∩ X ∩ B ε ) . It follows that: 1 -χ(f -1 (δ) ∩ X ∩ B ε ) = q i=0 1 -χ lk C (V i , X) Eu f,V i (0).
Corollary 6.4. We have:

χ(f -1 (δ) ∩ X ∩ B ε ) = q i=0 1 -χ lk C (V i , X) B f,V i (0).
Proof. By the previous lemma, we have the following equation:

(

2) Eu f,X (0) = 1-χ(f -1 (δ)∩ X ∩ B ε )+ q-1 i=0 χ lk C (V i , X) -1 Eu f,V i (0).
By the difference (1) -(2) we arrive to:

(3) B f,X (0) = χ(f -1 (δ) ∩ X ∩ B ε )+ q-1 i=0 χ lk C (V i , X) -1 B f,V i , (0).
Hence we find:

χ(f -1 (δ) ∩ X ∩ B ε ) = q i=0 1 -χ lk C (V i , X) B f,V i (0).
We are in position to prove the Lê-Greuel formula for the Euler obstruction of f .

Proof of Theorem 6.1. If X is a curve, the result is easy because, by Theorem 2.5:

B f,X (0) = χ(f -1 (δ) ∩ B ε ∩ X \ {0}) = χ(f -1 (δ) ∩ B ε ∩ X),
and Eu X g (0) = Eu f,X g (0) = 1. Thus it is enough to apply Corollary 5.4.

Let us assume that dim X = d ≥ 2 and prove this result by induction on the depth of the stratification. The first step is to consider the case when X has isolated singularity at the origin. In this case our stratification will be {V 0 = {0}, V 1 = X reg }. Applying Theorem 2.5, we have:

B f,X (0) -B f,X g (0) = = χ X reg ∩ B ε ∩ f -1 (δ) -χ X reg ∩ B ε ∩ f -1 (δ) ∩ {g = 0} = χ X ∩ B ε ∩ f -1 (δ) -χ X ∩ B ε ∩ f -1 (δ) ∩ {g = 0} .
But, by Corollary 5.4, we have:

B f,X (0) -B f,X g (0) = (-1) d-1 I X,0 (X f , Γ 1 f,g ) 1 -χ lk C (V 1 , X) = (-1) d-1 I X,0 (X f , Γ 1 f,g ), because lk C (V 1 , X
) is empty. Thus means that our assumption is true for the case of X with isolated singularity at the origin. Let us prove the general case. By the hypothesis of induction, for each i ∈ {1, . . . , d -1} we have:

(-1) d i -1 I X,0 (X f , Γ i f,g ) = B f,V i (0) -B f,V i ∩{g=0} (
0). Using Corollary 5.3, we have:

q i=1 (-1) d i -1 I X,0 (X f , Γ i f,g ) 1 -χ lk C (V i , X) = χ X ∩ f -1 (δ) ∩ B ε -χ X g ∩ f -1 (δ) ∩ B ε .
Thus using the hypothesis of induction, we find:

q-1 i=1 B f,V i (0) -B f,V i ∩{g=0} (0) 1 -χ lk C (V i , X) + (-1) d-1 I X,0 (X f , Γ q f,g ) = χ X ∩ f -1 (δ) ∩ B ε -χ X g ∩ f -1 (δ) ∩ B ε .
We can rewrite this equation as follows:

(-1) d-1 I X,0 (X f , Γ q f,g ) = A -B, where: A = χ(f -1 (δ) ∩ X ∩ B ε ) - q-1 i=0 B f,V i (0) 1 -χ lk C (V i , X) ,
and:

B = χ(f -1 (δ) ∩ X ∩ B ε ∩ {g = 0})- q-1 i=0 B f,V i ∩{g=0} (0) 1 -χ lk C (V i ∩ {g = 0}, X ∩ {g = 0}) , because by Lemma 3.2, lk C (V i , X) = lk C (V i ∩ {g = 0}, X ∩ {g = 0}
). Applying Corollary 6.4, we obtain:

(-1) d-1 I X,0 (X f , Γ q f,g ) = B f,X (0) -B f,X g (0).
In [START_REF] Teissier | Variétés polaires Locales et classes de Chern des variétés singulières[END_REF], the authors show a formula to compute the Euler obstruction of X at 0 using polar multiplicities. Our next result generalizes this formula giving a similar formula for B f,X (0), i.e., for the difference of the Euler obstruction and the Euler obstruction of the function. The strategy is to apply our results when G is a generic linear function. Let H ∈ CP N -1 be a hyperplane defined by H = {x ∈ C N | L(x) = 0} where L is a linear function. It is well-known that if H is general enough then H intersects X \{0} and X f \{0} transversally (see [8, I.1.5.5] for instance). Furthermore, if l : X → C is the restriction to X of L then Γ q f,l is the general relative polar curve of the morphism f : X → C (see [START_REF] Teissier | Variétés polaires Locales et classes de Chern des variétés singulières[END_REF] or [START_REF] Henry | Sur la condition de Thom stricte pour un morphisme analytique complexe[END_REF] for the definition of the general relative polar variety) and I X,0 (X f , Γ q f,l ) < +∞ (see [START_REF] Loeser | Formules intégrales pour certains invariants locaux des espaces analytiques complexes[END_REF]). Following the notations of Loeser, we denote by Γ 0 f the general relative polar curve of f : X → C. In this situation, we can apply Theorem 6.1. Theorem 6.5. We have: B f,X (0) -B f,X∩H (0) = (-1) d-1 I X,0 (X f , Γ 0 f ), where H ∈ CP N -1 is a generic hyperplane.

Since the left-hand side of the above equality and Eu X∩H do not depend on H , we see that Eu f,X∩H (0) is independent on the choice of the generic hyperplane H. Furthermore, when X = C N , we recover the well-known Teissier lemma [START_REF] Teissier | Introduction to equisingularity problems[END_REF], because in this situation: B f,X (0) = 1 + (-1) N -1 µ(f ), and B f,X∩H (0) = 1 + (-1) N -2 µ ′ (f ).

For i ∈ {0, . . . , d -1}, let us denote by Γ i f the general relative polar curve of the morphism f : X ∩H i → C, where H i is a generic plane of codimension i passing through 0. The following theorem expresses B f,X (0) in terms of the intersection multiplicities at the origin of the Γ i f 's with the X ∩ H i 's. Theorem 6.6. We have:

B f,X (0) = d-1 i=0 (-1) d-i-1 I X∩H i ,0 (Γ i f , X f ∩ H i ).
Proof. Let H d-1 ⊂ H d-2 ⊂ • • • ⊂ H 1 ⊂ H 0 = C N be a general flag such that H i has codimension i for i ∈ {0, . . . , d -1}. Denoting by X i the set X ∩ H i and applying the previous theorem, we get:

(-1) d-i-1 I X i ,0 (Γ i f , X i ∩ {f = 0}) = B f,X i (0) -B f,X i+1 (0), for i ∈ {0, . . . , d -2}. For i = d -1, X d-1 is a curve and Theorem 6.1 gives:

I X d-1 ,0 (Γ d-1 f , X d-1 ∩ {f = 0}) = B f,X d-1 (
0). Summing all these equalities, we obtain the result.

Applying this theorem when f = l is the restriction to X of a generic linear form leads to:

Eu X (0) = d-1 i=0
(-1) d-1-i I X∩H i ,0 (Γ i l , X l ∩ H i ).

But I X∩H i ,0 (Γ i l , X l ∩ H i ) is the multiplicity of the polar variety of codimension d-i-1 of X (see [START_REF] Teissier | Variétés polaires Locales et classes de Chern des variétés singulières[END_REF]Corollary 4.19]). Hence we recover Corollary 5.12 of [START_REF] Teissier | Variétés polaires Locales et classes de Chern des variétés singulières[END_REF]. Based on this last result, J.-P. Brasselet suggested that a possible definition for the Euler obstruction of a function could be the alternated sum of the relative polar multiplicities. This justifies why we choose to denote Eu X (0) -Eu f,X (0) by B f,X (0), which we call the Brasselet number.

In [START_REF] Kennedy | Integral formula for the Milnor number[END_REF], Kennedy presents a Gauss-Bonnet formula for the Milnor number of an analytic function f : (C n , 0) → (C, 0) with an isolated singularity. Using the integral formulas for the numbers I X∩H i ,0 (Γ i f , X f ∩ H i ) proved by Loeser [START_REF] Loeser | Formules intégrales pour certains invariants locaux des espaces analytiques complexes[END_REF], we can generalize Kennedy's formula to the singular case. Let us recall first two objects used by Loeser. For i ∈ {0, . . . , d -1}, let c w d-1-i (T f ) be the (d -1i)-th Chern Weil form associated with the relative tangent fiber bundle T f on the regular part of X ∩ f -1 (δ) equipped with the hermitian structure given by the embedding of X in C N . Let us also define ω = It is enough to apply the previous theorem. We can apply this last corollary to the stratum V k , k ∈ {1, . . . , q -1}, of X. Recalling that d k = dim V k , we have:

lim ε→0 lim δ→0 V k ∩f -1 (δ)∩Bε d k -1 i=0 c w d k -1-i (T f ) ∧ ω i = B f,V k (0),
where we keep the notation T f for the relative tangent bundle on V k ∩f -1 (δ).

Multiplying by 1χ(lk C (V k , X)) and using Corollary 6.4, we obtain a Gauss-Bonnet type formula for X ∩ f -1 (δ) ∩ B ε . Corollary 6.8. We have the following Gauss-Bonnet formula:

χ(f -1 (δ) ∩ X ∩ B ε ) = q k=1 1 -χ lk C (V k , X) lim ε→0 lim δ→0 V k ∩f -1 (δ)∩Bε d k -1 i=0 c w d k -1-i (T f ) ∧ ω i .

Definition 4 . 1 .

 41 is a Whitney stratification of the closed subanalytic set Y ∩ {ρ ≤ a}. Let θ : R n → R be another smooth subanalytic function such that θ |Y ∩{ρ≤a} admits an isolated critical point p in Y ∩ {ρ = a} which is not a critical point of θ |Y . If S denotes the stratum of Y that contains p, this implies that: ∇θ |S (p) = λ(p)∇ρ |S (p), with λ(p) = 0. We will say that p ∈ Y ∩ {ρ = a} is an outward-pointing (resp. inward-pointing) critical point for θ |Y ∩{ρ≤a} if λ(p) > 0 (resp. λ(p) < 0). Now let us suppose that 0 ∈ Y and that {0} is a single stratum of Y . Let θ : U ⊂ R n → R be a smooth subanalytic function defined on an open neighborhood U of 0. We assume that θ |U \{0}∩S has no critical point.

√ - 1 2π

 1 ∂∂log z 2 to be the inverse image on C N \ {0} of the Kähler form on CP N -1 . Corollary 6.7. We have the following integral formula: i (T f ) ∧ ω i .Proof. By Theorem 1 in[START_REF] Loeser | Formules intégrales pour certains invariants locaux des espaces analytiques complexes[END_REF], we have that for i ∈ {0, . . . , d -1}:(-1) d-1-i I X∩H i ,0 (Γ i f , X f ∩ H i ) = lim ε→0 lim δ→0 Xreg∩f -1 (δ)∩Bε c w d-1-i (T f ) ∧ ω i .


Diarmuid Grimes
email: d.grimes@4c.ucc.ie

Emmanuel Hebrard
email: hebrard@laas.fr

Models and Strategies for Variants of the Job Shop Scheduling Problem

Recently, a variety of constraint programming and Boolean satisfiability approaches to scheduling problems have been introduced. They have in common the use of relatively simple propagation mechanisms and an adaptive way to focus on the most constrained part of the problem. In some cases, these methods compare favorably to more classical constraint programming methods relying on propagation algorithms for global unary or cumulative resource constraints and dedicated search heuristics. In particular, we described an approach that combines restarting, with a generic adaptive heuristic and solution guided branching on a simple model based on a decomposition of disjunctive constraints. In this paper, we introduce an adaptation of this technique for an important subclass of job shop scheduling problems (JSPs), where the objective function involves minimization of earliness/tardiness costs. We further show that our technique can be improved by adding domain specific information for one variant of the JSP (involving time lag constraints). In particular we introduce a dedicated greedy heuristic, and an improved model for the case where the maximal time lag is 0 (also referred to as no-wait JSPs).

Introduction

Scheduling problems come in a wide variety and it is natural to think that methods specifically engineered for each variant would have the best performance. However, it was recently shown this is not always true. Tamura et al. introduced an encoding of disjunctive and precedence constraints into conjunctive normal form formulae [START_REF] Tamura | Compiling Finite Linear CSP into SAT[END_REF]. Thanks to this reformulation they were the first to report optimality proofs for all open shop scheduling instances from three widely studied benchmarks. Similarly the hybrid CP/SAT solver lazy-FD [START_REF] Feydy | Lazy Clause Generation Reengineered[END_REF] was shown to be extremely effective on Resource-Constrained Project scheduling (RCPSP) [START_REF] Schutt | Why Cumulative Decomposition Is Not as Bad as It Sounds[END_REF].

Previously, we introduced an approach for open and job shop problems with a variety of extra constraints [START_REF] Grimes | Job Shop Scheduling with Setup Times and Maximal Time-Lags: A Simple Constraint Programming Approach[END_REF][START_REF] Grimes | Closing the Open Shop: Contradicting Conventional Wisdom[END_REF] using simple reified binary disjunctive constraints combined with a number of generic SAT and AI techniques: weighted degree variable ordering [START_REF] Boussemart | Boosting Systematic Search by Weighting Constraints[END_REF], solution guided value ordering [START_REF] Beck | Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling[END_REF], geometric restarting [START_REF] Walsh | Search in a Small World[END_REF] and nogood recording from restarts [START_REF] Lecoutre | Nogood Recording from Restarts[END_REF]. It appears that the weighted degree heuristic efficiently detects the most constrained parts of the problem, focusing search on a fraction of the variables.

The simplicity of this approach makes it easy to adapt to various constraints and objective functions. One type of objective function that has proven troublesome for traditional CP scheduling techniques involves minimizing the sum of earliness/tardiness costs, primarily due to the weak propagation of the sum objective [START_REF] Danna | Structured vs. unstructured large neighborhood search: A case study on job-shop scheduling problems with earliness and tardiness costs[END_REF]. In this paper we show how our basic JSP model can be adapted to handle this objective. Experimental results reveal that our approach is competitive with the state of the art on the standard benchmarks from the literature. Moreover, we introduce two refinements of our approach for problems with maximum time lags between consecutive tasks, where we incorporate domain specific information to boost performance. These time lag constraints, although conceptually very simple, change the nature of the problem dramatically. For instance, it is not trivial to find a feasible schedule even if we do not take into account any bound on the total makespan (unless scheduling jobs back to back). This has several negative consequences. Firstly, it is not possible to obtain a trivial upper bound of reasonable quality may be found by sequencing the tasks in some arbitrary order. The only obvious upper bound is to sequence the jobs consecutively. Secondly, since relaxing the makespan constraint is not sufficient to make the problem easy, our approach can have difficulty finding a feasible solution for large makespans, even though it is very effective when given a tighter upper bound. However because the initial upper bound is so poor, even an exploration by dichotomy of the objective variable's domain can take a long time.

We introduce a simple search strategy which, when given a large enough upper bound on the makespan, guarantees a limited amount of backtracking whilst still providing good quality solutions. This simple strategy, used as an initial step, greatly improves the performance of our algorithm on this problem type. We report several new best upper bounds and proofs of optimality on these benchmarks. Moreover, we introduce another improvement in the model of the particular case of No wait JSP where the tasks of each job must be directly consecutive. This variant has been widely studied, and efficient metaheuristics have been proposed recently. We report 5 new best upper bound, and close 9 new instances in standard data sets.

Finally, because there are few comparison methods in the literature for problems with strictly positive time lags, we adapted a job shop scheduling model written in Ilog Scheduler by Chris Beck [START_REF] Beck | Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling[END_REF], to handle time lag constraints. Our method outperforms this model when time lag constraints are tight (short lags), however when time lags are longer, the Ilog Scheduler model together with geometric restarts and solution guided search is better than our method.

Background & Previous work

An n × m job shop problem (JSP) involves a set of nm tasks

T = {t i | 1 ≤ i ≤ nm}, partitioned into n jobs J = {J x | 1 ≤ x ≤ n}, that need to be scheduled on m machines M = {M y | 1 ≤ y ≤ m}. Each job J x ∈ J is a set of m tasks J x = {t (x-1) * m+y | 1 ≤ y ≤ m}.
Conversely, each machine M y ∈ M denotes a set of n tasks (to run on this machine) such that:

T = ( 1≤x≤n J x ) = ( 1≤y≤m M y ).
Each task t i has an associated duration, or processing time, p i . A schedule is a mapping of tasks to time points consistent with sequencing and resource constraints. The former ensure that the tasks of each job run in a predefined order whilst the latter ensure that no two tasks run simultaneously on any given machine. In the rest of the paper, we shall identify each task t i with the variable standing for its start time in the schedule. We define the sequencing (2.1) and resource (2.2) constraints in Model 1.

Moreover, we shall consider two objective functions: total makespan, and weighted earliness/tardiness. In the former, we want to minimize the the total duration to run all tasks, that is, C max = max ti∈T (t i +p i ) if we assume that we start at time 0. In the latter, each job J x ∈ J has a due date, d x . There is a linear cost associated with completing a job before its due date, or the tardy completion of a job, with coefficient w e x and w t x , respectively. (Note that these problems differ from Just in Time job shop scheduling problems [START_REF] Baptiste | Lagrangian Bounds for Just-in-Time Job-shop Scheduling[END_REF], where each task has a due date.) If t xm is the last task of job J x , then t xm + p xm is its completion time, hence the cost of a job is then given by: ET sum = Jx∈J (max(w e

x (d

x -t xm -p xm ), w t x (t xm + p xm -d x ))) model 1 JSP ti + pi ≤ ti+1 ∀Jx ∈ J , ∀ti, ti+1 ∈ Jx (2.1) ti + pi ≤ tj ∨ tj + pj ≤ ti ∀My ∈ M, ti = tj ∈ My (2.2)

Boolean Model

In previous work [START_REF] Grimes | Closing the Open Shop: Contradicting Conventional Wisdom[END_REF] we described the following simple model for open shop and job shop scheduling. First, to each task, we associate a variable t i taking its value in [0, ∞] that stands for its starting time. Then, for each pair of tasks sharing a machine we introduce a Boolean variable that stands for the relative order of these two tasks. More formally, for each machine M y ∈ M, and for each pair of tasks t i , t j ∈ M y , we have a Boolean variable b ij , and constraint (2.2) can be reformulated as follows:

b ij = 0 ⇔ t i + p i ≤ t j 1 ⇔ t j + p j ≤ t i ∀M y ∈ M, t i = t j ∈ M y (2.3)
Finally, the tasks of each job J x , are kept in sequence with a set of simple precedence constraints

t i + p i ≤ t i+1 for all t i , t i+1 ∈ J x .
For n jobs and m machines, this model therefore involves nm(n -1)/2 Boolean variables, as many disjunctive constraints, and n(m -1) precedence constraints. Bounds consistency (BC) is maintained on all constraints. Notice that state of the art CP models use instead m global constraints to reason about unary resources. The best known algorithms for filtering unary resources constraints implement the edge finding, not-first/not-last, and detectable precedence rules with a O(n log n) time complexity [START_REF] Vilím | Filtering Algorithms for the Unary Resource Constraint[END_REF]. One might therefore expect our model to be less efficient as n grows. However, the quadratic number of constraints -and Boolean variables -required to model a resource in our approach has not proven problematic on the academic benchmarks tested on to date.

Search Strategy

We refer the reader to [START_REF] Grimes | Job Shop Scheduling with Setup Times and Maximal Time-Lags: A Simple Constraint Programming Approach[END_REF] for a more detailed description of the default search strategy used for job shop variants, and we give here only a brief overview. This model does not involve any global constraint associated to a strong propagation algorithm. However, it appears that decomposing resource constraints into binary disjunctive elements is synergetic with adaptive heuristics, and in particular the weighted-degree-based heuristics [START_REF] Boussemart | Boosting Systematic Search by Weighting Constraints[END_REF]. (We note that the greater the minimum arity of constraints in a problem, the less discriminatory the weight-degree heuristic can be.) A constraint's weight is incremented by one each time the constraint causes a failure during search. This weight can then be projected on variables to inform the heuristic choices.

It is sufficient to decide the relative sequencing of the tasks, that is, the value of the Boolean variables standing for disjuncts. Because the domain size of these variables are all equal, we use a slightly modified version of the domain over weighted-degree heuristic, where weights and domain size are taken on the two tasks whose relative ordering is decided by the Boolean variable. Let w(t i ) be the number of times search failed while propagating any constraint involving task t i , and let min(t i ) and max(t i ) be, respectively, the minimum and maximum starting time of t i at any point during search. The next disjunct b ij to branch on is the one minimizing the value of:

(max(t i ) + max(t j )min(t i )min(t j ) + 2)/(w(t i ) + w(t j ))

A second important aspect is the use of restarts. It has been observed that weighted heuristics also have a good synergy with restarts [START_REF] Grimes | A Study of Adaptive Restarting Strategies for Solving Constraint Satisfaction Problems[END_REF]. Indeed, failures tend to happen at a given depth in the search tree, and therefore on constraints that often do not involve variables corresponding to the first few choices. As a result, early restarts will tend to favor diversification until enough weight has been given to a small set of variables, on which the search will then be focused. We use a geometric restarting strategy [START_REF] Walsh | Search in a Small World[END_REF] with random tie-breaking. The geometric strategy is of the form s, sr, sr 2 , sr 3 , ... where s is the base and r is the multiplicative factor. In our experiments the base was 256 failures and the multiplicative factor was 1.3. Moreover, after each restart, the dead ends of the previous explorations are stored as clausal nogoods [START_REF] Lecoutre | Nogood Recording from Restarts[END_REF].

A third very important feature is the idea of guiding search (branching choices) based on the best solution found so far. This idea is a simplified version of the solution guided approach (SGMPCS) proposed by Beck for JSPs [START_REF] Beck | Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling[END_REF]. Thus our search strategy can be viewed as variable ordering guided by past failures and value ordering guided by past successes.

Finally, before using a standard Branch & Bound procedure, we first use a dichotomic search to reduce the gap between lower and upper bound. At each step of the dichotomic search, a satisfaction problem is solved, with a limit on the number of nodes.

Job Shop with Earliness/Tardiness Objective

In industrial applications, the length of the makespan is not always the preferred objective. An important alternative criterion is the minimization of the cost of a job finishing early/late. An example of a cost for early completion of a job would be storage costs incurred, while for late completion of a job these costs may represent the impact on customer satisfaction.

Although the only change to the problem is the objective function, our model requires a number of additional elements. When we minimize the sum of earliness and tardiness, we introduce 4n additional variables. For each job J x we have a Boolean variable e x that takes the value 1 iff J x is finished early and the value 0 otherwise. In other words, e x is a reification of the precedence constraint t xm + p xm < d x . Moreover, we also have a variable E x standing for the duration between the completion time of the last task of J x and the due date d x when J x is finished early:

E x = e x (d x -t xm -p xm ).
Symmetrically, for each job J x we have Boolean variable l x taking the value 1 iff J x is finished late, and an integer variable L x standing for the delay (Model 2). model 2 ET-JSP minimise ETsum subject to :

ETsum = Jx∈J (w e x Ex + w t x Lx) (3.1) ex ⇔ (txm + pxm < dx) ∀Jx ∈ J (3.2) Ex = ex(dx -txm -pxm) ∀Jx ∈ J (3.3) lx ⇔ (txm + pxm > dx) ∀Jx ∈ J (3.4) Lx = lx(txm + pxm -dx) ∀Jx ∈ J (3.5) (constraints 2.1) & (constraints 2.3)
Unlike the case where the objective involves minimizing the makespan, branching only on the disjuncts is not sufficient for these problems. Thus we also branch on the early and late Boolean variables, and on the variables standing for start times of the last tasks of each job. For these extra variables, we use the standard definition of domain over weighted degree.

Job Shop Scheduling Problem with Time Lags

Time lag constraints arise in many scheduling applications. For instance, in the steel industry, the time lag between the heating of a piece of steel and its moulding should be small [START_REF] Wismer | Solution of the Flowshop-Scheduling Problem with No Intermediate Queues[END_REF]. Similarly when scheduling chemical reactions, the reactives often cannot be stored for a long period of time between two stages of a process to avoid interactions with external elements [START_REF] Rajendran | A No-Wait Flowshop Scheduling Heuristic to Minimize Makespan[END_REF].

Model

The objective to minimise is represented by a variable C max linked to the last task of each job by n precedence constraints: ∀x ∈ [1, . . . , n] t xm + p xm ≤ C max . The maximum time lag between two consecutive tasks is simply modelled by a precedence constraint with negative offset. Letting L(i) be the maximum time lag between the tasks t i and t i+1 , we use the following model:

model 3 TL-JSP minimise Cmax subject to : Cmax ≥ txm + pxm ∀Jx ∈ J (4.1) ti+1 -(pi + L(i)) ≤ ti ∀Jx ∈ J , ∀ti, ti+1 ∈ Jx (4.2) (constraints 2.1) & (constraints 2.3)

Greedy Initialization

In the classical job shop scheduling problem, one can consider tasks in any order compatible with the jobs and schedule them to their earliest possible start time. The resulting schedule may have a long makespan, however such a procedure usually produces reasonable upper bounds. With time lag constraints, however, scheduling early tasks of a job implicitly fixes the start times for later tasks, thus making the problem harder. Indeed, as soon as tasks have been fixed in several jobs, the problem becomes difficult even if there is no constraint on the length of the makepsan. Standard heuristics can thus have difficulty finding feasible solutions even when the makespan is not tightly bounded. In fact, we observed that this phenomenon is critical for our approach.

Once a relatively good upper bound is known our approach is efficient and is often able to find an optimal solution. However, when the upper bound is, for instance, the trivial sum of durations of all tasks, finding a feasible solution with such a relaxed makespan was in some cases difficult. For some large instances, no non-trivial solution was found, and on some instances of more moderate size, much computational effort was spent converging towards optimal values.

We therefore designed a search heuristic to find solutions of good quality, albeit very quickly. The main idea is to move to a new job only when all tasks of the same machine are completely sequenced between previous jobs. Another important factor is to make decisions based on the maximum completion time of a job, whilst leaving enough freedom within that job to potentially insert subsequent jobs instead of moving them to the back of the already scheduled jobs. We give a pseudo-code for this strategy in Algorithm 1. The set jobs to schedule stands for the jobs for which sequencing is still open, whilst f ixed jobs contains the currently processed job, as well as all the jobs that are completely sequenced. On the first iteration of the outer "while" loop, a job is chosen. There is no disjunct satisfying the condition in Line 1, so this job's completion time is fixed to a value given by the stretched procedure (Line 2), that is, the minimum possible starting time of its first task, plus its total duration, plus the sum of the possible time lags.

On the second iteration and beyond, a new job is selected. We then branch on the sequencing decisions between this new job and the rest of the set f ixed jobs before moving to a new job. We call J x(i) the job that contains task t i , and observe that for any unassigned Boolean variable b ij , either J x(i) or J x(j) ∈ f ixed jobs must be the last chosen job J y . The sequencing choice that sets a task of the new job before a task of previously explored jobs is preferred, i.e., considered in the left branch. Observe that a failure due to time lag constraints can be raised only in the inner "while" loop. Therefore, if the current upper bound on the makespan is large enough, this heuristic will ensure that we never backtrack on a decision on a task. We randomize this heuristic and use several iterations (1000 in the present set of experiments) to find a good initial solution.

Special Case: Job Shop with no-wait problems

The job shop problem with no-wait refers to the case where the maximum time-lag is set to 0, i.e. each task of a job must start directly after its preceding task has finished. In this case one can view the tasks of the job as one block.

In [START_REF] Grimes | Job Shop Scheduling with Setup Times and Maximal Time-Lags: A Simple Constraint Programming Approach[END_REF] we introduced a simple improvement for the no-wait class based on the following observation: if no delay is allowed between any two consecutive tasks of a job, then the start time of every task is functionally dependent on the start time of any other task in the job. The tasks of each job can thus be viewed as one block. We therefore use a single variable J x standing for the starting times of the job of same name.

We call J x(i) the job of task t i , and we define h i as the total duration of the tasks coming before task t i in its job J x(i) . That is,

h i = k∈{k | k<i ∧ t k ∈J x(i) } p k .
For every pair of tasks t i ∈ J x , t j ∈ J y sharing a machine, we use the same Boolean variables to represent disjuncts as in the original model, however linked by the following constraints:

b ij = 0 ⇔ J x + h i + p i -h j ≤ J y 1 ⇔ J y + h j + p j -h i ≤ J x
Although the variables and constants are different, these are the same constraints as used in the basic model. The no-wait JSP can therefore be reformulated as shown in Model 4, where the variables J 1 , . . . , J n represent the start time of the jobs and f (i, j) = h i + p ih j . model 4 NW-JSP minimise Cmax subject to :

Cmax ≥ Jx + t i ∈Jx pi ∀Jx ∈ J (4.3) bij = 0 ⇔ J x(i) + f (i, j) ≤ J x(j) 1 ⇔ J x(j) + f (j, i) ≤ J x(i) ∀My ∈ M, ti = tj ∈ My (4.4)
However, we can go one step further. For a given pair of jobs J x , J y the set of disjunct between tasks of these jobs define as many conflict intervals for the start time of one job relative to the other. For two tasks t i and t j , we have J x(j) ∈ ]J x(i)f (j, i), J x(i) + f (i, j)[. However, these intervals may overlap or subsume each other. It is therefore possible to tighten this encoding by computing larger intervals, that we shall refer to as maximal forbidden intervals, hence resulting in fewer disjuncts. We first give an example, and then briefly describe a procedure to find maximal forbidden intervals. In Figure 1a we illustrate two jobs J x {t 1 , t 2 , t 3 , t 4 } and J y = {t 5 , t 6 , t 7 , t 8 }. The number and shades of grey stand for the machine required by each task. The length of the tasks are respectively {20, 50, 80, 50} for J x and {60, 45, 20, 25} for J y . In Figure 1b we give, for each machine, the pair of conflicting tasks, their durations and the corresponding forbidden intervals.

For each machine M k , let t i be the task of J x and t j the task of J y that are both processed on machine M k . Following the reasoning used in Model 4, we have a conflict interval (represented by black arrows in Figure 1a) for each pair of tasks sharing the same machine: J y ∈ ]J xf (j, i), J x + f (i, j)[. In the example the forbidden intervals for J y are therefore: ]J x -60, J x + 20[. . .]J x -105, J x -35[. . .]J x -80, J x + 25[. . .]J x + 45, J x + 140[. However, these intervals can be merged, yielding larger (maximal) forbidden intervals, in which case we have:

J y ∈ ]J x -105, J x + 25[ ∧ J y ∈]J x + 45, J x + 140[.
Given two jobs J x and J y , Algorithm 2 computes all maximal forbidden intervals efficiently (in O(m log m) steps). First, we build a list of pairs whose first element is an end point of a conflict interval, and second element is either +1 if it is the start, and -1 otherwise. Then these Given this set of forbidden intervals, we can represent the conflicts between J x and J y with the following set of Boolean variables and disjunctive constraints:

b xy 105,25 = 0 ⇔ J y + 105 ≤ J x 1 ⇔ J x + 25 ≤ J y b xy 45,140 = 0 ⇔ J y -45 ≤ J x 1 ⇔ J x + 140 ≤ J y
In the previous encoding we would have needed 4 Boolean variables and as many disjunctive constraints (one for each pair of tasks sharing a machine). We believe, however, that the main benefit is not the reduction in size of the encoding. Rather, it is the tighter correlation between the model and the real structure of the problem which helps the heuristic to make good choices. model 5 NW-JSP minimise Cmax subject to :

Cmax ≥ Jx + t i ∈Jx pi ∀Jx ∈ J (4.5) bij a,b = 0 ⇔ Jy -a ≤ Jx 1 ⇔ Jx + b ≤ Jy ∀Jx = Jy ∈ J , [a, b] ∈ get-F-intervals(Jx, Jy, M)(4.6)

Experimental Evaluation

The full experimental results, with statistics for each instance, as well as benchmarks and source code are online: http://homepages.laas.fr/ehebrard/jsp-experiment.html.

Job Shop with Earliness/Tardiness Objective

The best complete methods for handling these types of problem are the CP/LP hybrid of Beck and Refalo [START_REF] Beck | A Hybrid Approach to Scheduling with Earliness and Tardiness Costs[END_REF] and the MIP approaches of Danna et al. [START_REF] Danna | Integrating Mixed Integer Programming and Local Search: A Case Study on Job-Shop Scheduling Problems[END_REF], and Danna and Perron [START_REF] Danna | Structured vs. unstructured large neighborhood search: A case study on job-shop scheduling problems with earliness and tardiness costs[END_REF], while more recently Kebel and Hanzalek proposed a pure CP approach [START_REF] Kelbel | Solving production scheduling with earliness/tardiness penalties by constraint programming[END_REF]. Danna and Perron also proposed an incomplete approach based on large neighborhood search [START_REF] Danna | Structured vs. unstructured large neighborhood search: A case study on job-shop scheduling problems with earliness and tardiness costs[END_REF].

Our experiments were run on an Intel Xeon 2.66GHz machine with 12GB of ram on Fedora 9. Each algorithm run on a problem had an overall time limit of 3600s, and there were 10 runs per instance. We report our results in terms of the best and worst run. We tested our method on two benchmarks which have been widely studied in the literature. The comparison experimental results are taken from [START_REF] Danna | Integrating Mixed Integer Programming and Local Search: A Case Study on Job-Shop Scheduling Problems[END_REF] and [START_REF] Danna | Structured vs. unstructured large neighborhood search: A case study on job-shop scheduling problems with earliness and tardiness costs[END_REF], where all experiments were performed on a 1.5 GHz Pentium IV system running Linux. For the first benchmark, these algorithms had a time limit of 20 minutes per instance, while for the second benchmark the algorithms had a time limit of 2 hours.

The comparison methods are as follows:

-MIP: Default CPLEX in [START_REF] Danna | Integrating Mixed Integer Programming and Local Search: A Case Study on Job-Shop Scheduling Problems[END_REF], run using a modified version of ILOG CPLEX 8.1 -CP: A pure constraint programming approach introduced by Beck and Refalo in [START_REF] Beck | A Hybrid Approach to Scheduling with Earliness and Tardiness Costs[END_REF], run using ILOG Scheduler 5.3 and ILOG Solver 5.3 -CRS-ALL: A CP/LP hybrid approach proposed by Beck and Refalo in [START_REF] Beck | A Hybrid Approach to Scheduling with Earliness and Tardiness Costs[END_REF], run using ILOG CPLEX 8.1, ILOG Hybrid 1.3.1, ILOG Scheduler 5.3 and ILOG Solver 5.3 -uLNS: An unstructured large neighborhood search MIP method proposed by Danna and Peron in [START_REF] Danna | Structured vs. unstructured large neighborhood search: A case study on job-shop scheduling problems with earliness and tardiness costs[END_REF], run using a modified version of ILOG CPLEX 8.1 -sLNS: A structured large neighborhood search CP/LP method proposed by Danna and Peron in [START_REF] Danna | Structured vs. unstructured large neighborhood search: A case study on job-shop scheduling problems with earliness and tardiness costs[END_REF], run using ILOG Scheduler 5.3, ILOG Solver 5.3 and ILOG CPLEX 8.1

The first benchmark consists of 9 sets of problems generated by Beck and Refalo [START_REF] Beck | A Hybrid Approach to Scheduling with Earliness and Tardiness Costs[END_REF] using the random JSP generator of Watson et al. [START_REF] Watson | Algorithm performance and problem structure for flow-shop scheduling[END_REF]. For instance size J xM, there were three sets of ten JSPs of size 10x10, 15x10 and 20x10 generated. The second benchmark is taken from the genetic algorithms (GA) literature and was proposed by Morton and Pentico [START_REF] Morton | Heuristic Scheduling Systems[END_REF]. There are 12 instances, with problem size ranging from 10x3 to 50x8. Jobs in these problems do have release dates. Furthermore earliness and tardiness costs of a job are equal.

We present results on the randomly generated ETJSPs in Table 1 in terms of number of problems solved to optimality and sum of the upper bounds, for each algorithm. 4 Here, the column "Best" for our method means the number of problems solved to optimality on at least one of the ten runs on the instance, while the column "Worst" refers to the number of problems solved to optimality on all ten runs. We also report the mean cpu time in seconds for our method.

We first consider the number of problems solved to optimality (columns "Opt."). While there is little difference in the performance of our method and that of uLNS and CRS-ALL on the looser instances (looseness factor of 1.3 and 1.5), we see that our method is able to close three of the 23 open problems in the set with looseness factor 1.0. An obvious reason for this improvement with our method would be the difference in time limits and quality of machines. However, analysis of the results reveals that of the 68 problems solved to optimality on every run of our method, only 8 took longer than one second on average, and only one took longer than one minute (averaging 156s). Furthermore, uLNS only solved two problems to optimality when the time limit was increased to two hours [START_REF] Danna | Structured vs. unstructured large neighborhood search: A case study on job-shop scheduling problems with earliness and tardiness costs[END_REF]. Clearly our method is extremely efficient at proving optimality on these problems.

The previous results suggest that CRS-ALL is much better than uLNS on these problems. However, as was shown by Danna et al. [START_REF] Danna | Integrating Mixed Integer Programming and Local Search: A Case Study on Job-Shop Scheduling Problems[END_REF], this may not be the case when the algorithms are compared based on the sum of the upper bounds found over the 30 "hard" instances (i.e. with looseness factor 1.0). In order to assess whether there was a similar deterioration in the performance of our method as for CRS-ALL on the problems where optimality was not proven, we report this data in the columns " ub" of Table 1.

We find, on the contrary, that the performance of our approach is even more impressive when algorithms are compared using this metric. The two large neighborhood search methods found the best upper bounds of the comparison algorithms with sLNS the most efficient by a factor of 2 over uLNS. However, there are a couple of points that should be noted here. Firstly sLNS is an incomplete method so cannot prove optimality, and secondly the sum of the worst upper bounds found by our method was still significantly better than that found by sLNS. Indeed, there was very little variation in performance for our method across runs, with an average difference of 256 between the best and worst upper bounds found.

Danna and Perron also provided the sum of the best upper bounds found on the hard instances over all methods they studied [START_REF] Danna | Structured vs. unstructured large neighborhood search: A case study on job-shop scheduling problems with earliness and tardiness costs[END_REF], which was 36,459. This further underlines the quality of the performance of our method on these problems. Finally, we investigated the hypothesis that the different time limit and machines used for experiments could explain these results. We compared the upper bounds found by our method after the dichotomic search phase, where the maximum runtime of this phase over all runs per instance was 339s. The upper bound sums over the hard instances were 32,299 and 49,808 for best and worst respectively, which refutes this hypothesis.

Table 2 provides results on the second of the benchmarks (taken from the GA literature). Following the convention of previous work on these problems [23][4][9], we report the cost normalized by the weighted sum of the job processing times. We include the best results found by the GA algorithms as presented by Vázquez and Whitley [START_REF] Vázquez | A comparison of genetic algorithms for the dynamic job shop scheduling problem[END_REF]. We also provide an aggregated view of the results of each algorithm using the geometric mean ratio (GMR), which is the geometric mean of the ratio between the normalized upper bound found by the algorithm and the best known normalized upper bound, across a set of instances.

The performance of our method was less impressive for these problems, solving two fewer problems to optimality than uLNS, and achieving a worse GMR than either of the large neighborhood search methods. However, we remind the reader that all comparison methods had a 2 hour time limit on these instances, except the GA approaches for which the time limit was not reported. We further note that we find an improved solution for one instance (ljb10) and outperform all methods other than uLNS and sLNS.

Job Shop Scheduling Problem with positive Time Lags

These experiments were run using the same settings as in Section 5.1. However, because of the large number of instances and algorithms, we used only 5 random runs per instance.

There are relatively few results reported for benchmarks with positive maximum time lag constraints, as most publications focus on the "no wait" case. Caumond et al. introduced a genetic algorithm [START_REF] Caumond | A Memetic Algorithm for the Job-shop with Time-lags[END_REF]. Then, Artigues et al. introduced a Branch & Bound procedure that allowed them to find lower bounds of good quality [START_REF] Artigues | Generalized Disjunctive Constraint Propagation for Solving the Job Shop Problem with Time Lags[END_REF]. Therefore, in order to get a better idea of the efficiency of our approach, we adapted a model written by Chris Beck for Ilog Scheduler (version 6.3) to problems featuring time lag constraints. This model was used to showcase the SGMPCS algorithm [START_REF] Beck | Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling[END_REF]. We used the following two strategies: In the first, the next pair of tasks to schedule is chosen following the Texture heuristic/goal predefined in Ilog Scheduler and restarts following the Luby sequence [START_REF] Luby | Optimal Speedup of Las Vegas Algorithms[END_REF] are performed, this was one of the default strategies used as a reference point in [START_REF] Beck | Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling[END_REF]. In the second, branching decisions are selected with the same "goal", however the previous best solution is used to decide wich branch should be explored first, and geometric restarts [START_REF] Walsh | Search in a Small World[END_REF] are performed, instead of the Luby sequence. In other words, this is SGMPCS with a singleton elite solution. We denote the first method Texture-Luby and the second method Texture-Geom+Guided. These two methods were run on the same hardware with the same time limit and number of random runs as our method. Finally, we report results for our approach without the greedy initialization heuristic (Algorithm 1) in order to evaluate its importance.

We used the benchmarks generated by Caumond et al. in [START_REF] Caumond | A Memetic Algorithm for the Job-shop with Time-lags[END_REF] by adding maximal time lag constraints to the Lawrence JSP instances of the OR-library 5 . Given a job shop instance N, and two parameters x and y, a new instance N x y is produced. For each job all maximal time lags are given the value ym, where m is the average processing time over tasks of this job. The first parameter x corresponds to minimal time lags and will always be 0 in this paper. 6 . In Table 3, we first report a comparison with the genetic algorithm described in [START_REF] Caumond | A Memetic Algorithm for the Job-shop with Time-lags[END_REF], denoted [CLT] and the adhoc Branch & Bound algorithm introduced in [START_REF] Artigues | Generalized Disjunctive Constraint Propagation for Solving the Job Shop Problem with Time Lags[END_REF], denoted [AHL]. We used only instances for which results were reported in both papers, and where the time lags were strictly positive, hence the relatively small data set. Despite that, and despite the difference in hardware and time limit, it is quite clear that our approach outperforms both the complete and heuristic methods on these benchmarks. Next, in Table 4, we report results on all modified Lawrence instances for both Ilog Scheduler models, and the two version of Model 3, with and without the greedy initialization heuristic. Since there are 280 instances in total, the results are aggregated by the level of tightness of the time lag constraints. For each set, we give the ratio of instances that were solved to optimality in at least one of the five runs in the first column, as well as the mean PRD in the second column.

First, we notice the great impact of the new initialization heuristic on our method. Without it, the Ilog Scheduler model was more efficient for instances with y = 1, and the overall results are extremely poor for larger values of y. However, the mean results are deceptive. Without initialization, Model 3 can be very efficient, although in a few cases no solution at all can be found. Indeed, relaxing the makespan does not necessarily makes the problem easy for this model. The weight of these bad cases in the mean value can be important, hence the poor PRD. On the other hand, we can see that the Ilog Scheduler model is more robust to this phenomenon: a non-trivial upper bound is found in every case. It is therefore likely that the impact of the initialization heuristic will not be as important on the Ilog model as on Model 3.

We also notice that solution guidance and geometric restarts greatly improve Ilog Scheduler's performance. Interestingly, we observe that our approach is best when the time lag constraints are tight. On the other hand, Scheduler is slightly more efficient on instances with loose time lag constraints and in particular proves optimality more often on these instances. However, whereas our method always finds near-optimal solutions (the worst mean PRD is 0.47 for instances with y = 1), both scheduler models find relatively poor upper bounds for small values of y.

Job Shop Scheduling Problem with no wait constraints

For the no-wait job shop problem, the best methods are a tabu search method by Schuster (TS [START_REF] Schuster | No-wait Job Shop Scheduling: Tabu Search and Complexity of Problems[END_REF]) and a hybrid constructive/tabu search algorithm introduced by Bożejko and Makuchowski in 2009 (HTS [START_REF] Bozejko | A Fast Hybrid Tabu Search Algorithm for the No-wait Job Shop Problem[END_REF]). We also report the results of a Branch & Bound procedure introduced by Mascis and Pacciarelli [START_REF] Mascis | Job-shop Scheduling with Blocking and No-wait Constraints[END_REF]. This algorithm was run on a Pentium II 350 MHz. For the no-wait class we used the same data sets as Schuster [START_REF] Schuster | No-wait Job Shop Scheduling: Tabu Search and Complexity of Problems[END_REF] and Bożejko et al. [START_REF] Bozejko | A Fast Hybrid Tabu Search Algorithm for the No-wait Job Shop Problem[END_REF] where null time lags are added to instances of the OR-library. We report the best results of each paper in terms of average PRD. It should be noted that for HTS, the authors reported two sets of results. The former were run with a time limit based on the runtimes reported in [START_REF] Schuster | No-wait Job Shop Scheduling: Tabu Search and Complexity of Problems[END_REF] and

  Values of p, h and f .

Fig. 1 :

 1 Fig. 1: Computation of conflict intervals.

  Algorithm 1 Greedy initialization branching heuristic f ixed jobs ← ∅; jobs to schedule ← J ; while jobs to schedule = ∅ do pick and remove a random job Jy in jobs to schedule; f ixed jobs ← f ixed jobs ∪ {Jy}; next decisions ← {bij | J x(i) , J x(j) ∈ f ixed jobs}; while next decisions = ∅ do

1

pick and remove a random disjunct bij from next decisions; if J x(i) = Jy then branch on ti + pi ≤ tj else branch on tj + pj ≤ ti; 2 branch on txm ≤ min(t (x-1)m+1 )+ stretched(Jy);

  Algorithm 2 get-F-intervals. Jx = {tx 1 , . . . , tx m }, Jy = {ty 1 , . . . , ty m }, M Iin ← []; foreach tx i ∈ Jx, ty j ∈ Jy such that M(tx i ) = M(ty j ) do Iin ← Iin extended with [(-f (j, i), +1), (f (i, j), -1)]; pairs are sorted by increasing first element. Now we can scan these pairs and count, thanks to the second element, how many intervals are simultaneously open. When we go from 0 to 1 open intervals, this marks the start of a maximal forbidden interval, and conversely the end when we go from 1 to 0 open intervals. The list I out has 2k elements, and the 2i + 1 th and 2i + 2 th elements are read as the start and end of a forbidden interval.

	sort Iin by increasing first element;
	Iout ← []; open ← 0;
	while not-empty(I) do
	(a, z) ← remove first element from Iin;
	if open = 0 then append a to Iout;
	open ← open + z;
	if open = 0 then append a to Iout;
	return Iout;

Data:

Table 1 :

 1 ET-JSP -Random Problems, Number Proven Optimal and Upper Bound Sum

	lf		MIP	CP	uLNS	sLNS	CRS-All	Best	Model 2 Worst	Avg.
		opt.	ub opt.	ub opt.	ub	ub opt.	ub opt.	ub opt.	ub Time (s)
	1.0	0 654,290 0 1,060,634 0 156,001 52,307 7 885,546 10 30,735 8 38,416 2534.86
	1.3 14 26,930 6 1,248,618 30		8,397 8,397 30	8,397 30 8,397 30 8,397	0.36
	1.5 27	7,891 6 1,672,511 30		6,964 6,964 30	6,964 30 6,964 30 6,964	0.18
	Notes: Comparison results taken from [9], except uLNS, taken from [8].
	Figures in bold are the best result over all methods.

Table 2 :

 2 ET-JSP -GA Problems, Normalized upper bounds Figures in bold indicate best upper bound found over the different algorithms. "*" indicates optimality was proven by the algorithm.

	Instance Size	MIP	CP	uLNS sLNS CRS-All	GA Best	Model 2 Best Worst
	jb1	10x3 0.191* 0.474 0.191* 0.191 0.191* 0.474 0.191* 0.191*
	jb2	10x3 0.137* 0.746 0.137* 0.137 0.531 0.499 0.137* 0.137*
	jb4	10x5 0.568* 0.570 0.568* 0.568 0.568* 0.619 0.568* 0.568*
	jb9	15x3 0.333* 0.355 0.333* 0.333 1.216 0.369 0.333* 0.333*
	jb11	15x5	0.233	0.365 0.213* 0.213 0.213* 0.262	0.221	0.235
	jb12	15x5 0.190* 0.239 0.190* 0.190 0.190* 0.246 0.190* 0.190*
		GMR	1.015	1.774	1	1	1.555 1.610	1.006	1.017
	ljb1	30x3 0.215* 0.847 0.215* 0.215 0.295 0.279	0.215	0.221
	ljb2	30x3	0.622	1.268 0.508 0.508 1.364 0.598	0.590	0.728
	ljb7	50x5	0.317	0.614 0.123 0.110 0.951 0.246	0.166	0.256
	ljb9	50x5	1.373	1.737 1.270 1.015 2.571 0.739	1.157	1.513
	ljb10	50x8	0.820	1.569 0.558 0.525 1.779 0.512	0.499	0.637
	ljb12	50x8	1.025	1.368 0.488 0.605 1.601 0.399	0.537	0.623
		GMR	1.943	3.233 1.213 1.170 4.098 1.220	1.299	1.686
	Overall GMR	1.329	2.434 1.084 1.068 2.305 1.408	1.118	1.256
	Comparison results taken from [9].

Table 3 :

 3 TL-JSP -Comparison with related work (Time & Upper bound).Due to space limitations, we present most of our results in terms of each solver's average percentage relative deviation (PRD) given by the following formula:P RD = ((C Alg -C Ref )/C Ref ) * 100,where C Alg is the best makespan found by the algorithm and C Ref is the best upper bound among all considered algorithms

	Instance	[AHL] time (s) Cmax time (s) Cmax time (s) Cmax [CLT] Model 3
	la06 0 10 707.00	927	0.00	926	0.03 926
	la06 0 1	524.00 1391 1839.00 1086	70.60 926
	la07 0 10 518.00 1123	25.00	890 3600.00 890
	la07 0 1	754.00 1065 1914.00 1032 3600.00 896
	la08 0 10 260.00	863	2.00	863	0.07 863
	la08 0 1	587.00 1052 1833.00 1048	615.80 892
	average	558.33 1070	935.50	974 1314.41 898
	P RD		18.88		8.32	0.00

Table 4 :

 4 TL-JSP -Comparison with Ilog Scheduler (Proofs of optimality & Upper bound PRD).

				Texture		Model 3
	Instance Sets	Luby	Geom+Guided	no init.	init. heuristic
		Opt. P RD Opt. P RD Opt. P RD Opt. P RD
	la[1,40] 0 0	0.12 25.37 0.12 16.15 0.37 10.42 0.35 0.06
	la[1,40] 0 0.25 0.20 22.98 0.25 12.01 0.37	3.46 0.40 0.00
	la[1,40] 0 0.5	0.22 19.47 0.25	5.17 0.37	2.62 0.42 0.00
	la[1,40] 0 1	0.35 15.76 0.42	1.18 0.40 17.43 0.45 0.47
	la[1,40] 0 2	0.67	7.35 0.75	0.13 0.67 74.16 0.70 0.37
	la[1,40] 0 3	0.75	3.47 0.92	0.00 0.75 95.91 0.77 0.29
	la[1,40] 0 10	0.95	0.10 0.97	0.00 0.92	0.04 0.92 0.05

Table 5 :

 5 NW-JSP -Comparison with related work (Upper bound PRD).

		Mascis et al. Schuster Bożejko et al.	Model 4		Model 5
	Instance	B&B	TS	HTS HTS+ tdom+bw tdom/tw tdom+bw tdom/tw
	la[1-10]	0.00	4.43 1.77	1.77	0.00	0.00	0.00	0.00
	la[11-20]	31.66	7.93 3.49	0.95	0.14	0.10	0.00	0.31
	la[21-30]	61.09	10.43 7.25	0.08	1.16	0.57	0.25	0.84
	la[31-40]	73.73	10.95 8.33	0.15	4.42	1.77	2.68	1.36
	abz[5-9]	47.04	9.01 5.95	0.78	2.47	1.14	1.13	1.20
	orb[1-10]	0.00	2.42 0.77	0.77	0.00	0.00	0.00	0.00
	swv[1-5]	60.85	3.94 3.67	0.00	2.54	0.77	0.00	0.43
	swv[6-10]	57.82	4.99 4.19	0.00	4.78	1.71	0.44	1.00
	swv[11-15]	70.98	0.68 2.48	0.60	19.50	6.53	17.54	5.18
	swv[16-20]	76.81	5.71 3.98	0.00	10.92	68.94	4.47	3.17
	yn[1-4]	72.74	12.40 8.85	0.32	5.60	5.75	2.37	2.88
	overall	44.72	6.51 4.36	0.52	3.53	5.50	1.97	1.13

Note that sLNS is not complete, hence it never proved optimality.

http://people.brunel.ac.uk/ ˜mastjjb/jeb/info.html

To the best of our knowledge, these are the best known upper bounds.

varying from 0.25 seconds for the easiest instances to 2360 seconds for the hardest. The latter (in italic font, and referred to as HTS+ in Table 5) were run "without limit of computation time". We use bold face to mark the best result amongst methods that had time limits, i.e. excluding HTS+. We ran two variable ordering heuristics for our method. First, the heuristics used for ET-JSP and TL-JSP, where the Boolean variable minimizing the value of (max(t i ) + max(t j )min(t i )min(t j ) + 2)/(w(t i ) + w(t j )) is chosen first, denoted tdom/tw. Second, we used another heuristic, denoted tdom+bw that selects the next Boolean variable to branch on solely according to the tasks' domain sizes (max(t i ) + max(t j )min(t i )min(t j ) + 2), and break ties with the Boolean variable's own weight w(b ij ). In Table 6 we report the results on no-wait instances for which we obtained new upper bounds (5 instances) or new proofs of optimality (9 instances), thanks to the model introduced here.

Conclusions

We have shown that the simple constraint programming approach introduced in [START_REF] Grimes | Closing the Open Shop: Contradicting Conventional Wisdom[END_REF] can be successfully adapted to handle the objective of minimizing the sum of earliness/tardiness costs. These problems have traditionally proven troublesome for CP approaches because of the weak propagation of the sum objective [START_REF] Danna | Structured vs. unstructured large neighborhood search: A case study on job-shop scheduling problems with earliness and tardiness costs[END_REF].

Then we introduced a new heuristic to find good initial solutions for job shop problems with maximal time lag constraints. The resulting method greatly improves over state of the art algorithms for this problem. However, as opposed to the other aspects of the method (adaptive variable heuristic, solution guided branching, restarts with nogood storage) this new initialization heuristic is dedicated to job shop problems with time lag constraints.

Finally, we showed that domain-specific information can also be used to improve our model for no-wait job shop scheduling problems, allowing us to provide several improved upper bounds and prove optimality in many cases.