Ivan Nourdin
email: inourdin@gmail.com

Giovanni Peccati
email: giovanni.peccati@gmail.com

Poisson approximations on the free Wigner chaos

Keywords: Catalan numbers, Contractions, Free Brownian motion, Free cumulants, Free Poisson distribution, Free probability, Marchenko-Pastur, Non-central limit theorems, Non-crossing partitions, Riordan numbers, Semicircular distribution, Wigner chaos. 2000 Mathematics Subject Classification: 46L54, 60H05, 60H07, 60H30

. As a by-product of our findings, we show that Wigner chaoses of order strictly greater than 2 do not contain non-zero free Poisson random variables. Our techniques involve the so-called 'Riordan numbers', counting noncrossing partitions without singletons.

Introduction 1.Overview

Let W be a standard Brownian motion on R + and let q 1 be an integer. For every deterministic symmetric function f ∈ L 2 (R q + ), we denote by I W q (f ) the multiple stochastic Wiener-Itô integral of f with respect to W . Random variables of the form I W q (f ) compose the so-called qth Wiener chaos associated with W . The concept of Wiener chaos roughly represents an infinite-dimensional analogous of Hermite polynomials for the one-dimensional Gaussian distribution (see e.g. [START_REF] Peccati | Wiener Chaos: Moments, Cumulants and Diagrams[END_REF] for an introduction to this topic).

The following two results, proved respectively in [START_REF] Nualart | Central limit theorems for sequences of multiple stochastic integrals[END_REF] and [START_REF] Nourdin | Non-central convergence of multiple integrals[END_REF], provide an exhaustive characterization of normal and Gamma approximations on Wiener chaos. As in [START_REF] Nourdin | Non-central convergence of multiple integrals[END_REF], we denote by F (ν) a centered random variable with the law of 2G(ν/2)-ν, where G(ν/2) has a Gamma distribution with parameter ν/2 (if ν 1 is an integer, then F (ν) has a centered χ 2 distribution with ν degrees of freedom).

Theorem 1.1 (A) Let N ∼ N (0, 1), fix q 2 and let I W q (f n ) be a sequence of multiple stochastic integrals with respect to the standard Brownian motion W , where each f n is a symmetric element of L 2 (R q + ) such that

E[I W q (f n ) 2 ] = q! f n 2 L 2 (R q + ) = 1.
Then, the following two assertions are equivalent, as n → ∞:

(i) I W q (f n ) converges in distribution to N ; (ii) E[I W q (f n ) 4 ] → E[N 4 ] = 3.
(B) Fix ν > 0, and let F (ν) have the centered Gamma distribution described above. Let q 2 be an even integer, and let I W q (f n ) be a sequence of multiple stochastic integrals, where each f n is symmetric and verifies E[I W q (f n ) 2 ] = E[F (ν) 2 ] = 2ν. Then, the following two assertions are equivalent, as n → ∞:

(i) I W q (f n ) converges in distribution to F (ν); (ii) E[I q (f n ) 4 ] -12E[I q (f n ) 3 ] → E[F (ν) 4 ] -12E[F (ν) 3 ] = 12ν 2 -48ν.
The results stated in Theorem 1.1 provide a drastic simplification of the so-called method of moments for probabilistic approximations, and have triggered a huge amount of applications and generalizations, involving e.g. Stein's method, Malliavin calculus, power variations of Gaussian processes, Edgeworth expansions, random matrices and universality results. See [START_REF] Nourdin | Stein's method on Wiener chaos[END_REF][START_REF] Nourdin | Stein's method meets Malliavin calculus: a short survey with new estimates[END_REF], as well as the forthcoming monograph [START_REF] Nourdin | Normal approximations with Malliavin calculus[END_REF], for an overview of the most important developments. See [START_REF] Nourdin | A webpage on Stein's method, Malliavin calculus and related topics[END_REF] for a constantly updated web resource, with links to all available papers on the subject.

In [START_REF] Kemp | Wigner chaos and the fourth moment[END_REF], together with Kemp and Speicher, we proved an analogue of Part A of Theorem 1.1 in the framework of free probability (and free Brownian motion). Let (A , ϕ) be a free probability space and let {S(t) : t 0} be a free Brownian motion defined therein (see Section 3 for details). As shown in [START_REF] Biane | Stochastic analysis with respect to free Brownian motion and analysis on Wigner space[END_REF], one can define multiple integrals of the type I S q (f ), where f is a square-integrable complex kernel (to simplify the notation, throughout the paper we shall drop the suffixes q, S, and write simply I(f ) = I S q (f )). Random variables of the type I(f ) compose the so-called Wigner chaos associated with S, playing in free stochastic analysis a role analogous to that of the classical Gaussian Wiener chaos (see for instance [START_REF] Biane | Stochastic analysis with respect to free Brownian motion and analysis on Wigner space[END_REF], where Wigner chaoses are used to develop a free version of the Malliavin calculus of variations). The following statement is the main result of [START_REF] Kemp | Wigner chaos and the fourth moment[END_REF].

Theorem 1.2 Let s be a centered semicircular random variable with unit variance (see Definition 2.3(i)), fix an integer q 2, and let I(f n ) be a sequence of multiple integrals of order q with respect to the free Brownian motion S, where each f n is a mirror symmetric (see Section 3) element of

L 2 (R q + ) such that ϕ[I q (f n ) 2 ] = f n 2 L 2 (R q + ) = 1.
Then, the following two assertions are equivalent, as n → ∞:

(i) I(f n ) converges in distribution to s; (ii) ϕ[I(f n ) 4 ] → ϕ[s 4 ] = 2.
The principal aim of this paper is to prove a free analogous of Part B of Theorem 1.1. As explained in Section 2, and somehow counterintuitively, the free analogous of Gamma random variables is given by free Poisson random variables (see Definition 2.3(ii), and also [6, p. 203]). The free Poisson law is also known as the Marchenko-Pastur distribution, arising in random matrix theory as the limit of the eigenvalue distribution of large sample covariance matrices (see e.g. Bai and Silverstein [1, Ch. 3], Hiai and Petz [4, pp. 101-103 and 130] and the references therein). The following statement is the main achievement of the present work. Theorem 1.3 Let q 2 be an even integer. Let Z(λ) have a centered free Poisson distribution with rate λ > 0. Let I(f n ) be a sequence of multiple integrals of order q with respect to the free Brownian motion S, where each f n is a mirror symmetric element of

L 2 (R q + ) such that ϕ[I q (f n ) 2 ] = f n 2 L 2 (R q + ) = ϕ[Z(λ) 2 ] = λ.
Then, the following two assertions are equivalent, as n → ∞:

(i) I(f n ) converges in distribution to Z(λ); (ii) ϕ[I(f n ) 4 ] -2ϕ[I(f n ) 3 ] → ϕ[Z(λ) 4 ] -2ϕ[Z(λ) 3 ] = 2λ 2 -λ.
One should note that the techniques involved in our proofs are different from those adopted in the previously quoted references, as they are based on a direct enumeration of contractions. These contractions emerge when iteratively applying product formulae for multiple Wigner integrals -see also [START_REF] Nourdin | Yet another proof of the Nualart-Peccati criterion[END_REF]. One crucial point is that the moments of a free Poisson random variable can be expressed in terms of the so-called Riordan numbers, counting the number of non-crossing partitions without singletons (see e.g. [START_REF] Bernhart | Catalan, Motzkin, and Riordan numbers[END_REF]). We also stress that one cannot expect to have convergence to a non-zero free Poisson inside a Wigner chaos of odd order, since random variables inside such chaoses have all odd moments equal to zero, while one has e.g. that ϕ[Z(λ) 3 ] = λ (see Remark 2.5(ii)).

As a consequence of Theorem 1.3, we will be able to prove the following result, stating that Wigner chaoses of order greater than 2 do not contain any non-zero Poisson random variable.

Proposition 1.4 Let q 4 be even, and let F be a non-zero random variable in the qth Wigner chaos. Then, F cannot have a free Poisson distribution.

As pointed out in Remark 3.2 below, centered Poisson random variables with integer rate can be realized as elements of the second Wigner chaos. As a consequence, Proposition 1.4 implies that the second Wigner chaos contains random variables whose distribution is not shared by any element of higher chaoses. This result parallels the findings of [START_REF] Kemp | Wigner chaos and the fourth moment[END_REF], where it is proved that Wigner chaoses of order 2 do not contain any non-zero semicircular random variable. Note that, at the present time, it is not known in general whether two non-zero random variables belonging to two distinct Wigner chaoses have necessarily different laws.

Remark 1.5 We are still far from understanding the exact structure of the free Wigner chaos. For instance, almost nothing is known about the regularity of the distributions associated with the elements of a fixed Wigner chaos. In particular, we ignore whether such laws may have atoms or are indeed absolutely continuous (as those in the classical Wiener chaos).

The free probability setting

Our main reference for free probability is the monograph by Nica and Speicher [START_REF] Nica | Lectures on the Combinatorics of Free Probability[END_REF], to which the reader is referred for any unexplained notion or result. We shall also use a notation which is consistent with the one adopted in [START_REF] Kemp | Wigner chaos and the fourth moment[END_REF].

For the rest of the paper, we consider as given a so-called (tracial) W * -probability space (A , ϕ), where: A is a von Neumann algebra of operators (with involution X → X * ), and ϕ is a unital linear functional on A with the properties of being weakly continuous, positive (that is, ϕ(XX * ) 0 for every X ∈ A ), faithful (that is, such that the relation ϕ(XX * ) = 0 implies X = 0), and tracial (that is, ϕ(XY ) = ϕ(Y X), for every X, Y ∈ A ).

As usual in free probability, we refer to the self-adjoint elements of A as random variables. Given a random variable X we write µ X to indicate the law (or distribution) of X, which is defined as the unique Borel probability measure on R such that, for every integer m 0, ϕ(X m ) = R x m µ X (dx) (see e.g. [START_REF] Nica | Lectures on the Combinatorics of Free Probability[END_REF]Proposition 3.13]).

We say that the unital subalgebras A 1 , ..., A n of A are freely independent whenever the following property holds: let X 1 , ..., X m be a finite collection of elements chosen among the A i 's in such a way that (for j = 1, ..., m -1) X j and X j+1 do not come from the same A i and ϕ(X j ) = 0 for j = 1, ..., m; then ϕ(X 1 • • • X m ) = 0. Random variables are said to be freely independent if they generate freely independent unital subalgebras of A .

Plan

The rest of the paper is organized as follows. In Section 2 we provide a characterization of centered free Poisson distributions in terms of non-crossing partitions. Section 3 deals with free Brownian motion and Wigner chaos. Section 4 contains the proofs of the main results of the paper (that is, Theorem 1.3 and Proposition 1.4), whereas Section 5 is devoted to some auxiliary lemmas.

Semicircular and centered free Poisson distributions

