Hossein Teimoori
email: hossein.teimoori@atu.ac.ir

Multiset Analogue

Hossein Teimoori Faal

A MULTISET ANALOGUE OF COFACTORS

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

Introduction

The determinant of a matrix was originally invented to find solutions of systems of linear algebraic equations. The initial efforts were made by many great mathematicians to formulating and proving the so-called Cramer's rule, Laplace expansion, and Cauchy-Binet determinantal identity, and these led them to find many interesting algebraic identities [START_REF] Brualdi | Determinantal identities: Gauss, Schur, Cauchy[END_REF]. The basic idea behind all these determinantal identities is to express the determinant of a matrix in terms of determinants of lower orders. These subdeterminants together with their corresponding signs are called cofactors. From algorithmic viewpoint finding combinatorial interpretations of determinants are more desirable than their linear algebraic manipulations for designing efficient parallel algorithms for computing the determinant [START_REF] Valiant | Why is Boolean complexity is difficult?[END_REF] . In particular, in the graph-theoretical setting, the computation of the determinant of a matrix A amounts to evaluating the signed weighted sum of cycle covers [START_REF] Brualdi | A combinatorial approach to matrix theory and its applications[END_REF] of its associated digraph D(A). Moreover, cofactors are also interpreted as the signed weighted sum of generalized cycle covers [START_REF] Teimoori | A multiset version of determinants and the coin arrangements lemma[END_REF]. Lyndon words play a central role in theory of combinatorics of words [START_REF] Lothaire | Combinatorics of words[END_REF] as a subfield of formal languages and automata theory [START_REF] Shallit | A second course in formal languages and automata theory[END_REF]. The author in [START_REF] Teimoori | A multiset version of determinants and the coin arrangements lemma[END_REF] has already obtained a multiset analogue of the classic determinant of a matrix by extending the idea of cycle covers to Lyndon covers. The basic idea behind the multiset analogue is to replace a sequence of disjoint cycles with a sequence of distinct Lyndon words. As a by product of combinatorial interpretation of determinants of matrices indexed by a multiset, he has also obtained a weighted generalization of the coin arrangements lemma [START_REF] Sherman | Combinatorial aspects of the Ising model of ferromagnetism. I. a conjecture of Feynman on paths and graphs[END_REF] which is a key lemma for proving Feynman conjecture about combinatorial interpretation of two-dimensional Ising model. The main goal of this paper is to find a multiset analogue of cofactors of a given matrix based on the idea of the generalized Lyndon covers. We will do this simply by passing from the combinatorics of permutations to the combinatorics of words. The paper will organize as follows. In Section 2, we first quickly review the basic definitions and notions related to the theory of combinatorics of permutations. Then, we review the graph-theoretical interpretations of determinants and cofactors as signed weighted sum over cycle covers and the generalized cycle covers, respectively. In Section 3, we first review the basic definitions form the theory of multisets and combinatorics of words. Then, we overview the multiset analogue of determinants by generalizing the idea of cycle covers to Lyndon covers. Finally, in Section 4, we give a multiset analogue of the graph-theoretical interpretation of cofactors based on the idea of the generalized Lyndon covers.

Basic Definitions and Notation

In this section, we first very briefly review the combinatorics of permutations from the reference [START_REF] Bona | Combinatorics of permutations[END_REF]. Then we briefly review the graph-theoretical interpretations of the determinant and cofactors of a matrix A based on the idea of cycle covers and the generalized cycle covers of the associated digraph D(A), respectively. For more information the reader may refer to the book [START_REF] Brualdi | A combinatorial approach to matrix theory and its applications[END_REF]. From here on, we will denote the set {1, 2, . . . , n} by [n]. Recall that any bijective function π :

[n] → [n] is a permutation. The representation of π as π = π 1 π 2 • • • π n is called the one-line representation of the permutation π. Definition 2.1. Let π = π 1 π 2 • • • π n be a permutation.
An inversion of π is a pair i, j of integers with 1 ≤ i < j ≤ n such that π i > π j . The number of inversions of π will be denoted by inv(π).

Definition 2.2. Let

π = π 1 π 2 • • • π n be a permutation of [n]. Let A = (a ij )
be a square matrix of order n. The sign sgn(π) of the permutation π is defined as sgn(π) = (-1) inv (π) . The weight wt(π) of the permutation π is defined to be wt

(π) = a 1π 1 a 2π 2 • • • a nπn .
Next, we give the classical definition of the determinant of a matrix. Here, we will denote the set of all permutations of the set [n] by S n . Definition 2.3. Let A = (a ij ) be a square matrix of order n. Then we define the determinant of A denoted by det(A), as follows

det(A) = ∑ π=π 1 π 2 •••πn∈Sn sgn(π)wt(π),
where π runs over the set of all permutations of the set [n]. Now, suppose A = (a ij ) is a square matrix of order n. We associate a digraph D = D(A) with the matrix A which plays an essential role in the graph-theoretical interpretations of the determinant of the matrix A. We have the following formal definition. Definition 2.4. For a given square matrix A = (a ij ) of order n, its associated digraph D = D(A) is defined as a digraph with the vertex set [n] and there is an arc from vertex i to vertex j, if a ij ̸ = 0. Whenever a ii ̸ = 0, we have a loop at vertex i. Definition 2.5. A linear subdigraph L of a digraph D is a spanning subdigraph of D in which each vertex has in-degree 1 and out-degree 1. Thus, by directed cycle decomposition of Eulerian digraphs, a linear subdigraph L consists of a spanning collection of pairwise vertex-disjoint cycles. The number of cycles contained in L is denoted by c(L). For a given square matrix A = (a ij ), the weight wt(L) of a linear subdigraph L of D(A) is defined as the product of the weights of its arcs and the weight of any arc (i, j) is defined to be a ij . Definition 2.6. Let A = (a ij ) be a square matrix of order n and D = D(A) its associated digraph. The sequence c = (c 1 , c 2 , . . . , c l ) of vertex-disjoint cycles of D such that ∑ l i=1 |c i | = n where |c i | is the length of the cycle c i is called a cycle cover of D. The sign sgn(c) of a cycle cover c is defined as sgn(c) = (-1) n-l . We also define the weight wt(c) of c to be the product of weights of its cycles and the weight wt(c i ) of each cycle

c i = (k 1 k 2 • • • k s-1 k s ) of length s is defined as wt(c i ) = a k 1 k 2 a k 2 k 3 • • • a k s-1 ks a ksk 1 .
We also need the following technical lemma due to Cauchy (see [START_REF] Brualdi | A combinatorial approach to matrix theory and its applications[END_REF]). We denote the number of cycles in the cyclic decomposition of π by cyc(π).

Lemma 2.1. Let π = π 1 π 2 • • • π n be a permutation of [n].
Then inv(π) and n -cyc(π) have the same parity. Therefore,

(-1) n-cyc(π) = (-1) inv(π) .
As a direct consequence of the Cauchy lemma and the cyclic decomposition of permutations, we have the following two equivalent graph-theoretical interpretations of the determinant of the matrix A. Lemma 2.2. Let A = (a ij ) be a square matrix of order n. Then

det(A) = ∑ L∈Lin(A) (-1) n-c(L) wt(L) = ∑ c∈Cyc(A)

sgn(c)wt(c), where Lin(A) is the set of all linear subdigraphs of D(A) and Cyc(A) is the set of all cycle covers of D(A).

Definition 2.7. Let A = (a ij ) be a square matrix of order n and

D = D(A) its associated digraph. The sequence c = (c 1 , c 2 , . . . , c l ) of disjoint cycles of D is called a partial cycle cover of D, if |c 1 | + • • • + |c l | ≤ n. A partial cycle cover c = (c 1 , c 2 , . . . , c l ) with k = |c 1 | + • • • + |c l | is also called an k-cycle cover of D.
The weight of an k-cycle cover c = (c 1 , c 2 , . . . , c l ) is defined as the product of the weights of its arcs and its sign is defined to be (-1) k-l .

Note that in the above definition, by convention, an empty sequence is a partial cycle cover or 0-cycle cover with the weight equal to 1.

Recall that for a matrix A of order n, its principal submatrix of order k,(k = 1, 2, . . . , n), is defined as a submatrix of A whose rows and columns are indexed by the same k-element subset of [n]. As a classical result, due to Laplace [START_REF] Brualdi | A combinatorial approach to matrix theory and its applications[END_REF], we know that the coefficient of t n-k in det(tI -A) is (-1) k times the sum of the determinants of the principal k × k submatrices of A. Thus, considering Lemma 2.2, we get the following well-known result.

Lemma 2.3. Let A = (a ij ) be a square matrix of order n. Then

det(I -A) = ∑ c=(c 1 ,...,c l )∈Cycp (-1) l wt(c),
where Cyc p (A) is the set of all partial cycle covers of D(A).

Recall from matrix theory that the (i, j)-minor M ij of the matrix A is the determinant of a matrix of size n -1 obtained from A by crossing out the ith row and the jth column of A. Moreover, the (i, j)-cofactor C ij corresponding to the entry a ij of the matrix A is defined, as follows (2.1)

C ij = (-1) i+j M ij .
Next, we give a graph-theoretical interpretation of the (i, j)-cofactor using the idea of 1-connection of vertex i to vertex j in associated digraph D(A) of A or equivalently, the generalized cycle cover in the digraph D(A). First, we start with the definition of 1-connection of a digraph. The first idea comes from [START_REF] Coates | Flow graph solutions of linear algebraic equations[END_REF] where the author associate with a matrix A = (a ij ), its Coates digraph which is a weighted digraph with the vertex set [n] and the weight of the arc (i, j) is a ji . Note that the weighted digraph D(A) has the weight a ij for the arc (i, j). We recall that the weight of a linear subdigraph of D(A) is defined as the product of the weights of its arcs. If i ̸ = j, then • exactly one arc leaves, but no arc enters, vertex i;

• exactly one arc enters, but no arc leaves, vertex j;

• for each vertex k ̸ = i, j, exactly one arc enters, and exactly one arc leaves, vertex k.

If i = j, then
• no arc enters or leaves vertex i;

• for each vertex k ̸ = i, exactly one arc enters, and exactly one arc leaves, vertex k.

Note that it is not hard to see that a 1-connection D[i → j] is a spanning subdigraph of D consisting of a path form i to j (of length zero, if i = j) and a (possibly empty) collection of the pairwise vertex-disjoint cycles having no vertex in common with the path. We will denote the number of those cycles in 1-connection D[i → j] by c(D[i → j]). The following lemma will be key in understanding of the connection between the graph-theoretical interpretations of the determinant of the matrix A and its (i, j)-cofactor. Lemma 2.4. Let (i, j) be an arc of digraph D(A). There is a bijection between the set of all linear subdigraphs of D(A) containing the arc (i, j) and all 1-connections of vertex j to vertex i of D(A).

Proof. Let L be an arbitrary linear subdigraph of D(A) containing the arc form vertex i to vertex j (the arc (i, j)). By the definitions of a linear subdigraph and a 1-connection, deleting the arc (i, j) from L yields a 1-connection D[j → i]. If i = j, the deleted arc is a loop at vertex i. Conversely, by adding an arc (i, j) to a given 1-connection D[j → i] we get a linear subdigraph L of D(A) containing the arc (i, j). □

The above lemma immediately implies that:

wt(L) = a ij wt(D[j → i]), c(L) = c(D[j → i]) + 1, (2.2)
where the weight of 1-connection D[i → j] is defined in similar way to its associated linear subdigraph as the product of the weights of its arcs. Next, we formally define a generalized (i, j)-cycle cover, as follows.

Definition 2.9. Let A = (a ij ) be a square matrix of order n and D = D(A) its associated digraph. For a ij ̸ = 0, the sequence c ij = ⟨p ij , c 1 , . . . , c l ⟩ is called the generalized (i, j)-cycle cover of the digraph D, if

• The sequence (c 1 , . . . , c l ) is a partial cycle cover of D and p ij is a path from vertex i to vertex j with no common vertex with the cycles c i (i = 1, 2, . . . , l), The weight wt(c ij ) is defined to be wt(c ij ) = wt(p ij )wt(c 1 ) • • • wt(c l ) and the weight of a path simply defined as the product of the weights of its arcs. The sign sgn(c ij ) is defined to be (-1) (n-1)-l .

• |p ij | + |c 1 | + • • • + |c l | = n -1,
If in Definition 2.9 the sequence (c 1 , . . . , c l ) is empty, we set l = 0. In this case the generalized (i, j)-cycle cover is just a path form vertex i to vertex j. Next, we need another key lemma. Recall that by the Laplace expansion formula for rows, we have

(2.3) det(A) = n ∑ j=1 a ij C ij .
Lemma 2.5. The cofactor C ij corresponding to the element a ij ̸ = 0 of A is the coefficient of a ij in the expansion of the determinant of A along the row i. Furthermore, we have

a ij C ij = ∑ L∈Lin ij (A) (-1) n-c(L) wt(L),
where Lin ij (A) is the set of all linear subdigraphs of D(A) containing the arc (i, j).

Proof. Considering the Laplace expansion formula (2.3), the first part is obvious. Now, by Lemma 2.2, we have

(2.4) det(A) = ∑ L∈Lin(A) (-1) n-c(L) wt(L) = n ∑ j=1 ∑ L∈Lin ij (A) (-1) n-c(L) wt(L),
for every fixed i ∈ [n], where Lin(A) is the set of all linear subdigraphs of D(A). Since a ij ̸ = 0, by subtracting formula (2.3) from (2.4) and considering the equalities in formula (2.2), we finally get

a ij C ij = ∑ L∈Lin ij (A) (-1) n-c(L) wt(L), as required. □ □
Now, we are ready to give two equivalent graph-theoretical interpretations of (i, j)-cofactor C ij . Theorem 2.6. Let A = (a ij ) be a square matrix of order n and D(A) its associated digraph. Let C ij be the cofactor corresponding to the element a ij ̸ = 0 of the matrix A. Then, we have

C ij = ∑ D[j→i]∈D ji (A) (-1) n-c(D[j→i])-1 wt(D[j → i]), = ∑ c ji =⟨p ji ,c 1 ,...,c l ⟩∈Cyc ji (A) sgn(c ji )wt(c ji ),

where D ji (A) is the set of all 1-connections from vertex j to vertex i of D(A) and Cyc ji (A) is the set of all generalized (j, i)-cycle covers of D(A).

Proof. The proof of the first interpretation is straight forward, considering Lemmas (2.4) and (2.5) and relations in (2.2). The two interpretations are equivalent based on Lemma (2.4) and the fact that there is a bijection between the set of all linear subdigraphs of D(A) and the set of all cycle covers of D(A), hence there is a bijection between the set of all linear subdigraphs of D(A) containing the are (i, j) and the set of all generalized (j, i)-cycle covers of D(A), as required.

□ □

Multiset Analogue of Determinants