The following definition contains most of the combinatorial objects that are used throughout the text. (ii) A partition π of [m] is said to be non-crossing if one cannot find integers p 1 , q 1 , p 2 , q 2 such that: (a) 1 p 1 < q 1 < p 2 < q 2 m, (b) p 1 , p 2 are in the same block of π, (c) q 1 , q 2 are in the same block of π, and (d) the p i 's are not in the same block of π as the q i 's. The collection of the non-crossing partitions of [m] is denoted by N C(m), m 1. (v) For every m 1 and every j = 1, ..., m, we define R m,j to be the number of non-crossing partitions of [m] with exactly j blocks and with no singletons. Plainly, R m = m j=1 R m,j . Also, when m is even, one has that R m,j = 0 for every j > m/2; when m is odd, then R m,j = 0 for every j > (m -1)/2.

Example 2.2 One has that:

-R 1 = R 1,1 = 0, since {{1}} is the only partition of [START_REF] Bai | Spectral Analysis of Large Dimensional Random Matrices, 2 nd Edition[END_REF], and such a partition is composed of exactly one singleton;

-R 2 = R 2,1 = 1, since the only partition of [START_REF] Bernhart | Catalan, Motzkin, and Riordan numbers[END_REF] with no singletons is {{1, 2}};

-R 3 = R 3,1 = 1, since the only partition of [START_REF] Biane | Stochastic analysis with respect to free Brownian motion and analysis on Wigner space[END_REF] with no singletons is {{1, 2, 3}};

-R 4 = 3, since the only non-crossing partitions of [START_REF] Hiai | The semicircle law, free random variables and entropy[END_REF] with no singletons are {{1, 2, 3, 4}}, {{1, 2}, {3, 4}} and {{1, 4}, {2, 3}}. This implies that R 4,1 = 1 and R 4,2 = 2.

The integers {R m : m 0} are customarily called the Riordan numbers. A detailed analysis of the combinatorial properties of Riordan numbers is provided in the paper by Bernhart [START_REF] Bernhart | Catalan, Motzkin, and Riordan numbers[END_REF]; however, it is worth noting that the discussion to follow is self-contained, in the sense that no previous knowledge of the combinatorial properties of the sequence {R m } is required.

Given a random variable X, we denote by {κ m (X) : m 1} the sequence of the free cumulants of X. We recall (see [6, p. 175]) that the free cumulants of X are completely determined by the following relation: for every m 1

ϕ(X m ) = π={b 1 ,...,b j }∈N C(m) j i=1 κ |b i | (X), (2.1)
where |b i | indicates the size of the block b i of the non-crossing partition π. It is clear from (2.1) that the sequence {κ m (X) : m 1} completely determines the moments of X (and viceversa).

Definition 2.3 (i)

The centered semicircular distribution of parameter t > 0, denoted by S(0, t)(dx), is the probability distribution given by

S(0, t)(dx) = (2πt) -1 4t -x 2 dx, |x| < 2 √ t.
We recall the classical relation:

2 √ t -2 √ t x 2m S(0, t)(dx) = C m t m ,
where C m is the mth Catalan number (so that e.g. the second moment of S(0, t) is t).

Since the odd moments of S(0, t) are all zero, one deduces from the previous relation and (2.1) (e.g. by recursion) that the free cumulants of a random variable s with law S(0, t) are all zero, except for κ 2 (s) = ϕ(s 2 ) = t.

(ii) The free Poisson distribution with rate λ > 0, denoted by P (λ)(dx) is the probability distribution defined as follows: (a) if λ ∈ (0, 1], then P (λ) = (1λ)δ 0 + λ ν, and (b) if λ > 1, then P (λ) = ν, where δ 0 stands for the Dirac mass at 0. Here,

ν(dx) = (2πx) -1 4λ -(x -1 -λ) 2 dx, x ∈ (1 - √ λ) 2 , (1 + √ λ) 2 . If X λ has the P (λ) distribution, then [6, Proposition 12.11] implies that κ m (X λ ) = λ, m 1.
(2.2)

From now on, we will denote by Z(λ) a random variable having the law of X λ -λ1 (centered free Poisson distribution), where 1 is the unity of A . Plainly,

κ 1 [Z(λ)] = ϕ[Z(λ)] = 0.
Note that both S(0, t) and P (λ) are compactly supported, and therefore are uniquely determined by their moments (by the Weierstrass theorem). Definition 2.3-(ii) is taken from [START_REF] Nica | Lectures on the Combinatorics of Free Probability[END_REF]Definition 12.12]. The choice of the denomination "free Poisson" comes from the following two facts: (1) P (λ) can be obtained as the limit of the free convolution of Bernoulli distributions (see [START_REF] Nica | Lectures on the Combinatorics of Free Probability[END_REF]Proposition 12.11]), and (2) the classical Poisson distribution of parameter λ has (classical) cumulants all equal to λ (see e.g. [START_REF] Peccati | Wiener Chaos: Moments, Cumulants and Diagrams[END_REF]Section 3.3]). As recalled in the Introduction, the free Poisson law is also called the "Marchenko-Pastur distribution".

The following statement contains a characterization of the moments of Z(λ), and shows that, when λ is integer, then Z(λ) is the free equivalent of a classical centered χ 2 random variable with λ degrees of freedom. This last fact could alternatively be deduced from [6, Proposition 12.13], but here we prefer to provide a self-contained argument.

Proposition 2.4 Let the notation of Definition 2.1 and Definition 2.3 prevail. Then, for every real λ > 0 and every integer m 1,

ϕ[Z(λ) m ] = m j=1 λ j R m,j .
(2.3)

Let p = 1, 2, ... be an integer, then Z(p) has the same law as p i=1 (s 2 i -1), where s 1 , ..., s p are p freely independent random variables with the S(0, 1) distribution, and 1 is the unit of A .

Proof. From (2.2), one deduces that κ m [Z(λ)] = λ for every m 2. Since κ 1 [Z(λ)] = 0, we infer from (2.1) that

ϕ[Z(λ) m ] = π={b 1 ,...,b j }∈N C(m)
λ j 1 {π has no singletons} , which immediately yields (2.3). To prove the last part of the statement, consider first the case p = 1, write s = s 1 and fix an integer m 2. In order to build a non-crossing partition of [m], say π, one has to perform the following three steps: (a) choose an integer j ∈ {0, ..., m}, denoting the number of singletons of π, (b) choose the j singletons of π among the m available integers (this can be done in exactly m j distinct ways), (c) build a non-crossing partition of the remaining mj integers with blocks at least of size 2 (this can be done in exactly R m-j distinct ways). Since C 0 = R 0 = 1 and C 1 = 1 = R 0 + R 1 , it follows that Catalan and Riordan numbers are linked by the following relation: for every m 0

C m = m j=0 m j R m-j = m j=0 m j R j , (2.4)
where the last equality follows from m j = m m-j . By inversion, one therefore deduces that

R m = m j=0 m j (-1) m-j C j , m 0. Therefore ϕ[(s 2 -1) m ] = m j=0 m j (-1) m-j ϕ(s 2j ) = m j=0 m j (-1) m-j C j = R m = m j=1 R m,j = ϕ[Z(1) m ],
from which we infer that s 2 -1 law = Z(1), yielding the desired conclusion when p = 1. Let us now consider the general case, that is, p 2. By free independence, for any m 2, we have that

κ m p i=1 (s 2 i -1) = p × κ m (s 2 1 -1) = p × κ m (Z(1)) = p = κ m (Z(p)).
This implies that p i=1 s 2 i -

1 law = Z(p),
[Z(λ) 3 ] = λR 3,1 = λ, while ϕ[Z(λ) 4 ] = λR 4,1 + λ 2 R 4,2 = λ + 2λ 2 .

Free Brownian motion and Wigner chaos

Our main reference for the content of this section is the paper by Biane and Speicher [START_REF] Biane | Stochastic analysis with respect to free Brownian motion and analysis on Wigner space[END_REF]. (ii) For every integer q 2, the space L 2 (R q + ) is the collection of all complex-valued functions on R q + that are square-integrable with respect to the Lebesgue measure. Given f ∈ L 2 (R q + ), we write f * (t 1 , t 2 , ..., t q ) = f (t q , ..., t 2 , t 1 ), and we call f * the adjoint of f . We say that an element of L 2 (R q + ) is mirror symmetric if f (t 1 , ..., t q ) = f * (t 1 , ..., t q ), for almost every vector (t 1 , ..., t q ) ∈ R q + . Notice that mirror symmetric functions constitute a Hilbert subspace of L 2 (R q + ).

(iii) Given f ∈ L 2 (R q + ) and g ∈ L 2 (R p + ), for every r = 1, ..., min(q, p) we define the rth contraction of f and g as the element of L 2 (R p+q-2r

+ ) given by f r ⌢g(t 1 , ..., t p+q-2r ) (3.5) = R r + f (t 1 , .
.., t q-r , y r , y r-1 , ..., y 1 )g(y 1 , y 2 , ..., y r , t q-r+1 , t p+q-2r )dy 1 • • • dy r .

One also writes f 0 ⌢g(t 1 , ..., t p+q ) = f ⊗ g(t 1 , ..., t p+q ) = f (t 1 , ..., t q )g(t q+1 , ..., t p+q ). In the following, we shall use the notations f 0 ⌢g and f ⊗ g interchangeably. Observe that, if p = q, then f

p ⌢g = f, g * L 2 (R q + ) .
A free Brownian motion S on (A , ϕ) consists of: (i) a filtration {A t : t 0} of von Neumann sub-algebras of A (in particular, A u ⊂ A t , for 0 u < t), (ii) a collection S = {S(t) : t 0} of self-adjoint operators such that:

-S(t) ∈ A t for every t; -for every t, S(t) has a semicircular distribution S(0, t), with mean zero and variance t;

for every 0 u < t, the 'increment' S(t) -S(u) is freely independent of A u , and has a semicircular distribution S(0, tu), with mean zero and variance tu.

For every integer q 1, the collection of all random variables of the type

I S q (f ) = I(f ), f ∈ L 2 (R q + )
, is called the qth Wigner chaos associated with S, and is defined according to [3, Section 5.3], namely:

-first define I(f ) = (S(b 1 ) -S(a 1 )) . . . (S(b q ) -S(a q )), for every function f having the form

f (t 1 , ..., t q ) = q i=1 1 (a i ,b i ) (t i ), (3.6)
where the intervals (a i , b i ), i = 1, ..., q, are pairwise disjoint;

-extend linearly the definition of I(f ) to 'simple functions vanishing on diagonals', that is, to functions f that are finite linear combinations of indicators of the type (3.6);

-exploit the isometric relation

I(f 1 ), I(f 2 ) L 2 (A ,ϕ) = ϕ (I(f 1 ) * I(f 2 )) = ϕ (I(f * 1 )I(f 2 )) = f 1 , f 2 L 2 (R q + ) , (3.7)
where f 1 , f 2 are simple functions vanishing on diagonals, and use a density argument to define I(f ) for a general f ∈ L 2 (R q + ).

Observe that relation (3.7) continues to hold for every pair f 1 , f 2 ∈ L 2 (R q + ). Moreover, the above sketched construction implies that I(f ) is self-adjoint if and only if f is mirror symmetric. Finally, we recall the following fundamental multiplication formula, proved in [START_REF] Biane | Stochastic analysis with respect to free Brownian motion and analysis on Wigner space[END_REF]. For every f ∈ L 2 (R q + ) and g ∈ L 2 (R p + ), where q, p 1,