In this section, we first quickly review the basics of the multiset theory and the combinatorics of words. Then, we briefly review a multiset analogue of the classical determinant of a matrix, based on the idea of word systems [START_REF] Teimoori | A multiset version of determinants and the coin arrangements lemma[END_REF]. We first recall that for a given ground set A, a multiset M over A is defined as a pair of ⟨A, f ⟩ where f : A → N 0 is a function. Here by N 0 we mean the set of all nonnegative integers. For each a ∈ A, the value f (a) is called the multiplicity of a. The cardinality of M = ⟨A, f ⟩ is defined to be N = ∑ a∈A f (a) . Definition 3.1. Let M 1 = ⟨A, f ⟩ and M 2 = ⟨A, g⟩ be two multisets over A. Then we say that M 1 is a submultiset of M 2 denoted by M 1 ⊆ M 2 if for all a ∈ A, we have f (a) ≤ g(a).

Definition 3.2.

Let M 1 = ⟨A, f ⟩ and M 2 = ⟨A, g⟩ be two multisets over A.

Then M 1 and M 2 are said to be equal, if for all a ∈ A f (a) = g(a).

Definition 3.3.

Let M be a multiset of cardinality N and let r be a positive integer satisfying r ≤ N . We define an r-permutation of M as an ordered arrangement of r objects of M . In particular, an N -permutation of M will also be called a permutation of M .

Next, we also need to have a quick review of combinatorics of words. The interested reader may consult the reference [START_REF] Lothaire | Combinatorics of words[END_REF].

For a finite alphabet A, a word is a (finite) sequence of elements of A. We denote the set of all words over alphabet A by A ⋆ . A sequence with no elements is called an empty word and is denoted by λ. We also denote the set of nonempty words over A by A + . A word u ∈ A ⋆ is a factor of a given word w, if there exists words w 1 and w 2 such that w = w 1 uw 2 . The factor u is called a proper factor of w if u ̸ = w. If w 1 (respectively w 2 ) is an empty word then u is called a prefix (respect. suffix) of the word w. A word w is primitive if it can not be written as a power of another smaller word. Two words w 1 and w 2 are said to be conjugate if one can obtain from the other by the cyclic shift of its elements. The binary relation of w 1 is conjugate with w 2 is an equivalence relation that partitions the set A ⋆ into conjugacy classes. The conjugacy class of a given word w denoted by (w) is called a circular word. A lexicographic order on the set of nonempty words A + is a total order on the alphabet A extended to words in the following way: For any w 1 , w 2 ∈ A ⋆ , w 1 ≺ w 2 if and only if either w 2 ∈ w 1 A + or w 1 = uap and w 2 = ubq, a ≺ b; a, b ∈ A; u, p, q ∈ A ⋆ . Definition 3.4. A Lyndon word is a primitive word that is minimal with respect to the lexicographic order in its conjugate class. We will denote the set of all Lyndon words with L.

Definition 3.5. Let M = {1 m 1 , . . . , n mn } be a multiset of cardinality N = ∑ n i=1 m i over [n]
. We associate a function f M with M which we call the set-indicator function of M , as follows

f M : [N ] → [n] f M (i l ) = l, i l ∈ [ ( l-1 ∑ j=1 m j ) + 1, l ∑ j=1 m j ], (1 ≤ l ≤ n),
where by convention we set ∑ 0 j=1 m j = 0 and for positive integers a and b, by [a, b] we mean the set of all integers between a and b including themselves.

Example 3.1. For M = {1 2 , 2 2 , 3 1 } of cardinality 5, we have f M : [5] → [3] f M (1) = 1, f M (2) = 1, f M (3) = 2, f M (4) = 2, f M (5) = 3.
Next, we define a matrix indexed by a multiset. Definition 3.6. Let M = {1 m 1 , . . . , n mn } be a multiset of cardinality N = ∑ n i=1 m i over the ground set [n]. We say that a square matrix A of order N is a matrix indexed by the multiset M if there is a square matrix A ′ of order n so that for all i, j ∈ [N ],

(A) ij = (A ′ ) f M (i)f M (j) .
Example 3.2. Let [3] = {1, 2, 3} be our ground set. For the multiset M = {1 2 , 2 2 , 3 1 } of cardinality 5, a matrix A = (a ij ) indexed by M in general has the following form ∑ n i=1 m i with the set-indicator function f M and let A = (a ij ) be a square matrix indexed by M . Assume that σ = σ 1 σ 2 • • • σ l is the cyclic decomposition of σ ∈ S N . We define the word system associated with the permutation σ as a multiset γ = ⟨γ 1 , γ 2 , . . . , γ l ⟩ of circular words, as follows. For each i (i = 1, 2, . . . , l), we associate with the cycle

A =      
σ i = (i 1 i 2 • • • i s ) of σ a circular word γ i = (f M (i 1 )f M (i 2 ) • • • f M (i s )
). The sign sgn(γ) of the word system γ = ⟨γ 1 , γ 2 , . . . , γ l ⟩, is defined to be sgn(γ) = (-1) N -l . The weight wt M (γ) of γ, is defined as the products of the weights of its circular words and the weight wt M (γ j ), j = 1, 2, . . . , l, of the circular word γ j = (j ⟨( 1 Hence, we get ) .

1 j 2 • • • j s ) is defined to be wt M (γ j ) = a j 1 j 2 a j 2 j 3 • • • a j s-1 js a jsj 1 .
mdet(A) = 2! ( ( -
Remark 3.1. Note that in Example 3.4 the word systems inside the parentheses in the first sum are consisting of only distinct circular primitive words, i.e., those which are not powers of any smaller words. It is also straight forward to see that the second sum is zero. This fact is not a mere coincidence. It leads to a multiset analogue of the graph-theoretical interpretation of determinants.

Next, we define the multiset analogue of the cycle cover motivated by Remark 3.1. To do this, we simply replace each primitive word with its corresponding Lydon word. Here is the formal definition. Definition 3.9. A word system γ = ⟨γ 1 , γ 2 , . . . , γ l ⟩ is a Lyndon cover of the multiset M if all γ i 's are circular Lyndon words and distinct. The weight and the sign of a Lyndon cover are defined in the same way that they are defined for a word system.

The weight wt M (γ ij ) of the generalized (i, j)-Lyndon cover γ ij is defined as the product of the weights of its components. The sign sgn(γ ij ) of γ ij is defined to be sgn(γ ij ) = (-1) (N -1)-r . Remark 4.1. Note that in the above definition the sum

|η ij | + |γ 1 | + • • • + |γ r |
is defined to be N and not N -1. It is because the lengths of a non-circular word w and the circular word (w) obtained from it are the same. But in the case of the generalized (i, j)-cycle cover, the length of a path is one less than the length of the cycle on the same vertex set. There is a bijection between the set of all Lyndon covers of M containing the word segment ij and the set of all generalized (j, i)-Lyndon covers of M .

Proof. Let γ = ⟨γ 0 , γ 1 , . . . , γ r ⟩ be a Lyndon cover so that γ 0 contains the word segment ij. Then, consider the class of all cyclic-shifts of the word γ 0 . One of these primitive words, say η ji , starts with j and ends at i. Hence by replacing γ 0 with η ji , we get a generalized (j, i)-Lyndon cover γ ji = ⟨η ji , γ 1 , . . . , γ r ⟩. Conversely, starting with η ji and obtaining the class of all its cyclic-shifts and naming the minimal element of the class γ 0 (with respect to the lexicographic order) yields a Lyndon cover γ = ⟨γ 0 , γ 1 , . . . , γ r ⟩. Furthermore, we have (4.1) wt M (γ) = a ij wt M (γ ji ), sgn(γ) = sgn(γ ji ).

□

Note that the standard definition of the cofactor (the equality (2.1)) corresponding to the entry a ij of the matrix A = (a ij ) does not work in the case where A is a square matrix indexed by the multiset M . This is because, when we cross out the ith row and jth column of the matrix A, we may obtain a submatrix B of A such that its rows and columns are indexed by submultisets M r and M c of M with M r ̸ = M c . To solve this problem, we use the idea behind Lemma 2.5 to define the correct multiset version of a cofactor of a matrix.

Definition 2 . 8 .

 28 Let D be a digraph with the vertex-set [n]. Let i and j be vertices of D. A 1-connection of vertex i to vertex j is a spanning subdigraph D[i → j] of D with the following properties:

  where |p ij | and |c i | denote the usual length of a path and a cycle, respectively.

Example 3 . 3 .Definition 3 . 8 .Example 3 . 4 .

 333834 For the multiset M = {1 2 , 2 2 , 3 1 } of cardinality N = 5 and the permutation σ = (1)(23)(45) of S 5 , the word system γ associated with σ is γ = ⟨(1), (12), (23)⟩.We will denote the multiset of all N ! word systems associated with the set of all N ! permutations of [N ] by Γ sys . Next, we present a multiset analogue of the classical combinatorial definition of the determinant of a matrix, as follows. Let A = (a ij ) be a square matrix indexed by the multiset M = {1 m 1 , . . . , n mn } of cardinality N = ∑ n i=1 m i . Then we define the determinant of A denoted by mdet(A), as followsmdet(A) = ∑ γ=⟨γ 1 ,γ 2 ,...,γ l ⟩∈Γsys sgn(γ)wt M (γ),where γ runs over the multiset of all N ! word systems associated with S N . For the multiset M = {1 1 , 2 2 } of cardinality N = 3, we have cycle notation word system weight (1)(2)[START_REF] Brualdi | A combinatorial approach to matrix theory and its applications[END_REF]

1 ) 3 - 1

 131 wt M (⟨(122)⟩) + (-1) 3-2 wt M (⟨(12), (2)⟩) ) + ( (-1) 3-3 wt M (⟨(1), (2), (2)⟩) + (-1) 3-2 wt M (⟨(1), (22)⟩)

Example 4 . 1 .Definition 4 . 4 .

 4144 Let M = {1 4 , 23 , 3 1 } be our multiset of cardinality N = 8 and let A = (a ij ) be a square matrix indexed by M . Then, clearlyγ 12 = ⟨1132, (112), (2)⟩, is a generalized (1, 2)-Lyndon cover of M , where η 12 = 1132 is (1, 2)-primitive word in M . We also have wt M (γ 12 ) = (a 11 a 13 a 32 )(a 11 a 12 a 21 )(a 22 ) and sgn(γ 12 ) = (-1) (8-1)-2 = -1.Next, we give a multiset version of Lemma 2.4. But, first we need one more definition. We say that the Lyndon cover γ = ⟨γ 1 , . . . , γ r ⟩ contains the word segment u, if one of γ i 's contains that word segment.

Lemma 4 . 1 .

 41 Let A = (a ij ) be a square matrix indexed by M with a ij ̸ = 0.

  a 11 a 11 a 12 a 12 a 13 a 11 a 11 a 12 a 12 a 13 a 21 a 21 a 22 a 22 a 23 a 21 a 21 a 22 a 22 a 23 a 31 a 31 a 32 a 32 a 33 Let M = {1 m 1 , . . . , n mn } be a multiset of cardinality N =

	
	    	.
	Definition 3.7.

Finally, we state the main result of this section without proof. For the proof see the reference [START_REF] Teimoori | A multiset version of determinants and the coin arrangements lemma[END_REF]. Theorem 3.1. For any square matrix A = (a ij ) indexed by the multiset M = {1 m 1 , 2 m 2 , . . . , n mn } of cardinality N = ∑ n i=1 m i , we have

where Lyn(A) is the set of all Lyndon covers of the multiset M .

The Generalized Lydon Cover and Cofactors

It this section, we find the multiset version of the notion of the generalized (i, j)-cycle cover of M . For a circular word

not regarded as following i s and none of the cyclic shifts of w regarded as the same word. We can define the multiset version of the partial cycle cover, as follows.

Definition 4.1. A word system γ = ⟨γ 1 , γ 2 , . . . , γ l ⟩ is a partial Lyndon cover of the multiset M of cardinality N if all γ i 's are circular Lyndon words and distinct and the non-circular word

We also say that γ is an k-Lyndon cover of the multiset M . The weight of an k-Lyndon cover γ = ⟨γ 1 , γ 2 , . . . , γ l ⟩ of M is defined as the product of the weights of its distinct circular Lyndon words and its sign is defined to be (-1) k-l . Definition 4.2. Let A = (a ij ) be a square matrix indexed by the multiset

is a non-circular primitive word, and i 1 = i and i s = j. The weight wt(η ij ) of an (i, j)-primitive word

Now, we can define the appropriate multiset analogue of the generalized (i, j)-cycle cover of D(A). Definition 4.3. Let A = (a ij ) be a square matrix indexed by the multiset

• The sequence ⟨γ 1 , . . . , γ r ⟩ is a partial Lyndon cover of the multiset M , • η ij is (i, j)-primitive word in M and for each l (l = 1, 2, . . . , r) the Lyndon representation of (η ij ) is different from the Lyndon representation of the circular word γ l ,

where Lyn ij (A) is the set of all Lyndon covers of M containing the word segment ij.

Proof. By Definition 4.5, for each i ∈ [n], we have

Now, by Theorem 3.1, we have

where Lyn(A) is the set of all Lyndon covers of M and Lyn ij (A) is the set of all Lyndon covers of M containing the word segment ij. Since a ij ̸ = 0, by subtracting formula (4.2) from (4.3) and considering the equalities in formula (4.1), we finally get

sgn(γ)wt M (γ), as required. □ Thus, we arrive at the following multiset analogue of the graph-theoretical interpretation of (i, j)-cofactor of a matrix. □


Wajdi Trabelsi

Christophe Sauvey

Nathalie Sauer

Paul Verlaine

Heuristics and metaheuristics for mixed blocking constraints flowshop scheduling problems

Keywords: flowshop scheduling problem, blocking constraints, heuristic, metaheuristics, makespan

Storage or buffer capacities between successive machines in flowshop problems may be unlimited, limited or null. The last two cases can lead to blocking situations. In flowshop scheduling literature, many studies have been performed about classical flowshop problems and also about some problems with only one blocking situation between all machines. This paper deals with makespan minimization in flowshop scheduling problems where mixed blocking constraints are considered. After a problem description and definitions of different blocking constraints, a mathematical model is presented and heuristics are developed to propose quick solutions to these kinds of problems. Then, metaheuristics are used to improve found solutions. A comparison between heuristics and metaheuristics is then performed.

INTRODUCTION

In order to obtain higher profits, modern production companies usually try to maximize their productivity. The latter goal, among others, can be achieved by optimal or almost optimal jobs scheduling in the production process while reducing storage capacity and even to remove it whenever possible. Storage capacity reduction between machines can lead to situations that are known in literature as blocking situations. Scheduling models differ depending on the technology used and constraints applied in the system. The most common scheduling problem is classical flowshop where buffer space capacity between machines is considered unlimited. Other problems are characterized by only classical blocking constraint RSb (Release when Starting Blocking: a machine remains blocked by a job until this job starts on the next machine in routing) and some others by specific blocking constraints RCb or RCb* (Release when Completing Blocking: a machine will be available to treat its next operation after its job is finished on the following machine in the process). In this paper, a general case is presented where successive machines can be subject to different types of blocking constraints, considering makespan as optimization criterion. This problem is likely to better approach industry-derived cases, which can already be seen as flowshop problems.

The first article dealing with a flowshop problem was published over fifty years ago [START_REF] Johnson | Optimal two-and three-stage production schedules with setup times included[END_REF]. Since then, many authors have focused on different aspects of this problem. We can cite a few articles: [START_REF] Bellman | Some combinatorial problems arising in the theory of multistage processes[END_REF] and [START_REF] Bellman | Mathematical Aspects of Scheduling and Applications[END_REF] for classical flowshop problem with two machines and [START_REF] Nawaz | A heuristic algorithm for the m-machine, n-job flowshop sequencing problem[END_REF] and [START_REF] Carlier | Two branch and bound algorithms for the permutation flow[END_REF] for general case with multiple machines. For greater sized problems, some heuristics and metaheuristics have been proposed, such as [START_REF] Iyer | Improved genetic algorithm for the permutation flow-shop scheduling problem[END_REF] and [START_REF] Siarry | Advances in Metaheuristics for Hard Optimization[END_REF].

For problems with classical blocking constraint (RSb), [START_REF] Sawik | A schedule algorithm for flexible flow lines with limited intermediate buffers[END_REF][START_REF] Sawik | Scheduling flexible flow lines with no in-process buffers[END_REF] proposed a heuristic for multi-stage flowshop problem both respectively with and without storage capacity. In [START_REF] Wang | An effective hybrid genetic algorithm for flowshop scheduling with limited buffers[END_REF], authors developed a hybrid genetic algorithm for flowshop scheduling with limited buffers. Other papers dealing with flowshop problems with RSb constraint, such as (Carraffa et al., 2001) and [START_REF] Ronconi | A Branch-and-Bound Algorithm to Minimize the Makespan in a Flow-shop with Blocking[END_REF], can also be cited.

Regarding RCb constraint, an Integer Linear Programming (I.L.P) model, lower bounds and a metaheuristic are presented in [START_REF] Martinez | Ordonnancement de systèmes de production avec contraintes de blocage[END_REF] for flowshop and hybrid flowshop cases. These problems have been solved in [START_REF] Yuan | Application of EM algorithm to flow-shop scheduling problems with a special blocking[END_REF] and [START_REF] Yuan | Application of EM algorithm to hybrid flow shop scheduling problems with a special blocking[END_REF]) by a metaheuristic "Electromagnetism-like Mechanism". A new blocking constraint called RCb* has been proposed in [START_REF] Trabelsi | Heuristic methods for problems with blocking constraints solving jobshop scheduling[END_REF] which is an RCb constraint variant. In this work, authors propose heuristics to solve jobshop problems with RCb and RCb* constraints.