I(f )I(g) = min(q,p) r=0 I(f r ⌢g). (3.8)
Remark 3.2 Let {e i : 1, ..., p} be an orthonormal system in L 2 (R + ). Then, the random variables s i = I(e i ), i = 1, ..., p, have the S(0, 1) distribution and are freely independent. Moreover, the product formula (3.8) implies that

p i=1 (s 2 i -1) = I p i=1 e i ⊗ e i ,
and therefore that the double integral I ( p i=1 e i ⊗ e i ) has a centered free Poisson distribution with rate p.

Proof of the main results

Proof of Theorem 1.3

In the free probability setting (see e.g. [6, Definition 8.1]) convergence in distribution is equivalent to the convergence of moments, so that I(f n ) converges in distribution to Z(λ) if and only if ϕ(I(f n ) m ) → ϕ(Z(λ) m ), for every m 1. In particular, convergence in distribution implies ϕ(I(

f n ) 4 ) -2ϕ(I(f n ) 3 ) → ϕ(Z(λ) 4 ) -2ϕ(Z(λ) 3 ) = 2λ 2 -λ. Now assume that ϕ[I(f n ) 4 ] -2ϕ[I(f n ) 3 ] → 2λ 2 -λ.
We have to show that, for every

m 2, ϕ[I(f n ) m ] → ϕ[Z(λ) m ].
Iterative applications of the product formula (3.8) yield

I(f n ) m = (r 1 ,...,r m-1 )∈Am I (. . . ((f n r 1 ⌢f n ) r 2 ⌢f n ) . . . f n ) r m-1 ⌢ f n ,
where

A m = (r 1 , . . . , r m-1 ) ∈ {0, 1, . . . , q} m-1 : r 2 2q -2r 1 , r 3 3q -2r 1 -2r 2 , . . . , r m-1 (m -1)q -2r 1 -. . . -2r m-2 .
We deduce that

ϕ[I(f n ) m ] = (r 1 ,...,r m-1 )∈Bm (. . . ((f n r 1 ⌢f n ) r 2 ⌢f n ) . . . f n ) r m-1 ⌢ f n ,
with B m = (r 1 , . . . , r m-1 ) ∈ A m : 2r 1 + . . . + 2r m-1 = mq . We decompose B m as follows:

B m = D m ∪ E m , with D m = B m ∩ {0, q 2 , q} m-1 and E m = B m \ D m , so that ϕ[I(f n ) m ] = (r 1 ,...,r m-1 )∈Dm (. . . ((f n r 1 ⌢f n ) r 2 ⌢f n ) . . . f n ) r m-1 ⌢ f n + (r 1 ,...,r m-1 )∈Em (. . . ((f n r 1 ⌢f n ) r 2 ⌢f n ) . . . f n ) r m-1 ⌢ f n . (4.9)
By the forthcoming Lemma 5.1, we have f n q/2 ⌢f nf n → 0 and f n r ⌢f n → 0 for r ∈ {1, . . . , q -1} \ { q 2 }. The conclusion is then obtained by observing that the first sum in (4.9) converges to ϕ[Z(λ) m ] by Proposition 2.4 and the forthcoming Lemma 5.2, whereas the second sum converges to zero by the forthcoming Lemma 5.4. 2

Proof of Proposition 1.4

Assume that F = I(f ), where f is a mirror symmetric element of L 2 (R q + ) for some even q 4, and also that ϕ[F 2 ] = f 2 L 2 (R q + ) = λ > 0. If F had the same law of Z(λ), then ϕ(F 4 ) -2ϕ(F 3 ) = 2λ 2λ, and the forthcoming Lemma 5.1 would imply that f

q/2 ⌢f -f L 2 (R q + ) = 0 and f r ⌢f L 2 (R 2q-2r + ) = 0 for all r ∈ {1, . . . , q -1} \ { q 2 }. As shown in [5, Proof of Corollary 1.7], the relation f q-1 ⌢ f L 2 (R 2
+ ) = 0 implies that necessarily f = 0, and therefore that F = 0. Since ϕ[F 2 ] = λ > 0 we have achieved a contradiction, and the proof is concluded. 2

Ancillary lemmas

This section collects some technical results that are used in the proof of Theorem 1.3.

Lemma 5.1 Let q 2 be an even integer, and consider a sequence

{f n : n 1} ⊂ L 2 (R q + ) of mirror symmetric functions such that f n 2 L 2 (R q + ) = λ > 0 for every n. As n → ∞, one has that ϕ[I(f n ) 4 ] -2 ϕ[I(f n ) 3 ] → 2λ 2 -λ if and only if f n q/2 ⌢f n -f n L 2 (R q + ) → 0 and f n r ⌢f n L 2 (R 2q-2r + ) → 0 for all r ∈ {1, . . . , q - 1} \ { q 2 }.
Proof. The product formula yields

I(f n ) 2 -I(f n ) = λ + I(f n 0 ⌢f n ) + I(f n q/2 ⌢f n -f n ) + 1 r q-1 r =q/2 I(f n r ⌢f n ).
Using the isometry property and the fact that multiple Wigner integrals of different orders are orthogonal in L 2 (A , ϕ), we deduce that

ϕ[(I(f n ) 2 -I(f n )) 2 ] = λ 2 + f n 0 ⌢f n 2 L 2 (R 2q + ) + f n q/2 ⌢f n -f n 2 L 2 (R q + ) + 1 r q-1 r =q/2 f n r ⌢f n 2 L 2 (R 2q-2r + ) = 2λ 2 + f n q/2 ⌢f n -f n 2 L 2 (R q + ) + 1 r q-1 r =q/2 f n r ⌢f n 2 L 2 (R 2q-2r + ) ,
and the desired conclusion follows because ϕ

[I(f n ) 2 ] = f n 2 L 2 (R q + ) = λ. 2
Lemma 5.2 Let m 2 be an integer, let q 2 be an even integer, and recall the notation adopted in (4.9). Assume

{f n : n 1} ⊂ L 2 (R q + ) is a sequence of mirror symmetric functions satisfying f n 2 L 2 (R q + ) = λ > 0 for every n. If f n q/2 ⌢f n -f n 2 L 2 (R q + ) → 0 as n → ∞, then (r 1 ,...,r m-1 )∈Dm (. . . ((f n r 1 ⌢f n ) r 2 ⌢f n ) . . . f n ) r m-1 ⌢ f n → ϕ[Z(λ) m ] = m j=1 λ j R m,j , (5.10)
as n → ∞.

Proof. Assume that f n q/2 ⌢f n ≈ f n (given two sequences {a n } and {b n } with values in some normed vector space, we write a n ≈ b n to indicate that a nb n → 0 with respect to the associated norm), and consider (r 1 , . . . , r m-1 ) ∈ D m . Using the identities f n

0 ⌢f n = f n ⊗ f n , f n q ⌢f n = f n 2 L 2 (R q + ) = λ and f n q/2 ⌢f n ≈ f n , it is evident that (. . . ((f n r 1 ⌢f n ) r 2 ⌢f n ) . . . f n ) r m-1 ⌢ f n → λ j ,
where j equals the number of the entries of (r 1 , . . . , r m-1 ) that are equal to q. It follows that, for every m 2, there exists a polynomial w m (λ) (independent of q) such that, for every sequence {f n } as in the statement, (r 1 ,...,r m-1 )∈Dm

(. . . ((f n r 1 ⌢f n ) r 2 ⌢f n ) . . . f n ) r m-1
⌢ f n → w m (λ). Now consider the case q = 2 and f n = f = p i=1 e i ⊗e i , where p 1 and {e i : i = 1, ..., p} is an orthonormal system in L 2 (R q + ). The following three facts are in order: Lemma 5.4 Let m 2 be an integer, let q 2 be an even integer, and recall the notation adopted in (4.9). Assume {f n : n 1} ⊂ L 2 (R q + ) is a sequence of mirror symmetric functions satisfying f n 2 L 2 (R q + ) = λ > 0 for every n. If (r 1 , . . . , r m-1 ) ∈ E m and if f n r ⌢f n L 2 (R 2q-2r + ) → 0 for all r ∈ {1, . . . , q -1} \ { q 2 }, then

(. . . ((f n r 1 ⌢f n ) r 2 ⌢f n ) . . . f n ) r m-1 ⌢ f n → 0, as n → ∞.
Proof. Let j ∈ {1, . . . , m -1} be the smallest integer such that r j ∈ {1, . . . , q -1} \ { q 2 }. Then ⌢ f n (using f n q/2 ⌢f n ≈ f n and f n q ⌢f n = λ)

( * * ) C (f n ⊗ . . . ⊗ f n ) ⊗ (f n ⊗ r j f n ) × f n m-j-1 L 2 (R q + ) (by Cauchy-Schwarz) = C f n r j ⌢f n L 2 R 2q-2r j + (since f n 2 L 2 (R q + ) = λ) -→ 0, as n → ∞.
In the previous computations, we have adopted the following conventions: (a) C is a finite constant independent of n that may change from line to line, (b) the tensor products in ( * ) and ( * * ) have an unspecified order which depends on (r 1 , ..., r k-1 ), and (c) the first norm in ( * * ) refers to an appropriate L 2 (R s + ) space, for some s depending of the order of the tensor product.

2

Definition 2 . 1

 21 (i) Given an integer m 1, we write [m] = {1, ..., m}. A partition of [m] is a collection of non-empty and disjoint subsets of [m], called blocks, such that their union is equal to [m]. The cardinality of a block is called size. A block is said to be a singleton if it has size one.

  (iii) For every m 1, the quantity C m = |N C(m)|, where |A| indicates the cardinality of a set A, is called the mth Catalan number. One sets by convention C 0 = 1. Also, recall the explicit expression C m = 1 m+1 2m m .(iv) We define the sequence {R m : m 0} as follows: R 0 = 1, and, for m 1, R m is equal to the number of partitions in N C(m) having no singletons.

Definition 3 . 1 (

 31 L p spaces) (i) For 1 p ∞, we write L p (A , ϕ) to indicate the L p space obtained as the completion of A with respect to the norm a p = ϕ(|a| p ) 1/p , where |a| = √ a * a, and • ∞ stands for the operator norm.

2 L 2 (R 2 + 2 Remark 5 . 3

 222253 (a) I( p i=1 e i ⊗ e i ) has the same law as Z(p) (see Remark 3.2), (b) f ) = p, and (c) f 1 ⌢f = f . Since E m = ∅ for q = 2, the previous discussion (combined with (4.9) and Proposition 2.4) yields that, for every m 2, w m (p) = ϕ[Z(p) m ] = m j=1 p j R m,j , for every p = 1, 2, .... Since two polynomials coinciding on a countable set are necessarily equal, we deduce that w m (λ) = ϕ[Z(λ) m ] for every λ > 0. By inspection of the arguments used in the proof of Lemma 5.2, one deduces that R m = |D m |, for every m 2.