Finally, for articles that have dealt with different types of constraints mixed in a production system, we can cite [START_REF] Martinez | Complexity of flowshop scheduling problems with a new blocking constraint[END_REF] who studied complexity issues with RSb and RCb constraints. We can also cite works by [START_REF] Grabowski | Sequencing of jobs in some production systems[END_REF] which consider a real-life problem of scheduling clients' orders of concrete blocks in a factory of building industry modeled as a hybrid flowshop scheduling problem with mixed no-wait/no-store constraints and mixed bottleneck/non-bottleneck machines. To our knowledge, no other author was interested in solving flowshop problems simultaneously subjected to different types of blocking constraints on successive machines in a process.

In this paper, we describe different flowshop cases with one or more blocking constraints. We present a mathematical model, propose a heuristic method to solve mixed flowshop problems, and compare it with NEH heuristic. We also use some improvement methods for both algorithms. Then, genetic algorithms are used to improve found solutions. In the last part, a comparison between heuristics and metaheuristics is performed.

PROBLEM DESCRIPTION

In flowshop scheduling problem, a set of n jobs, J = {J 1 , J 2 , …, J n }, must be executed on a set of m machines, M = {M 1 , M 2 , …, M m }. All jobs J i require the same operation order, O i = {O i1 , O i2 , …, O im }, that must be executed according to the same manufacturing process. Operation O ij needs an execution time P ij on machine M j  M. Each machine can only execute one job at any time. Preemptive operation is not authorized in presented work. Objective function consists in determining best scheduling in order to reduce makespan, i.e. time when all operations are completed.

In the following, we present different cases of flowshop problem: classical flowshop problem without blocking constraint (Fig. 1), a flowshop scheduling problem with only one blocking constraint present between all machines (Fig. 2, 3, and 4) and an example in which different blocking constraints are mixed (Fig. 5). To illustrate these different cases, we consider an example with five jobs and five machines.

The following execution time matrix P ij , has list of machines M j in columns and the list of jobs J i in lines.

 

5 .., , 1 , 1 2 1 2 2 1 1 1 2 2 1 2 2 1 1 1 2 2 3 1 2 1 2 1 1 ,                   j i P j i
In classical flowshop problem, buffer space capacity is considered to be unlimited. Therefore, there is no blocking situation and the system can be called Wb (Without blocking): a machine will be immediately available to execute the next operation after its operation in process is finished. In the example presented in Fig. 1, machine M 1 is available to treat job J 4 as soon as job J 3 on machine M 1 will be finished. For flowshop problem with a classical blocking constraint RSb (Release when Starting Blocking), a machine remains blocked by a job until this job starts on next machine in routing. This constraint is met in industrial problems where there is no intermediate storage between machines. In our example presented in Fig. 2, job J 3 remains blocked on machine M 1 as long as the following machine M 2 is not available.

Fig. 2. Flowshop problem with classical blocking RSb

In specific blocking RCb* (Release when Completing Blocking*), a machine will be immediately available to treat its next operation after its job on the following machine in process is finished without regard to whether or not it leaves the machine. In the example presented in Fig. 3, specific blocking RCb* differs from classical blocking RSb by the fact that machine M 1 remains blocked by job J 3 until its operation on machine M 2 is finished. This constraint was introduced for the first time by [START_REF] Trabelsi | Heuristic methods for problems with blocking constraints solving jobshop scheduling[END_REF]. We come across this kind of constraint in production lines when two successive machines are depending on same resource (tool or operator…), so they cannot process at same time.

In the case of particular blocking constraint RCb, a machine will be immediately available to treat its next operation after the operation of its job on the following machine in process is finished and it has left this machine. This constraint was introduced for the first time by [START_REF] Dauzère-Pérès | Modélisation et résolution par PLNE d'un problème réel d'ordonnancement avec contraintes de blocage[END_REF]. RCb constraint is useful in some industrial environments, such as waste treatment industry and aeronautics parts fabrication [START_REF] Martinez | Ordonnancement de systèmes de production avec contraintes de blocage[END_REF]. For cider brewing applications for example, one cannot melt apples of different customers. In a first step, apples are poured in a bath and then pressed to make apple juice. New customer apples cannot be poured in bath before all of the first customer's apples have been pressed.

The difference between RCb and RCb* blocking is underlined by job J 3 (Fig. 3 and4): in an RCb* blocking problem, machine M 1 remains blocked by job J 3 until its following operation on machine M 2 is finished, whereas in RCb problem, blocking time is bigger since machine M 1 will only be available when its following operation on M 2 is completed and job J 3 leaves machine M 2 . This date corresponds to further following operation on machine M 3 beginning.

In a large production line, we can encounter different types of blocking constraints which depend on intermediate storage between machines, characteristics of machines and technical constraints.

To describe a flowshop problem where different blocking constraints are mixed, we introduce a vector V that contains blocking constraints between machines. Element V j is blocking constraint between machines M j and M j+1 . This vector has m-1 elements (as many elements as the number of transitions between machines). In the previous example, if V = (RCb, RSb, RCb*, Wb), then RCb is the blocking constraint between machines M 1 and M 2 . Thereby, we construct Gantt diagram as follows (Fig. 5):

MATHEMATICAL MODEL

In this section, we present a mathematical model for a flowshop problem subject to different blocking constraints. This model is detailed in [START_REF] Trabelsi | Mathematical Model and Lower Bound for Flowshop Problem With Mixed Blocking Constraints[END_REF] in order to minimize makespan of a flowshop with mixed blocking constraint. Since jobs sequence is identical on all machines, we have to determine jobs permutation G that minimizes scheduling completion time or makespan. This model was solved by Xpress-MP optimization software and run on a PC with a 3.16 GHz Core 2 Duo' CPU.

Parameters

Parameters used in this model are as follows:

-n: Number of jobs.

-m: Number of machines.

-Pi, j: Job Ji execution time on machine Mj.

-Bh,j = 1 if there is an h blocking constraint between machine Mj and machine Mj+1 and 0 otherwise. With: h = 1: if there is Wb, i.e. no blocking constraint between machine Mj and machine Mj+1. h = 2: if there is an RSb constraint between machine Mj and machine Mj+1. h = 3: if there is an RCb* constraint between machine Mj and machine Mj+1. h = 4: if there is an RCb constraint between machine Mj and machine Mj+1.

Variables

Variables used in this model are as follows:

-Sk, j : Starting time of job at position k in sequence G on machine Mj.

-Ck, j : Completion time of job at position k in sequence G on machine Mj.

-Gi,k = 1 if job Ji is at position k in sequence G and 0 otherwise.

Model

Developed mathematical model is as follows:

max Min C (1)
With following constraints:

  n , .., i C C i, m 1 max    (2)     m , .., j , n , .., k , G P + S S n i i, k i, j- k, j- k, j 2 1 . 1 1 1        (3)     m- , .., j , n , .., k B . + S B . + C B . + S . B C S , j , j+ k- , j , j+ k- , j , j+ k- , j , j k- k, j 2 1 2 4 2 1 3 1 1 2 1 1 1 1      (4)   n , .., k , B + C B + S B C S , m- , m k- , m- , m k- , m- , m- k- k, m- 2 . . . 1 3 1 1 2 1 1 1 1 1 1    (5)   n , .., k C S , m k- k, m 2 1    (6)     m , .., j , n , .., k , G P + S C n i i, k i, j k, j k, j 1 1 . 1        (7)   n , .., k , G n i i, k 1 1 1      (8)   n , .., i , G n k i, k 1 1 1      (9)       n , .., k , n , .., i , , G i, k 1 1 1 0      (10)     m , .., j , n , .., k , S k, j 1 1 0      (11)     m , .., j , n , .., k , C k, j 1 1 0      (12)

Equations meaning

Each model constraint is described as follows:

-Equation ( 1): Objective function of our problem: minimize total completion time of scheduling.

-Equation ( 2): Makespan value must be greater than or equal to completion time of all jobs on the last machine.

-Equation (3): Represents precedence constraint between the same job on successive operations: to start its operation on a downstream machine, a job must first finish its operation on the upstream machine.

-Equation ( 4): This equation models different blocking constraints represented by parameter Bh,j. For example, if there is an RSb constraint between machine Mj and machine Mj+1, equation ( 4) becomes:

1 1, j+ k- k, j S S 
-Equation ( 5): This is a special case of the above equation which only deals with the penultimate machine. There is no blocking RCb at this stage because it depends on the two following machines.

-Equation ( 6): This is a special case of (4). It only deals with last machine, which can only be without blocking.

-Equation ( 7): This constraint calculates the completing time of jobs: i.e. last machine operations completion time.