(

r j- 1 ⌢≈

 1 ( * ) C (. . . ((f n ⊗ . . . ⊗ f n )

  and the proof of Proposition 2.4 is concluded. 2

	Remark 2.5 (i) Relation (2.4) is well known -see e.g. [2, Section 5] for an alternate proof
	based on "difference triangles".

(ii) Using the last two points of Example 2.2, we deduce from (2.3) that ϕ


Gilles Puy

Pierre Vandergheynst

Rémi Gribonval

Yves Wiaux

Spread Spectrum for Universal Compressive Sampling

We propose a universal and efficient compressive sampling strategy based on the use of a spread spectrum technique. The method essentially consists in a random pre-modulation of the signal of interest followed by projections onto randomly selected vectors of an orthonormal basis. The effectiveness of the technique is induced by a decrease of coherence between the sparsity and the sensing bases. The sensing scheme is universal for a family of sensing bases in the sense that the number of measurements needed for accurate recovery is optimal and independent of the sparsity matrix. It is also efficient as sensing matrices with fast matrix multiplication algorithms can be used. These results are confirmed experimentally through analyses of the phase transition of the 1 -minimization problem.

II. REDUCING THE MUTUAL COHERENCE BY PRE-MODULATION

In the absence of pre-modulation, i.e. when C is reduced to the identity matrix, the compressive sampling theory already demonstrates that a small number m N of random measurements is sufficient for an accurate and stable reconstruction of α [START_REF] Rauhut | Compressive Sensing and Structured Random Matrices[END_REF]. However, the recovery conditions depend on the mutual coherence µ = max 1i,jN |φi, ψj | between Φ and Ψ. The performance is optimal when the bases are perfectly incoherent, i.e. µ = N -1/2 , and unavoidably decreases when µ increases.

The spread spectrum technique proposed in this work significantly reduces the mutual coherence µ towards its optimal value [START_REF] Puy | Universal and Efficient Compressed Sensing Strategy through Spread Spectrum Modulation[END_REF]. In the presence of a digital pre-modulation by a random Rademacher or Steinhaus sequence c ∈ C N , the mutual coherence µ = max 1i,jN |φi, C ψj | is essentially bounded by the moduluscoherence β 2 (Φ, Ψ) = max 1i,jN P N k=1 |φ * ki ψ kj | 2 . Indeed, we can show that the mutual coherence µ satisfies

N -1/2 µ β (Φ, Ψ) p 2 log (2N 2 /), (3)
with probabilty at least 1 -.

This work is supported by the CIBM of the Geneva, Lausanne Universities and EPFL, by the Leenaards and Louis-Jeantet foundations, by the SNSF (grant PP00P2-123438), by the EU FET-Open project FP7-ICT-225913-SMALL, and by the EPFL-Merck Serono Alliance award. For universal sensing bases Φ, e.g. the Fourier, Hadamard, or noiselet transform, we have β (Φ, Ψ) = N -1/2 whatever the sparsity matrix Ψ. The mutual coherence µ is thus equal to its optimal value, up to a logarithmic factor, whatever the sparsity matrix considered! III. SPREAD SPECTRUM UNIVERSALITY Theorem 1. Let c ∈ C N , with N > 3, be a random Rademacher or Steinhaus sequence and y satisfying equation [START_REF] Rauhut | Compressive Sensing and Structured Random Matrices[END_REF]. For universal sensing bases Φ ∈ C N×N and for a universal constant C > 0, if m C s log 8 (N ), then α is the unique minimizer of the 1-minimization problem [START_REF] Puy | Universal and Efficient Compressed Sensing Strategy through Spread Spectrum Modulation[END_REF] with probability at least 1 -O " N -log 3 (N) " .

For universal sensing bases, the spread spectrum technique is thus universal: the recovery condition does not depend on the sparsity basis and the number of measurements needed to reconstruct sparse signals is optimal in the sense that it is reduced to the sparsity level s. The experimental study of the phase transitions of the 1-minimization problem confirms this result (see Figure 1). The spread spectrum technique is also efficient as the pre-modulation only requires a sample-by-sample multiplication between x and c and fast matrix multiplication algorithms are available for several universal sensing bases such as the Fourier, Hadamard, or noiselet bases.

IV. CONCLUSION

We presented a universal and efficient compressive sampling strategy based on spread spectrum. For applications such as radio interferometry and MRI, this technique is of great interest to optimize the number of measurements needed for an accurate recovery [START_REF] Wiaux | Spread spectrum for imaging techniques in radio interferometry[END_REF], [START_REF] Puy | Accelerated MR imaging with spread spectrum encoding[END_REF].

1 )

 1 I. SPREAD SPECTRUM TECHNIQUE Let x ∈ C N be an s-sparse digital signals in an orthonormal basis Ψ = (ψ1, ..., ψN ) ∈ C N×N and α ∈ C N be its decomposition in this basis: α = Ψ * x. The spread spectrum technique consists in a pre-modulation of the original signal x by a wide-band signal c = (c l ) 1lN ∈ C N , with |c l | = 1 and random phases, and a projection onto m randomly selected vectors of another orthonormal basis Φ = (φ1, ..., φN ) ∈ C N×N [2]. The indices Ω = {l1, . . . , lm} of the selected vectors are chosen independently and uniformly at random from {1, . . . , N}. We denote Φ * Ω the m × N matrix made of the selected rows of Φ * . The measurement vector y ∈ C m thus reads as y = AΩ α with AΩ = Φ * Ω CΨ ∈ C m×N . (In the above equation, the matrix C ∈ C N×N stands for the diagonal matrix associated to the sequence c. Finally, we aim at recovering α by solving the 1-minimization problem arg min ᾱ∈C N ᾱ1 subject to y = AΩ ᾱ.

Fig. 1 .

 1 Fig. 1. Phase transition of the 1 -minimization problem for sparse signals in the Fourier basis and random selection of Fourier (first and third panels) or Hadamard (second and fourth panels) measurements without and with random modulation. The dashed green line indicates the weak phase transition of Donoho-Tanner [3] and the color bar goes from white to black indicating a probability of recovery from 0 to 1. The domain of recovery becomes optimal with the spread spectrum technique. Definition 1. (Universal sensing basis) An orthonormal basis Φ ∈ C N×N is called a universal sensing basis if all its entries φ ki , 1 k, i N , are of equal complex magnitude.


Ammar Adrien Bellanger

A Oulamara

Scheduling hybrid flowshop with parallel batching machines and compatibilities

Keywords: Hybrid flowshop problem, batch processing machines, task compatibilities

Scheduling hybrid flowshop with parallel batching

machines and compatibilities.

Introduction

In this paper we consider a two-stage hybrid flowshop scheduling problem, where each of n tasks is to be processed first at stage one and then at stage two. The first stage contains several identical discrete machines and the second stage contains several identical batching machines. Each discrete machine can process no more than one task at time, and each batching machine can process up to k tasks simultaneously in a batch. The batch processing time is equal to the maximal processing time of the tasks in this batch, and all tasks of the same batch start and finish together. The processing of task j on any machine of stage one requires p j time units, and on any machine of stage two the processing time q j lies in closed interval [a j , b j ]. The terms initial and terminal endpoints will refer to a j and b j , respectively. On the second stage the tasks are processed in batches. A batch is a set of tasks with the additional constraint that the tasks of the same batch have to be compatible. A compatibility is a symmetric binary relation in which a pair (i, j) of tasks is compatible if they share a similar processing time on the second machine (i.e, [a i , b i ] ∩ [a j , b j ] = ∅), so an undirected compatibility graph G = (V, E) -which is an interval graph-is defined, where V is the set of tasks and a pair of tasks is an element of the edge set E if and only if they are compatible. The batch processing time on the batching machine is determined as the maximum initial endpoint a j of compatible tasks. For each batch B, denote its processing time on the second machine as q(B) = max{a j | j ∈ B}. For a given schedule, task completion times C j , j = 1, . . . , n can be calculated. If task j belongs to batch B on the second stage, then C j = C 2 (B), where C 2 (B) is the time at which a machine on stage two finishes the processing of batch B. The objective is to find a schedule which minimizing the completion time of the latest batch C max = max{C j | j = 1, . . . , n}. Following the standard scheduling notation, see Graham et al. [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling : a survey[END_REF], we denote the problem formulated above as F H2Bm 1 , m 2 |pbatch(II), G p = INT, k < n|C max , where m 1 and m 2 represent the number of machines on first and second stage, respectively, pbatch(II) means that the stage two is composed with parallel batching machines, G p = INT specifies that the compatibility graph is an interval graph, which depends on the processing times of tasks, and k < n specifies that the capacity of batching machines is a variable and it is part of the input. This problem is motivated by the scheduling of tire in the manufacturing industry. Indeed, making tires involves several steps, and requires a high degree of precision and control at each step of the process. This process begins by producing the gum-like material that will be milled and split into strips that become the sidewalls after adding steel and fabric cords to reinforce the rubber compound and provide strength. When all parts involved to make the tires are prepared, the main and difficult task can be started. A typical tire is built in a two-stage process. In the first stage (tire building), all components (sidewalls and tread) are assembled and radial tires are built on a round drum, which is a part of the tire building machine. The machine pre-shapes the tire into a form that is very close to the tire's final dimensions. The end result is called a green tire or uncured tire. In the second stage (tire curing), curing occurs through a series of chemical reactions. Tire curing is a high-temperature and high-pressure batch operation in which a pair of uncured tires is placed into a mold at a specified temperature. Each type of tire must be cured for a total duration in the interval of its total curing duration and total curing duration plus 4% of this value. Two kinds of tires can be cured together if they share a same value of total curing duration. After the mold is closed, the rubber compound flows into mold the shape and form the tread details and sidewall. The mold cannot be opened until the curing reaction is completed for both green tires on the same mold. As the rubber is a perishable material, the objective is to produce tires as soon as possible, which is equivalent to minimizing the completion time of the last product.

In the scheduling literature, intensive research involving a single batching machine without task compatibilities are studied for various objective functions and additional constraints. The main comprehensive study is that of Brucker et al. [START_REF] Brucker | Scheduling a batch processing machine[END_REF]. Potts and Van Wassenhove [START_REF] Potts | Integrating scheduling with batching and lotsizing : a review of algorithm and complexity[END_REF], Potts and Kovalyov [START_REF] Potts | Scheduling with batching : a review[END_REF] have published state-of-the-art surveys of the batch scheduling problem. A single batching machine with task compatibilities has been studied in Finke et al. [START_REF] Finke | Batch processing with interval graph compatibilities between tasks[END_REF] for general graph and also for some special graphs. Boudhar and Finke [START_REF] Boudhar | Scheduling on a batch machine with job compatibility[END_REF] consider the problem of minimizing makespan in general compatibility graph. They show that the problem with capacity k = 2 of the batching machine is solvable in polynomial time as a weighted matching problem. For 3 ≤ k < n minimizing the makespan is NP-hard, even for split graph.

For flowshop system, Potts et al. [START_REF] Potts | Scheduling batches with simultaneous job processing for two-machine shop problems[END_REF] studied the flowshop problem with two batching machines. They offered a polynomial algorithm for the problem of minimizing batch completion time, when both batching machines can process an unbounded number of tasks in the same batch, and proved the NP-hardness of this problem when at least one of the machines can process up to k tasks in the same batch k < n. Oulamara et al. [START_REF] Oulamara | Flowshop scheduling problem with batching machine and task compatibilities[END_REF] consider the two-machine flowshop problem where the first machine is a discrete machine and the second is a batching machine. The objective is to minimize the makespan. The tasks in the same batch have to be compatible. One of their result is used in our study. Given a batching machine with capacity k and each task j has processing time given as an interval [a j , b j ]. Minimizing the total batch processing time is solvable in O(nlogn) by listing the intervals in nonincreasing order of their initial endpoint a j and forming the first batch from the first k compatible tasks, forming the second batch with the next k compatible tasks and so on. We call this rule, Full-Compatible-Batch-Largest-Processing-Time (FCBLPT). Oulamara et al. [START_REF] Oulamara | Scheduling a no-wait flowshop with unbounded batching machines[END_REF] studied the no-wait flowshop problem with two batching machines, and proposed a polynomial algorithm for the above problem, though they also extended their studies to the case of m batching machines. Other related results for the case of flowshop batching machine can be found in [START_REF] Lin | Batch scheduling in the no-wait two-machine flowshop to minimize the makespan[END_REF], [START_REF] Oulamara | Flowshop problems with batch processing machines[END_REF].

Although extensive research has been carried out on flowshops with batching machines, to the best of our knowledge, the problem of hybrid flowshop involving batching machines and task compatibilities has not been considered before. The case of classical hybrid flowshop is extensively considered in the literature, Lee and Vairaktarakis [START_REF] Lee | Minimizing makespan in hybrid flowshop[END_REF], Gupta et al. [START_REF] Gupta | Heuristics for hybrid flow shops with controllable processing times and assignable due dates[END_REF], Guinet et al. [START_REF] Guinet | A computational study of heuristics for two-stage flexible flowshop[END_REF], Allaoui and Artiba [START_REF] Allaoui | Scheduling two-stage hybrid flow shop with availability constraints[END_REF], Haouari and M'Hallah [START_REF] Haouari | Heuristic algorithms for the two-stage hybrid flowshop problem[END_REF].

The reminder of this paper is organized as follows. In section 2, we introduce the notation used in this paper. In section 3 we establish lower bounds, heuristics with computational experiments for the considered problem. Section 5 presents a PTAS algorithm scheme in the case of uniform processing time on the first stage.

Notations

The following notations are used throughout the paper:

• m 1 (m 2 ) : The number of machines on the first (second) stage.

• m = max{m 1 ; m 2 }.

• p j : The processing time of task j on any machine of the first stage.

• q j : The processing time of task j on any machine of the second stage, the value of q j lies within interval [a j , b j ].

• k : The batch capacity of machines of the second stage, 2 k < n.

• q(B l ) : The processing time of batch B l on the second stage, q(B l ) = max{a j |j ∈ B l }.

The example below illustrates the considered scheduling problem, with n = 8, k = 2. The processing times are given in Table 1, whereas Figure 1 shows the compatibility graph. A feasible schedule S = (T 1 , T 8 ), (T 6 , T 7 ), (T 3 , T 5 ), (T 2 , T 4 ) contains four batches, its Gantt chart is given in Figure 2.

[Insert Figure 1

Several machines on each stage

In this section we consider the general case in which each stage contains several machines, denoted by F H2B(m 1 , m 2 ). We start by presenting three lower bounds and three heuristics along with their worst case analysis.

Lower bounds

In the following we derive three lower bounds to be used to evaluate the performance of approximate heuristics. The first and the second are machine-based bounds, whereas the third is job-based bound. Let C max be the minimum makespan.

First, observe that all the processing on the first stage cannot be completed before time

P i p i m 1 . Therefore, C max ≥ LB 1 = n i=1 p i m 1 + min 1≤j≤n a j .
On the other hand, the processing at the second stage cannot be completed before the minimal load of that stage, i.e. the total processing on the second stage is greather than C max (B) divided by m 2 , where C max (B) is obtained by the FBCLPT algorithm. Therefore,

C max ≥ LB 2 = min 1≤i≤n p i + C max (B) m 2 .
The last lower bound is based on the largest processing time, i.e.

C max ≥ LB 3 = max 1≤i≤n {p i + a i }.

Heuristics with worst-case performance

In this section, we investigate the worst-case analysis of three heuristic algorithms. These heuristics are based on the combination of well known rules for machine scheduling.

Before presenting these heuristics, we show the efficiency of the H-FCBLPT heuristic on scheduling of parallel batching machines (P B(m)|G = INT, k < n|C max ) that would be useful in the rest of the paper.

Algorithm H-FCBLPT

1. Apply FCBLPT rule to construct a list of batches.

2. Order the batches in nonincreasing order of their processing time and assign them to the machines as they become available.

Lemma 1 The H-FCBLPT rule approximate the problem P B(m)|G p = INT, k < n|C max with ratio of ( 4 3 -1 3m ). Proof. The H-FCBLPT heuristic starts by constructing a list of batches with minimal total processing times, Oulamara et al. [START_REF] Oulamara | Flowshop scheduling problem with batching machine and task compatibilities[END_REF], and it order the batches in nonincreasing order of their processing times and assigns them to the machines as they become available. In fact, the second step of H-FCBLPT heuristic applies the LPT rule to the P ||C max problem obtained by aggregating the jobs in the batches, then the ratio ( 43 -1 3m ) of Graham [START_REF] Graham | Bounds on multiprocessor timing anomalies[END_REF]. In the rest of this section, we present three heuristics and their worst-case analysis when each stage contains several machines.

Heuristic H LP T

Heuristic H LP T schedules tasks at each stage independently, in a way that tasks are scheduled on the first stage following LPT rule, and then batched using the FCBLPT rule. Note that batches are carried out on the second stage in the LPT order.

Algorithm H LP T 1. Reindex tasks in a LPT order and let L be the list of tasks. On the first stage, schedule each task of L in the order in which they appear in the list on the first available machine. Let t be the completion time of all tasks.

2. Apply FCBLPT rule to construct a list of batches and denote by L B the obtained list. , and this bound is tight. Proof. Let S H LP T be the schedule produced by heuristic H LP T . Let us consider the two stages independently. At the first stage, the LPT rule gives an approximation ratio of ( 43 -1 3m 1 ). At the second stage, one has a scheduling problem with parallel batching machines (P B(m)|G p = INT, k < n|C max ), which is approximated with a ratio of ( 43 -1 3m 2 ) by FCBLPT heuristic (Lemma 1). Therefore,

C max (S H LP T ) C max (S H P m 1 ) + C max (S H Bm 2 ) 4 3 -1 3m 1 C max (S * P m 1 ) + 4 3 -1 3m 2 C max (S * Bm 2 )
. Let S * be the optimal schedule for hybrid flowshop problem, and C max (S * ) its makespan, then

C max (S * ) C max (S * P m 1 ) and C max (S * ) C max (S * Bm 2 ). Hence, C max (S H LP T ) 4 3 -1 3m 1 C max (S * H P m 1 ) + 4 3 -1 3m 2 C max (S * Bm 2 ) 8 3 -2 3m C max (S * ).
Type Tasks number

p j [a j , b j ] A 1 2 2m -1 [ǫ; 2m -1] A 2 2 2m -2 [ǫ; 2m -1] ... A m-1 2 m + 1 [ǫ; 2m -1] A m 3 m [ǫ; 2m -1] B 1 2 ǫ [2m -1; 2m -1] and [2m -1 -ǫ; 2m -1 -ǫ] B 2 2 ǫ [2m -2; 2m -2] and [2m -2 -ǫ; 2m -2 -ǫ] ... B m-1 2 ǫ [m + 1; m + 1] and [m + 1 -ǫ; m + 1 -ǫ] B m 3 ǫ [m; m], [m -ǫ; m -ǫ] and [m -2ǫ; m -2ǫ] C nb C ǫ [ǫ; ǫ]
Table 2: Task processing times.

Therefore,

C max (S H LP T ) C max (S * ) 8 3 - 2 3m .
Thus, the heuristic H LP T provides a solution with a performance ratio bounded by 8 3 -2 3m . Now we present an instance for which this upper bound is reached. Denote by I an instance for the hybrid flowshop problem with m machines on stage one and two, composed of classes A, B and C containing 2m + 1, 2m + 1 and nb C tasks, respectively. The processing times are given in Table 2 where ǫ < min{ m 3 ; (m-1) 2 2m+1 }. The capacity of batching machines is equal to 2m + 1. Without loss of generality, we assume that m is an even number.

[Insert Figure 3 about here] [Insert Figure 4 about here]

The makespan C max (S H LP T ) for the schedule S H LP T , produced by the heuristic H LP T , is equal to C max (S H LP T ) = 8m -2 -3ǫ (see Figure 3). While the optimal value of the makespan for the instance I is C max (S * ) = 3m + 2ǫ (see Figure 4). C max (S * ) is optimal as it reachs the lower bound LB 1 =

P p i m + min j a j . Therefore, C max (S H LP T ) C max (S * ) = 8m -2 -3ǫ 3m + 2ǫ . Hence lim ǫ→0 C max (S H LP T ) C max (S * ) = 8 3 - 2 3m .
If nb C > 0, when ǫ tend toward 0, then the tasks of type C are insignificant. Thus the result.

Heuristic H LBP T

This heuristic starts by constructing a list L B of batches using the FCBLPT rule. Then the tasks of each batch are scheduled at the Stage 1 according to LPT order. At Stage 2, batches are scheduled as soon as possible.

Algorithm H LBP T

1. Apply the FCBLPT rule on the list of tasks, and let L B be the list of batches, i = 1. Proof. Let S H LBP T be the schedule produced by heuristic H LBP T . Consider the two stages independently. The second stage is a parallel batching machines problem (P B(m)|G p = INT, k < n|C max ). The FCBLPT algorithm generates a solution within ( 43 -1 3m 2 ) of the optimal solution. The first stage is a classical parallel machines problem. It is known that the list scheduling gives a solution within (2 -1 m 1 ) of the optimal solution. Therefore,

Let

C max (S H LBP T ) C max (S H P m 1 ) + C max (S H Bm 2 ) 2 -1 m 1 C max (S * P m 1 ) + 4 3 -1 3m 2 C max (S * Bm 2 ).
Let S * be the optimal schedule for the hybrid flowshop problem, and C max (S * ) its makespan. Then C max (S * ) C max (S * P m 1 ) and C max (S * ) C max (S * Bm 2 ). Hence

C max (S H LBP T ) 2 -1 m 1 C max (S * P m 1 ) + 4 3 -1 3m 2 C max (S * Bm 2 ) 10 3 -4 3m C max (S *
). The tightness of this bound is an open question.

Heuristic H J

This heuristic is based on Johnson algorithm. It starts by constructing a list of batches using the FBCLPT rule, and reindex batches according to Johnson rule [START_REF] Johnson | Optimal two-and three-stage production schedules with setup times included[END_REF]. The batches are considered as tasks, and the processing time of each batch B is equal to

P j∈B p j m 1 and Q(B) m 2 on
C max (S H J ) C max (S H P m ) + C max (S H Bm ) 2 -1 m C max (S * P m ) + 2 -1 m C max (S * Bm ).
Let S * be the optimal schedule for the hybrid flowshop problem, and C max (S * ) its makespan. Then,

C max (S * ) C max (S * P m ) and C max (S * ) C max (S * Bm ). So, C max (S H J ) 2 -1 m C max (S * P m ) + 2 -1 m C max (S * Bm ) 4 -2 m C max (S * ).
4 One machine at the second stage

In this section we consider the case in which the second stage contains only one batching machine. We denote this problem as F H2B(m, 1). We present two heuristics with a performance guarantee.

Heuristic H LP T

This heuristic schedules tasks at each stage independently, i.e. tasks are scheduled on the first stage according to the LPT rule. Then, on Stage 2, tasks are batched using FCBLPT rule, and batches are scheduled on the batching machine as soon as possible.

Algorithm H LP T

1. Reindex tasks in LPT order and let L be the list of tasks. At the first stage, schedule each task of L in the order they appear in the list on the first available machine.

2. Apply FCBLPT algorithm, and let L B be the list of the produced batches.

Theorem 4

The heuristic S H LP T gives a schedule S H LP T in O(nlogn) with a performance guarantee of ( 7 3 -1 3m ) and this bound is tight.

Proof. The first stage is classical parallel machine problem. It is known that the list scheduling generates a solution within ( 4 3 -1 3m ) of the optimal solution. At the second stage, we have a problem of one batching machine (B|G p = INT, k < n|C max ), which is solved by FCBLPT rule ( [START_REF] Oulamara | Flowshop scheduling problem with batching machine and task compatibilities[END_REF]). Using the same technical aspect as in the proof of theorem 1, we obtain the ratio ( 73 -1 3m ). To show that this bound is tight, consider the following instance I of the problem with the capacity of the batching machine equal to 2m + 2. The list of tasks and their processing times are given in Table 4. Without loss of generality, we consider an even number of machines.

Type Tasks number

p 1 p 2 A 1 2 2m -1 [ǫ; 3m] A 2 2 2m -2 [ǫ; 3m] ... A m-1 2 m + 1 [ǫ; 3m] A m 3 m [ǫ; 3m] B 1 ǫ [3m; 3m] C nb C ǫ [ǫ; ǫ]
Table 3: Task processing times.

The makespan C max (S H LP T ) for schedule S H LP T produced by heuristic H LP T is equal to C max (S H LP T ) = 7m-1, Figure 5. The optimal value of the makespan is C max (S * ) = 3m+2ǫ, Figure 6. C max (S * ) is optimal it reaches the lower bound LB 1 = P p 1,i m + min j a j .

[Insert Figure 5 about here]

[Insert Figure 6 about here]

Therefore, C max (S H LP T ) C max (S * ) = 7m -1 3m + 2ǫ ,
and lim

ǫ→0 7m -1 3m + 2ǫ = 7 3 - 1 3m
.

Heuristic H J

This heuristic uses Johnson algorithm. It starts by applying FCBLPT rule to construct a list of batches, then a Johnson order [START_REF] Johnson | Optimal two-and three-stage production schedules with setup times included[END_REF] is used to sequence these batches. Algorithm H J 1. Apply FCBLPT rule to produce a list L of batches.

2. Reindex batches following Johnson order, where the processing time of each batch B is equal to

P j∈B p j m 1
and Q(B) m 2 on Stages 1 and 2, respectively. 3. Let B be the first batch of L, and L B be the list of tasks of B. At the first stage, schedule tasks L B in LPT order on the first available machine. Then, schedule a batch B on the batching machine as soon as possible. Remove B from L. If L = ∅, then return the schedule, otherwise go to step 3.

Theorem 5 Heuristic H J generates a schedules S H J in O(nlogn) with a performance guarantee of (3 -1 m ), and this bound is tight.

Proof. At the first stage, we have a parallel machines problem, where a list algorithm is used to schedule tasks within(2 -1 m ) of the optimal solution. On stage 2, the FBCLPT rule produces an optimal solution. Therefore, heuristic H J produces a schedule with ratio performance of (3 -1 m ). To show the tightness of this bound, consider the following instance I of problem with the capacity of the batching machine equal to 2m. The list of tasks and their processing times are given in Table 4. Let L be an integer.

Type Tasks number

p 1 p 2 A m -1 (m -1)L [ǫ; mL] B m -1 L [ǫ; mL] C 1 mL [ǫ; mL] D 1 ǫ [mL; mL] E nb E ǫ [ǫ/2; ǫ/2]
Table 4: Task processing times.

The makespan C max (S H J ) for schedule S H J produced by heuristic H J is equal to C max (S H J ) = (3m -1)L, Figure 7. The optimal value of the makespan is C max (S * ) = mL + 2ǫ, Figure 6. C max (S * ) is optimal as it reaches the lower bound LB 1 = P p 1,i m + min j a j .

[Insert Figure 7 about here]

[Insert Figure 8 about here]

Therefore, C max (S H J ) C max (S * ) = 3m -1 m + 2ǫ . And lim ǫ→0 (3m -1)L mL + 2ǫ = 3 - 1 m .
This completes the proof.

One machine at the first stage

In this section we consider the case in which the first stage contains one machine and the second stage contains m parallel batching machines. We denote this problem as F H2B(1, m).

We present two heuristics along with their performance guarantee.

Heuristic H LBP T

This heurstic starts by creating a list L of batches using FCBLPT rule. Then the tasks of each batch are scheduled on Stage 1, and on Stage 2, each batch is scheduled on the first available machine.

Algorithm H LBP T

1. Apply FCBLPT rule and let L be the produced list of batches.

2. Let B be the first batch of L. Sequence tasks of B on the first machine. After their completion, schedule batch B at the second stage on the first available machine. Remove B from L, if L = ∅, then return the schedule, otherwise go to step 2.

Theorem 6 Heuristic H LBP T produces a schedule S H LBP T in O(nlogn) with a performance guarantee of ( 7 3 -1 3m ), and this bound is tight.

Proof. Since at the second stage, the LPT order gives a ( 4 3 -1 3m ) approximation ratio for parallel batching machines problem then, including the first stage, we obtain the ratio of ( 73 -1 3m ). To show that this bound is tight, consider the following instance I of problem with the capacity of the batching machines equal to 2. The list of tasks and their processing times are given in Table 5, and an even number of machines at second stage.

Type Tasks number p

1 p 2 A 1 2 ǫ [2m -1; 2m -1] et [2m -1 -ǫ; 2m -1 -ǫ] A 2 2 ǫ [2m -2, 2m -2] et [2m -2 -ǫ; 2m -2 -ǫ] ... A m-1 2 ǫ [m + 1; m + 1] et [m + 1 -ǫ; m + 1 -ǫ] A m 3 ǫ [m; m], [m -ǫ; m -ǫ] et [m -2ǫ; m -2ǫ] B 1 3m [ǫ; 2m] C nb C ǫ [ǫ; ǫ]
Table 5: Task processing times.

The makespan C max (S H LBP T ) for schedule S H LBP T produced by heuristic H LBP T is equal to C max (S H LBP T ) = 7m -1 -2ǫ, Figure 9. The optimal value of the makespan is C max (S * ) = (2m + 2)ǫ + 3m, Figure 10. C max (S * ) is optimal since it reaches the lower bound LB 1 = p 1,i + min j a j .

[Insert Figure 9 about here]

[Insert Figure 10 about here] Therefore,

C max (S H LBP T ) C max (S * ) = 7m -1 -2ǫ 3m + (2m + 2)ǫ ,
and lim

ǫ→0 7m -1 -2ǫ 3m + (2m + 2)ǫ = 7 3 - 1 3m
This completes the proof.

Heuristic H J

This heuristic uses Johnson algorithm. It starts by applying FCBLPT algorithm to construct a list of batches. Then, a Johnson order is used to sequence these batches. The processing time of each batch B is equal to j∈B p j and Q(B) m 2 on Stages 1 and 2, respectively.

Algorithm H J 1. Apply FCBLPT rule to produce a list L of batches.

2. Reindex the batches according to Johnson order. The processing time of each batch B is equal to j∈B p j and Q(B) m 2 on Stages 1 and 2, respectively. 3. Let B be the first batch of L, and L B be the list of tasks of batch B. Sequence tasks of B on the first machine. After their completion, schedule the batch B on the first available machine. Remove B from L. If L = ∅, then return the schedule, otherwise go to 3.

Theorem 7 Heuristic H J gives a schedule S H J in O(nlogn) with a performance guarantee of (3 -1 m ).

Proof. The proof is similar to that of theorem 6. Instead of an approximation ratio of ( 4 3 -1 3m ) obtained by the LPT order for parallel batching machines, we use here a list order that results a performance ratio of (2 -1 m ) for parallel batching machines. Thus we obtain a performance guarantee ratio of (3 -1 m ).

Computational experiments

In this section we mesure the efficiency of the heuristics as follows by calculating the relative distance between the solution given by the heuristic and the best lower bound:

D H moy = C max (H) -LB LB × 100
.

Experiments were done on two sets of 100 and 250 tasks, respectively. For each set of tasks, we have done two series of computational experiments. With regard to the first experiment, the initial endpoint a j of the interval processing time of tasks on the batching machine are generated from a uniform distribution [START_REF] Deng | A ptas for semiconductor burn-in scheduling[END_REF]100]. In the second experiments, they are generated from a uniform distribution [50, 500]. The terminal endpoints b j for the task j are given by b j = a j + a j × α where α ∈ {0.05, 0.15, 0.25}. For both sets, the processing times of tasks on Stage 1 are generated from a uniform distribution [START_REF] Deng | A ptas for semiconductor burn-in scheduling[END_REF]100]. We tested instances with 3 different couples of number of machines at each stage: the first case contains 1 machine on Stage 1 and 10 on Stage 2, denoted as 1-10. With the same notation, cases 10-1 and 10-10 denote the second and the third couple, respectively. For all instances, the capacity of batching machine, k, is equal to two. The comparative results are summarized in Tables 6 and7. For the parameter setting in Tables 12 and13, we can see that heuristic H LP T is outperformed by heuristics H LP BT and H J , even when one of each stage contains only one machine. Heursitics H LP BT and H J generate similar results with a minimal advantage to H J . This may be due to the fact that in H J the flowshop environment is better taken into count.

p 2i ∈ m 1 - m 2 α

Constant processing times at stage one

In this section, we analyze the case where each stage contains several machines (m 1 parallel machines on Stage 1 and m 2 parallel machines on Stage 2). The processing times of tasks are constant on Stage 1, and their interval processing times on Stage 2 are uniform, i.e., for all tasks i and j if a i ≤ a j , then b i ≤ b j . The uniform interval processing times on batching machines is a real assumption, as in the tire manufacturing (see section 1).

This scheduling problem can be considered as a problem of minimizing the makespan with generalized release dates on parallel batching machines. The processing tasks on Stage 1 are considered as generalized release dates. A generalized release date r i means that at time r i one has α i available tasks. In our case, at release date r 1 , one has m 1 available tasks, i.e., m 1 tasks are completed on Stage 1, and available for processing on Stage 2. At r 2 one has 2m 1 available tasks, and so on. This probem is denoted by P B(m 2 )|r, G p = INT, k < n|C max and P B(r) for

p 2i ∈ m 1 - m 2 α H LP T H LP
≤ i ≤ α = ⌈ n m 1 ⌉.
In the rest of this section, we use the term release dates instead of generalized release dates.

Since the problem P B(r) is NP-hard, this section focusses on setting a polynomial time approximation scheme (PTAS, for short) for the P B(r) problem. In other words, we need to find a solution within a (1 + ǫ) factor of the optimal solution in polynomial time, over all 0 < ǫ < 1. To get such PTAS, we perform several transformations to simplify the input of an instance into one with a simple structure. Each transformation increases the objective function value by less than 1 + O(ǫ). So with a constant number of transformations, the objective function value stays within 1 + O(ǫ) of the original optimum.

Li et al. [START_REF] Li | Minimizing makespan with release times on identical parallel batching machines[END_REF] exhibited an approximation scheme algorithm (PTAS) for the problem of minimizing makespan with release times on identical parallel batching machines. Afrati et al. [START_REF] Afrati | Approximation schemes for minimizing average weighted completion time with release dates[END_REF], Hall et Shmoys [START_REF] Hall | Approximation schemes for constrained scheduling problems[END_REF], et Deng et al. [START_REF] Deng | A ptas for semiconductor burn-in scheduling[END_REF] provide principle and results for PTAS algorithm.

Let r max = ⌈ n m 1 ⌉p be the maximum release date, a max = max{a j |1 ≤ j ≤ n} be the maximum initial endpoint over all tasks, and P (B) be the total processing times of batches obtained by applying the FCBLPT rule. Denote by opt the optimal value of the makespan. We have the following result.

Lemma 2 max{r max , a max , P (B) m 2 } opt r max + a max + P (B) m 2 .

Proof. It is obvious that max{r max , a max , P (B) m 2 } is a lower bound for the optimal solution of P B(r), since each of r max , a max and P (B) m 2 is a lower bound for the problem. To show the correctness of the upper bound, we exhibit a schedule with an objective value of at most r max + a max + P (B) m 2 . Consider the schedule obtained from the following algorithm: Let L be the list of batches obtained by the FCBLPT rule, and use a list scheduling algorithm to sequence batches, starting at time r max . Let B be the last scheduled batch. B starts no later than r max + P (B) m 2 , and must finish no later than r max + a max + P (B) m 2 . Thus, the correctness of the upper bound.

Let M = ǫ × max{r max , a max , C(B) m 2 }, where 0 < ǫ < 1. From Lemma 2, we can deduce that any optimal schedule has a makespan value lower than 3 ǫ M. Consider the first transformation on release dates. The idea is to transform each r i , i = 1, . . . , α, to a multiple integer of M, i.e. we round down each r i to the nearest multiple of M. Let ri = M⌊ r i M ⌋ be the rounded value of r i . We have the following result. Lemma 3 With (1 + ǫ) loss, we can assume that there are at most ( 1 ǫ + 1) distinct release dates in the original problem.

Proof. The gap between an original release date and its rounded value is at most M. So, a feasible schedule for the original problem can be obtained from the feasible solution of the rounded problem by moving forward all batches by an amount of at most M. Since M ǫ×opt, the transformation involves a (1+ǫ) loss. Furthermore, we have M ǫ×r max . Hence ⌊ r i M ⌋ 1 ǫ , for all i. Thus we obtain at most ( 1 ǫ + 1) distinct release times. Since the rounded problem contains ( 1 ǫ + 1) distinct release dates, where each release date is a multiple of M, we partition the time horizon interval [0, 3 ǫ M) into ( 1 ǫ + 1) disjoint intervals. We denote by

δ i = [(i -1)M, iM) the i th interval, i = 1, . . . , 1 ǫ and δ1 ǫ +1 = [( 1 ǫ M, ( 3 ǫ
)M). We assume that the ( 1 ǫ + 1) release dates are denoted by ρ 1 , ρ 2 , ..., ρ1 ǫ +1 , with ρ i = (i -1)M, i = 1, 2, . . . , 1 ǫ + 1. The second transformation concerns tasks. We split the set of tasks into two subsets, namely small tasks and large tasks. A task is called small if its initial endpoint of the interval processing time is less than ǫ × M. Otherwise, it is called large. A batch is called large if it contains at least one large task, and small otherwise.

Our polynomial time approximation scheme (PTAS) proceeds in two steps. First, we schedule large tasks optimally after one transformation on their processing times. In the second step, we schedule approximately the set of small tasks. Before proceeding further, let us present the following result.

Lemma 4 There exists an optimal schedule with the following properties :

1. On any one machine, the batches started at the same time interval are sequenced in nonincreasing batch processing times order.

2. On each interval, δ 1 to δ1 ǫ +1 , batches started at the same interval are filled in nonincreasing batch processing times order, such as each of them consists of k (or as many as possible) largest compatible and available number of tasks.

3. On each interval, δ 1 to δ1 ǫ +1 , there is at most one large batch that contains small tasks.

Proof. This lemma can be easily established by using exchange arguments.

Small tasks

In this section, we restrict our discussion to the case where all tasks are small.

First, we apply FCBLPT rule to obtain a list L of batches. This list is ordered in nonincreasing order of P B i k i where P B i is the processing time and k i is the number of tasks of batch B i . Then, at the beginning of each interval δ i , when there are enough number of tasks available to sequence the first batch of L, schedule this batch on the first available machine, otherwise we go to the next interval.

Algorithm ST

• Apply algorithm FCBLPT. Let L be the list of obtained batches. Reindex L in nonincreasing P B i k B i , where P B i denote the batch processing time and k B i the number of tasks of batch B i , respectively. Let B be the first batch of list L, and nb = 0.

• For each interval δ i 1. If there is no enough available tasks to process a batch B (i.e. m 1 ⌊ (i-1)M p ⌋nb ≤ 0) or if there is no available machine before the end of interval δ i (except for the last interval), then go to the next interval δ i+1 2. If enough tasks are available to process batch B (i.e. m 1 ⌊ (i-1)M p ⌋nb ≥ k B ) and there is an available machine, then schedule batch B on the first available machine. Remove B from L, nb = nb + k B go to step 1.

Lemma 5 Algorithm ST is a PTAS when all tasks are small with at most 1 + (2 + 1 m 2 )ǫ 2 loss. Proof. Denote by S and opt the optimal schedule and the optimal makespan, respectively. Let S and õ pt be the schedule obtained by Algorithm ST and the value of its makespan, respectively. Consider the last idle time interval ∆ in schedule S, and let t be the terminal endpoint of ∆. It is easy to see that t must be one of the modified release date ρ i , otherwise the batch scheduled after ∆ can be shifted to the right. Since all batches in S are small, then any batch that starts before t must be finished earlier than t + ǫM. Denote by à the set of all batches in S started after t. Since all batches of à are scheduled without idle times from time t + ǫM and S is obtained by list scheduling algorithm, then an upper bound on õ pt is

õ pt ≤ t + ǫM + B∈ Ã P B m 2 + P max B ≤ t + B∈ Ã P B m 2 + 2ǫM, (1)
where P max B is the largest processing time of batches of set Ã. Assume that B is the delayed batch from δ i to δ i+1 . We have that B∈ Ã P B = B∈ Ã\ B P B + P B ≤ B∈ Ã\ B P B + ǫM. Ã \ B represents the set of all tasks to be scheduled from time t.

We denote by A the list of batches scheduled after time t in the optimal schedule S. Looking at the construction and the reindexing operation in Algorithm ST, it is easy to deduce that

Large tasks

The scheduling of the large tasks is based on enumeration. In order to limit the number of feasible schedules, we use the technique of [START_REF] Afrati | Approximation schemes for minimizing average weighted completion time with release dates[END_REF] to get a number of distinct processing times independent of number of tasks. We round the initial endpoint of all interval processing times by multiplying every initial endpoint by (1 + ǫ). Next, we decrease it to the lower integer power of (1 + ǫ). The following lemma is due to Afrati et al. [START_REF] Afrati | Approximation schemes for minimizing average weighted completion time with release dates[END_REF].

Lemma 6 With (1 + ǫ) loss, we assume that all initial endpoint of interval processing times of large tasks are integer powers of (1 + ǫ).

This lemma ensures that the number of distinct processing times can be bounded by a constant number.

Lemma 7

The number of distinct initial endpoint of processing times of large tasks, v, is bounded by ⌊log 1+ǫ (1/ǫ) + 1⌋.

Proof. Let j be the shortest large task, we have a j ǫM ǫ 2 a max . From lemma 6, we may assume that a j = (1 + ǫ) x and a max (1 + ǫ) x+v-1 for some integer x. It follows that

a j = (1 + ǫ) x ǫ 2 (1 + ǫ) v-1 (1 + ǫ) x . Hence v ≤ ⌊1 + log 1+ǫ (1/ǫ 2 )⌋.
Let a 1 < a 2 < . . . < a v be the v distinct processing times of large tasks. We keep the compatibility relations between tasks. We use the concept of machine configurations and execution profiles, introduced by Hall and Shmoys [START_REF] Hall | Approximation schemes for constrained scheduling problems[END_REF].

Let σ be a feasible schedule. We delete from σ all tasks and small batches, and retain only empty large batches, which are represented by their processing times. For each machine, we call machine configuration, with respect of σ, the pair (λ, µ) with λ = (λ 1 , . . . , λ 1 ǫ +1 ) and µ = (µ 1,1 , . . . , µ 1,v , µ 2,1 , . . . , µ 2,v , , µ 1 ǫ +1,1 , . . . , µ 1 ǫ +1,v ) such that λ i is the total number of large batches started on that machine in interval δ i , and µ i,j , i = 1, . . . , 1 ǫ + 1, j = 1, . . . , v is the number of empty large batches started in δ i with processing time a j , thus v i=1 µ i,j = λ i , i = 1, . . . , 1 ǫ + 1. Since the length of each interval δ i , i = 1, . . . , 1 ǫ , is M, except for δ1 ǫ +1 which has length of 2 ǫ M, and each large batch has processing times greater than ǫM, then each δ i , i = 1, . . . , 1 ǫ contains at most 1 ǫ large batches and the last interval δ1 ǫ +1 contains at most 2 ǫ large batches. On the other hand, from Lemma 7, processing times of empty large batches are chosen from v values with v ≤ ⌊1 + log 1+ǫ (1/ǫ 2 )⌋. Then, when δ i contains w large batches, the number of possibilities for each interval δ i is at most v w configurations. Hence, when w takes all values from zero to 1 ǫ , the total number of configurations of vector µ i = (µ i,1 , . . . , µ i,v ) is equal to 1 + v + . . . + v 1/ǫ , and the number of machine configuration to consider for all intervals δ i can be bounded by (

1 + v + . . . + v 1/ǫ ) 1/ǫ × (1 + v + . . . + v 2/ǫ 2 ) < 2 1/ǫ × v 3/ǫ
, which is independent of n. Thus, for a given schedule, we define an execution profile as a tuple (m 1 , . . . , m ψ ), where m i is the number of machines with the configuration i for that schedule. Therefore, we may only consider (m + 1) ψ execution profile.

A PTAS for PB(r)

In this section we merge the two types of tasks in the same schedule to produce a polynomial approximation scheme for the P (r).

The main idea of PTAS Algorithm is as follows : given an execution profile σ and feasible assignement of large tasks to this profile, the objective is to schedule small tasks in intervals δ i (i = 1, . . . , 1 ǫ +1) each time it is possible, i.e. there are enough number of available tasks at each begining interval δ i and there is an idle time on machines in interval δ i . When a scheduling of a small batch in an interval idle time δ i crosses the interval δ i+1 , i.e. a small batch starts its execution in the interval δ i and completed in interval δ i+1 , we can strech the end of the interval δ i to make an extra space with length ǫM for a small batch such that it need not cross the interval. Since there are at most 1 ǫ intervals streched, then the following lemma.

Lemma 8 (Afrati et al. [START_REF] Afrati | Approximation schemes for minimizing average weighted completion time with release dates[END_REF]) With (1 + ǫ) loss, we restrict our attention to schedules in which no small batch crosses an interval.

From Lemma 3, we know that among the large batches started in the same interval, only one large batch may contain small tasks. Since all these small tasks are compatible between each other, we can stretch each interval to make an extra space of length ǫ × M to schedule the small tasks in the same small batch. Since there are ( 1 ǫ + 1) intervals, we obtain the following lemma.

Lemma 9 With (1 + ǫ + ǫ 2 ) loss, we assume that no small tasks is included in a large batch. Now we are ready to present the complete algorithm.

Algorithm LT-ST

• Get all possible execution profiles as mentioned in Section 7.2

• For each execution profile, set nb = 0 1. Assign a configuration for each machine according to the profile. If it is not possible, delete the profile.

2. For each machine and each interval, start the empty large batches specified by the execution profil as soon as possible in non-increasing processing times order. If some batch needs to be delayed to start in one of the next interval, then delete this profile.

3. For each interval, fill the empty large batches started in this interval in the order of non-increasing batch processing times such that each of them consists of b (or as many as possible) compatible tasks that have greater initial endpoints and no more than the processing time of the batch. If one of the batches remains empty, than delete the profile. Otherwise, add to nb, the number of sequenced tasks, and update the rest of available tasks to be scheduled in this interval, i.e. l δ i = m 1 .⌊(i -1)M/p⌋nb.

4. Run algorithm ST to schedule small tasks in the spaces left by the large batches.

• Select the feasible schedule with the smallest makespan.

Theorem 8 Algorithm LT-ST is a PTAS for problem P B(r).

Proof. Since an optimum schedule is associated with one of the (m + 1) ψ execution profiles and all execution profiles are explored, then a schedule obtained by Algorithm LT-ST approximates the optimal solution. Given an execution profile, Algorithm LT-ST generates an optimal schedule of large tasks for this profile. Invoking Algorithm ST yields at most 1 + (2 + 1 m 2 )ǫ 2 loss. Combining Lemmas 2, 5, 7 and 8, and taking the smallest one among the feasible schedules produced, Algorithm LT-ST generates an (1 + 4ǫ + (3 + 1 m 2 )ǫ 2 ) loss, and its time complexity is O(nlogn + n × (m + 1) ψ ).

Conclusion

In this paper we have considered a new application of two-stage hybrid flowshop problem that involves classical and batching machines. The batching machine can process several tasks per batch with the additional feature that the tasks of the same batch have to be compatible. A compatibility relation is defined between each pair of tasks. We have considered the makespan criterion. Since minimizing the makespan is NP-hard, we have presented three heuristics and their worst-case analysis. We have also considered two particular cases, namely, one discrete machine at the first stage and one batching machine at the second stage. When the processing times of the tasks are constant at the first stage, we have propossed a polynomial time approximation scheme.

Theorem 2

 2 B be the first batch of L B , and L B (B) be the list of tasks of B. Schedule tasks L B (B) at Stage 1 according to the LPT rule. Next, schedule the batch B on Stage 2 on the first available machine when all its tasks of B are completed at Stage 1. Remove B from L.If L = ∅, then return the schedule, otherwise go to step 2. The heuristic H LBP T gives a schedule S H LBP T in O(nlogn) with a performance guarantee of10 3 -4 3m .

3 .

 3 Schedule the first batch B of L B on the batching machine as soon as possible, i.e. when all tasks of B are completed on Stage 1. Remove B from L B . If L B = ∅, then return the schedule, otherwise go to step 3.

Figure 2 : 1 Stage 2 A 2 A 2 : 1 Figure 5 :A 1 : 2m - 1 A 1 : 2m - 1 A 2 : 2m - 2 A 2 : 2m - 2 A

 212221511112222 Figure 2: Feasible schedule S

Figure 6 : 2 Figure 7 : 2 A1 : 2m - 1 A2 : 2m - 2 A1

 627212 Figure 6: Optimal schedule S *

Figure 9 :Am- 2 : m + 2 Am- 1 :Figure 10 :

 922110 Figure 9: Schedule S H LBP T

Table 1 :

 1 Task processing times.

	about here]
	[Insert Figure 2 about here]

  3. Let B be the first batch of list L B . Schedule a batch B on stage two on the first available machine starting from time t. Remove B from L B . If L B = ∅, then return the schedule, else go to step 3.

	Theorem 1 The heuristic H LP T gives a schedule S H LP T in O(n log n) with a performance guarantee of 8 3 -2 3m

  Apply the FCBLPT rule on the list of tasks, and let L B be the reindexed list of batches obtained by applying Johnson algorithm. 2. Denote B the first batch of L B , and L B (B) be the list of tasks of B. Schedule tasks L B (B) at stage one according to the LPT rule. Then schedule batch B on the second stage on the first available machine, when all tasks of B are completed on the first stage. Remove B from L. If L = ∅, then return the schedule, otherwise go to step 2. The heuristic H J produces a schedule S H J in O(nlogn) with a performance guarantee of 4 -2 m .Proof. Let S H J be the schedule produced by heuristic H J . Consider the two stages independently. The second stage is a parallel batching machines problem (Bm|G p = INT, k < n|C max ), it is approximated with a ratio of (2-1 m ) by list scheduling. At Stage 1, one uses a list scheduling to schedule tasks, which gives a ratio of (2 -1 m ) to makespan. Therefore,

	2, respectively. Algorithm H J 1. Theorem 3	Stage 1 and

Table 6 :

 6 Experiments on D moy , for n=100

				H LP T	H LP Ta		H LP BT	H J
				moy	worst	moy worst	moy	worst	moy	worst
			0.05	2.962	4.007 0.244 0.273 0.244	0.273	0.244	0.273
		1-10	0.15 0.25	2.747 2.434	3.786 0.249 0.284 0.249 3.481 0.253 0.283 0.253	0.284 0.283	0.249 0.253	0.284 0.283
			0.05	15.693 19.783 4.683 7.795 1.739	2.765	0.233	0.701
	[5, 100]	10-1	0.15 0.25	14.552 18.804 6.103 9.187 1.848 15.152 19.154 5.918 8.399 1.965	3.316 2.990	0.255 0.287	0.613 0.755
			0.05	40.713 53.332	-	-8.326 12.101	8.338 11.933
		10-10	0.15 0.25	39.363 48.178 38.446 50.842	--	-8.790 12.255 -7.559 9.760	8.690 11.928 7.480 9.955
			0.05	14.337 17.475 0.264 0.323 0.264	0.323	0.264	0.323
		1-10	0.15 0.25	14.105 18.844 0.282 0.435 0.282 13.115 17.538 0.298 0.466 0.298	0.435 0.466	0.282 0.298	0.435 0.466
			0.05	2.879	4.075 0.791 1.405 0.408	0.703	0.060	0.176
	[50, 500]	10-1	0.15 0.25	2.382 1.860	3.272 1.181 2.207 0.421 3.244 1.393 1.950 0.494	0.699 0.779	0.077 0.067	0.300 0.177
			0.05	35.627 43.105	-	-7.516	9.135 10.779 16.966
		10-10	0.15 0.25	36.412 44.111 37.769 44.737	--	-8.037 -8.143 10.127 10.637 19.971 9.570 12.528 18.478

Table 7 :

 7 Experiments on D

						Ta	H LP BT	H J
				moy	worst	moy worst	moy worst	moy worst
			0.05	3.862	4.242 0.096 0.102 0.096 0.102 0.096 0.102
		1-10	0.15 0.25	3.615 3.632	4.431 0.097 0.101 0.097 0.101 0.097 0.101 4.402 0.097 0.102 0.097 0.102 0.097 0.102
			0.05	17.346 19.327 4.507 5.922 0.940 1.244 0.064 0.277
	[5, 100]	10-1	0.15 0.25	17.462 20.333 4.540 6.407 0.791 1.269 0.066 0.190 17.396 19.242 4.802 6.170 0.862 1.234 0.083 0.185
			0.05	43.802 48.198	-	-3.230 5.270 3.250 5.391
		10-10	0.15 0.25	42.032 46.273 42.600 46.323	--	-3.381 4.370 3.395 4.242 -3.162 4.496 3.166 4.560
			0.05	16.885 19.006 0.103 0.122 0.103 0.122 0.103 0.122
		1-10	0.15 0.25	16.676 18.983 0.106 0.174 0.106 0.174 0.106 0.174 16.799 18.556 0.109 0.170 0.109 0.170 0.109 0.170
			0.05	3.199	4.249 0.626 1.004 0.220 0.304 0.015 0.044
	[50, 500]	10-1	0.15 0.25	3.415 3.127	4.035 0.743 1.221 0.219 0.311 0.019 0.045 4.226 0.808 1.578 0.189 0.298 0.015 0.045
			0.05	38.351 44.161	-	-3.123 3.608 1.342 3.138
		10-10	0.15 0.25	40.447 43.943 39.356 44.929	--	-2.935 3.540 1.409 2.361 -3.101 3.593 1.353 2.175

moy , for n=250 short. Since the generalized release dates in our model correspond to completion times of tasks on Stage 1, then r i = i × p where p is the constant processing time of tasks on Stage 1, and at time r i there are i × m 1 available tasks, where 1

  B∈ Ã\ B P B ≤ B∈A P B . Thus B∈ Ã P B ≤ A P B + ǫM. It then follows that,

			t + B∈ Ã P B m 2	+ 2ǫM ≤ t + B∈A P B + ǫM m 2	+ 2ǫM
	Since t +	P	B∈A P B m 2

is a lower bound for opt then using inequality (1), we obtain õ pt ≤ opt

+ ǫM m 2 + 2ǫM. Since M ≤ ǫ × opt, we get õ pt ≤ (1 + (2 + 1 m 2 )ǫ 2 )opt.