-Equation ( 8

HEURISTICS

As presented in [START_REF] Trabelsi | Mathematical Model and Lower Bound for Flowshop Problem With Mixed Blocking Constraints[END_REF], it is not possible to obtain an exact solution for big-sized problems in a reasonable time. Therefore, it is necessary to develop approached methods and estimate their mean error with optimal solution (when it is computable) or lower bounds.

In this paper, we propose some heuristics with some local improvements in order to quickly obtain a feasible solution (in a polynomial time), but not necessarily an optimal one. In this section, we review the NEH method and present a new heuristic. We also use some improvement methods for both algorithms.

1. NEH heuristic presentation

NEH heuristic is one of the most famous heuristics known for flowshop scheduling [START_REF] Nawaz | A heuristic algorithm for the m-machine, n-job flowshop sequencing problem[END_REF]. This heuristic is not only efficient, but also very simple to compute. It is a constructive algorithm that selects the longest job not yet sequenced and tries to place it at all possible positions of the partial sequence under construction. Selected position minimizes partial makespan. A lot of references took this heuristic as a reference to compare their results [START_REF] Zobolas | Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm[END_REF], [START_REF] Ruiz | A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem[END_REF]. A pedagogical comparative study of some heuristics is performed in (Ruiz and Maroto, 2005). Adaptation of this heuristic to our problem is merely respect different blocking constraints between all machines when we calculate the corresponding makespan.

Algorithm 1 Let J = (J1, J2, ..,

2. TSS heuristic presentation

Proposed heuristic is based on a construction method. This proposal is inspired by an algorithm developed in [START_REF] Trabelsi | Heuristic methods for problems with blocking constraints solving jobshop scheduling[END_REF] for jobshop problem with RCb and RCb* blocking. From a partial solution, it is necessary to choose which job must be placed next. For that, we chose a criterion that combines three parameters:

-Cpmax: Partial Makespan: i.e. completion time of a new placed job.

-SomTpsIn: Sum of inactive times: i.e. the time during which machines are inactive, including idle times and blocking times.

-SomTpsEx: Sum of execution times of placed operations in partial schedule.

To have a best possible scheduling, we trend on one hand to minimize inactive times of machines and completion time, and on the other hand to maximize machine use, which is depicted in the following criterion:

Cr = min (Cpmax + SomTpsIn -SomTpsEx).
Then, n possibilities of schedule are constructed by switching jobs to place at first position and finally we choose the one that gives smallest final makespan Cmax.

General structure of the proposed algorithm to solve flowshop problems with mixed constraints is given below.

Algorithm 2

Introduce problem data (jobs number, machines number, operations execution time and blocking constraints between machines) For i = 1 to n (we calculate all possibilities by switching job to place at first position)

We Example: Let be a flowshop scheduling problem with four jobs and three machines.

Operations execution times are as follows:

    3 .., , 1 , 4 .., , 1 1 2 2 2 1 1 3 2 1 2 1 1 ,                    j i P j i
Blocking constraints vector: V = (RCb, RSb) , i.e. RCb is blocking constraint between machines M 1 and M 2 , and RSb is blocking constraint between machines M 2 and M 3 . Let be J 1 the job placed at first position. We have then three possibilities to place a following job: J 2 , J 3 or J 4 (Figure 6). We use choice criterion between these three cases to choose the job that gives the smallest criterion. We will explain how we calculated these different parameters through first case i.e. when job J 2 is placed (Figure 6-A [4][5] on machine M 2 ) and three time units as blocking time due to RCb constraint between machines M 1 on M 2 . -Cpmax = 8 ut. This partial makespan represents minimal date from which all machines will be available.

Then, Cr(A) = 8 + 5 -10 = 3 ut.

The results of each possibility (J 2 , J 3 or J 4 ) are given in Table 1. In this example, job J 3 is placed as second job in partial sequence because criterion Cr is minimal with job J 3 . Final solution given by above presented algorithm for this F3|Mixed|C max example is presented by the Gantt diagram (Figure 7). Fig. 8. Four machines problem with RCb blocking constraint TSS local improvement is based on the fact that, in an obtained sequence, a job with greater differential blocking time is permuted with all other jobs of sequence and the best solution is chosen. We continue as long as permutations improve makespan.

5. Experimental results

Presented works had been performed to see the effect of different improvements on obtained results by heuristics solving.

To determine whether our heuristic TSS would give good results, we compared it with the NEH algorithm in step (a), and then for both algorithms we added an NEH local improvement in step (b) and a TSS local improvement in step (c). At the end, the best solution is kept as the better makespan (d).

For each problem with fixed dimension, we generated 100 different instances (20 instances for problems bigger than 11 jobs / 10 machines) for which we know optimal solutions, obtained in works of [START_REF] Trabelsi | Mathematical Model and Lower Bound for Flowshop Problem With Mixed Blocking Constraints[END_REF]. For each of these instances, execution times were generated uniformly in interval [0,99]. All heuristics processes are programmed in the "C++" language and run on a PC with a 3.16 GHz Core 2 Duo' CPU. 4,46% 3,75% 3,39% 4,61% 3,94% 3,72% 2,86% 4,25% 2,55% 3,42% 1,76% 3,70% 1,20% 2,55% 0,86% 1,73% 5 b 0,48% 0,38% 0,21% 0,17% 0,29% 0,29% 0,40% 0,32% 0,44% 0,34% 0,39% 0,22% 0,36% 0,27% 0,20% 0,12% c 0,45% 0,23% 0,19% 0,15% 0,23% 0,19% 0,38% 0,13% 0,38% 0,25% 0,35% 0,15% 0,32% 0,17% 0,19% 0,08% d a 4,15% 4,02% 4,25% 3,97% 5,37% 4,58% 4,14% 3,98% 4,35% 3,82% 2,91% 4,09% 1,78% 2,56% 1,12% 1,84% 6 b 0,41% 0,74% 0,38% 0,33% 0,61% 0,43% 0,39% 0,54% 0,86% 0,81% 0,73% 0,50% 0,58% 0,24% 0,39% 0,21% c 0,35% 0,59% 0,37% 0,32% 0,53% 0,30% 0,36% 0,45% 0,76% 0,71% 0,67% 0,43% 0,55% 0,19% 0,35% 0,18% d a 5,21% 4,07% 4,87% 3,72% 5,68% 4,24% 4,92% 4,02% 4,58% 3,84% 3,95% 4,01% 2,46% 2,65% 1,72% 2,07% 7 b 0,50% 0,87% 0,46% 0,46% 0,78% 0,89% 0,82% 0,68% 0,93% 0,73% 0,84% 0,58% 0,88% 0,37% 0,53% 0,26% c 0,48% 0,69% 0,46% 0,44% 0,66% 0,75% 0,69% 0,57% 0,84% 0,59% 0,75% 0,49% 0,85% 0,34% 0,48% 0,23% d a 5,35% 3,87% 5,21% 3,26% 6,42% 3,77% 5,90% 3,95% 5,80% 4,10% 4,36% 3,95% 3,09% 2,82% 2,16% 2,18% 8 b 0,82% 0,95% 0,54% 0,52% 0,94% 0,79% 1,13% 1,03% 1,23% 1,00% 1,09% 0,76% 0,96% 0,52% 0,64% 0,42% c 0,75% 0,79% 0,50% 0,48% 0,84% 0,63% 1,02% 0,84% 1,14% 0,75% 1,01% 0,68% 0,93% 0,48% 0,61% 0,40% d a 5,33% 3,67% 6,10% 3,45% 6,35% 4,01% 6,27% 4,12% 5,74% 4,17% 5,19% 4,25% 3,33% 3,37% 2,43% 2,42% 9 b 0,57% 0,85% 0,80% 0,73% 1,25% 1,23% 1,53% 1,05% 1,49% 1,26% 1,18% 0,87% 1,26% 0,73% 0,92% 0,62% c 0,53% 0,76% 0,75% 0,59% 1,14% 1,02% 1,49% 0,85% 1,41% 1,14% 1,11% 0,80% 1,13% 0,72% 0,82% 0,61% d a 5,51% 3,72% 5,57% 3,17% 6,33% 4,02% 6,86% 4,54% 6,77% 4,56% 5,67% 4,86% 3,95% 3,20% 2,94% 2,57% 10 b 0,81% 0,94% 0,74% 0,81% 1,46% 1,27% 1,31% 1,25% 2,16% 1,63% 1,51% 1,32% 1,60% 0,92% 1,08% 0,63% c 0,72% 0,87% 0,68% 0,71% 1,31% 1,16% 1,22% 1,14% 2,10% 1,49% 1,43% 1,18% 1,51% 0,87% 1,01% 0,58% d a 5,52% 3,33% 6,21% 3,19% 7,20% 4,23% 7,03% 4,39% 7,16% 5,74% 6,03% 3,89% 4,32% 3,87% 3,43% 2,56% 11 b 0,75% 0,96% 1,04% 0,95% 1,57% 1,52% 1,49% 1,30% 1,67% 1,90% 1,97% 1,44% 1,44% 1,11% 1,07% 0,72% c 0,65% 0,87% 0,97% 0,82% 1,44% 1,43% 1,32% 1,18% 1,57% 1,83% 1,95% 1,44% 1,43% 1,05% 1,01% 0,67% d a 5,47% 3,31% 5,27% 3,21% 7,15% 4,07% 7,58% 5,12% 7,85% 5,57% 6,41% 4,84% 4,80% 3,64% 3,49% 2,50% 12 b 0,77% 0,81% 0,96% 0,88% 1,34% 1,46% 2,00% 1,70% 2,33% 2,02% 1,67% 1,49% 1,56% 1,11% 1,12% 0,86% c 0,75% 0,79% 0,94% 0,81% 1,24% 1,30% 1,85% 1,69% 2,22% 1,87% 1,46% 1,43% 1,56% 1,01% 1,06% 0,82% d 50 100 0,11% 0,17% 0,17% 0,22% 15 20 0,07% 0,10% 0,45% 0,28% 5 6 7 10 0,08% 0,08% 0,11% 0,08% 0,08% 0,06% 0,31% 0,32% 0,22% 0,17% 0,12% 0,11% 0,24% 0,25% 0,35% 0,31% 0,47% 0,28% 0,41% 0,57% 0,39% 0,38% 0,78% 0,65% 1,17% 0,89% 0,41% 0,39% 0,82% 0,74% 0,36% 0,28% 0,80% 0,59% 0,52% 0,46% 0,53% 0,44% 0,75% 0,47% 0,45% 0,53% 0,97% 0,80% 1,09% 1,13% 0,94% 0,52% 0,84% 0,58% 0,51% 0,52% 0,90% 1,15% 1,61% 0,98%

Table 2 : Error percentages between optimal solutions and makespan by using different heuristics Results presented in Table 2 prove that for small-sized problems (with 5 to 8 jobs), NEH and TSS have a very close error percentage (TSS is often better for problems with big number of machines), while for problems of larger sizes, NEH is often much better than TSS. (Table 2, lines a)

By adding an NEH local improvement on previous results, we note that error percentage becomes significantly smaller and comparable for both proposed heuristics. We also note that with TSS as a first heuristic, we only obtained best results for problems with 5 machines and some other problems (6/10, 7/7, 10/6...). (Table 2, lines b)

Since NEH local improvement gives good results, and as computing time is negligible, we can add other improvements. We added TSS local improvement, and that still improves results for both types of heuristics (Table2, lines c).

Finally, after adding different improvements to TSS and NEH heuristics, the best solution is kept for both cases (Table2, lines d) and we can note that error percentage is improving again, which means that the best solutions found with NEH or TSS heuristic taken first are often different.

We can notice the interest of varying both heuristics and local improvements:

-It gives us the possibility of tackling problems from different angles. Obtained solutions are rather different, which allows us to choose the best one. -As computing time of problems solved by heuristics and local improvement methods is negligible, we can mix them together to improve again solutions. We also notice that maximum error percentage by using our methods is obtained for about 15 machines.

META HEURISTICS 1. Genetic algorithms

In order to further improve solutions obtained by heuristic methods, we propose to use genetic algorithms which have proven their efficiency on discrete optimization problems since 1962. Holland's works on adaptive problems [START_REF] Holland | Outline for logical theory of adaptive systems[END_REF] and its fields of application have widely spread [START_REF] Holger | Stochastic Local Search: Foundations and Applications[END_REF], [START_REF] Siarry | Advances in Metaheuristics for Hard Optimization[END_REF].

Results obtained by genetic algorithm for flowshop scheduling problems with RCb blocking constraint proposed in works of [START_REF] Sauvey | A genetic algorithm with genes-association recognition for flowshop scheduling problems[END_REF] encouraged us to perform this method on mixed blocking flowshop problems. We used this metaheuristic to consider different blocking constraints simultaneously. This genetic algorithm runs with two main phases: selection and evaluation (Figure 8). An initial population is randomly generated and directly evaluated. Evaluation consists in our problem to calculate each individual's makespan in order to sort them. Then, a selection is operated on individuals in order to determine those likely to give the best results. Our selection includes crossing, mutation, and addition of new individuals at each new operation.

Fig. 8. Genetic algorithm presentation

In our genetic algorithm, we can impose best individuals keeping percentage (pc_best), new randomly generated people introduction percentage (pc_new), and crossing percentage (pc_cross). Individuals selected for crossing are taken among the preceding generation's best individuals and new randomly generated people. The remaining percentage of the created generation is created by mutation. Mutation is a random alteration of an individual's genes. In our algorithm, we select for mutation among best-kept individuals in order to see whether they further improve their good results.

As represented on Fig. 8, the loop composed of steps 2 and 3 is repeated as long as it is allowed by step 4. To perform our simulations, we chose to stop when the population no longer evolves quickly enough or stops evolving altogether. Population is then homogeneous and we can hope that it is near to optimum. The criteria we have retained to stop our simulations is the number of times when the best value was identical (ctbvi). It is very easy to put a loop counter to count the number of times loop 2-3-4 is performed. At each loop iteration, we hope that the evaluation of the new population will give a better individuate than best individuate evaluated up to time. Then, if the best individuate of the new current population improves the algorithm solution, it is memorized as the algorithm temporary solution and a loop counter is initialized to 0. If the algorithm temporary solution is not improved by the current loop population, this loop counter is incremented up to a maximum value defined by the parameter ctbvi. The returned algorithm solution is a temporary solution which has not evolved since ctbvi algorithm loops.

2. Experimental results

Percentages of crossing, mutation, and new individuals are adjustable. To perform work presented in this paper, we set for our experiments these percentages as follows: (pc_best : 0,1 ; pc_new : 0,1 ; pc_cross : 0.65). The criteria we have retained to stop our simulations is the number of times when the best value was identical (ctbvi = 500). The genetic algorithms processes are also programmed in the "C++" language and run on a PC with a 3.16 GHz Core 2 Duo' CPU.

In table 3, we can see at first (lines a) mean error between optimal solutions and makespan obtained by using genetic algorithm with 50 individuals. We add local improvements (lines b) to TSS and NEH. Then, in (lines c) we take best solution that gives the better makespan between the last genetic algorithm with local improvements (b) and another genetic algorithm with 100 individuals. Computing time of (c) is then presented.

Table 3 : Error percentages between optimal solutions and makespan obtained with different metaheuristics We note that genetic algorithms are very efficient: 0% error for problems up to 8 jobs with a computing time that is almost negligible, and remains inferior to 0.64% error for all other problems up to 12 jobs and 100 machines with a reasonable computing time.

If we detail further results, we find that there is not much improvement of results in (b) when adding NEH and TSS local improvements. On the contrary, in (c), we see a marked improvement on obtained solutions, allowing us to note that tackling a problem from different angles (i.e. use of two genetic algorithms or more) is better than adding local improvements to obtained schedules.

CONCLUSION AND PERSPECTIVES

In this paper, we focused on flowshop scheduling problem with mixed blocking constraints and its solving with heuristic and metaheuristic methods. Among the most effective heuristic methods, NEH has been taken to be locally improved and compared with our proposed heuristic TSS. We have tackled this problem with NEH and TSS heuristics successively, with two local improvements. First one is based on the iterative NEH method. Second is based on the permutation of the job that has the greatest differential blocking time in the sequence with all other jobs of this sequence. The best solution of the two heuristics with both improving methods is then chosen.

Our methods, when combined, improves significantly and very quickly our solutions: less than 1.61% error between optimal solutions and makespan in a time less than a second for a tested range of problems. Using metaheuristics, we further improved the results (highest error percentage is 0.34%), but it can be considerably more time consuming: up to 11.15s per problem on realized tests.

In our future works, we intend to further improve the efficiency of these methods, especially in computation time for the genetic algorithm. Then, we will try to adapt our methods on hybrid flowshop problems in order to obtain comparable results.

Fig. 1 .

 1 Fig. 1. Classical flowshop problem (Wb case)

Fig. 3 .

 3 Fig. 3. Flowshop problem with specific blocking RCb*

Fig. 4 .

 4 Fig. 4. Flowshop problem with specific blocking RCb

Fig. 5 .

 5 Fig. 5. Flowshop problem with mixed blocking constraints

  ): Each job Ji is placed at only one position k in sequence G. -Equation (9): At each position k of sequence G is only assigned one job Ji. -Equation (10): Gi, k is a Boolean variable. It is equal to 1 if job Ji is at position k in sequence G and 0 otherwise. -Equation (11): Starting time of jobs cannot be negative. -Equation (12): Completion time of jobs cannot be negative.

Figure 6 :

 6 Figure 6: Three possible scheduling cases

  ut. We placed two first jobs and we calculate its operations execution times.-SomTpsIn = 1+1+1+2 = 5 ut. It is the sum of inactive times with two time units as idle times (intervals [2-3] on machine M 1 and

  Jn) a list of jobs ordered by decreasing total processing time For i = 1 to n Select job Ji from J

	Cpmax = ∞
	For k = 1 to i
	Place job Ji at position k in partial sequence without changing relative position of other
	jobs already sequenced
	Calculate Cmax of associated partial scheduling
	If Cmax < Cpmax then
	Bestk = k
	Cpmax = Cmax
	End if
	End for
	Place job Ji at position Bestk in partial sequence
	End for

Table 1 :

 1 Choice criterion used to place next operation

		Execution time « SomTpsEx » (ut)	Idle time + Blocking time « SomTpsIn » (ut)	Partial makespan « Cpmax » (ut)	Cr
	A	10	2 + 3	8	3
	B	8	1 + 2	6	1
	C	9	4 + 3	7	5

Table 2

 2 presents the mean error between optimal solutions Opt and makespan C max . Error percentage is calculated as follows:

	%	err		C	max Opt  Opt		100

3. NEH local improvement

This local improvement is based on the iterative NEH method. In fact, we start with the scheduling order obtained by initial heuristic and then we use the iterative part of NEH algorithm, as long as we notice a solution improvement.

Algorithm 3

Let J = (J1, J2, .., Jn) a jobs order obtained by initial heuristic

TSS local improvement

In regard to classical flowshop problems, RCb blocking induces supplementary blocking time, which is defined as differential blocking time. In [START_REF] Sauvey | A genetic algorithm with genes-association recognition for flowshop scheduling problems[END_REF], the authors give two definitions of differential blocking time depending on whether it comes before occurrence of job J i on machine M j , or after. Differential blocking time "before" job J i on machine M j is due to insufficient execution time of job J i on machine M j-1 in front of the execution time of the preceding job in the routing on machine M j+1 . Differential blocking time "after" job J i on machine M j is due to insufficient execution time of the preceding job in the routing on machine M j+2 . (Figure 8)