Eric Andres
email: eric.andres@univ-poitiers.fr

Dimitri Ouattara
email: jean.ouattara@univ-poitiers.fr

Gaëlle Largeteau-Skapin

Rita Zrour
email: rita.zrour@univ-poitiers.fr

Gaelle Largeteau-Skapin
email: gaelle.largeteau.skapin@univ-poitiers.fr

Thoughts on 3D Digital Subplane Recognition and Minimum-Maximum of a Bilinear Congruence Sequence

Keywords: Digital planes, Digital Subplane Recognition Problem, congruence sequence Initial Sequence Characteristics (51, 131, 71) Interval [0, 13] 1 st

published or not. The documents may come

Introduction

Since J-P. Reveilles, among other previous authors [START_REF] Brons | Linguistic methods for the description of a straight line on a grid[END_REF][START_REF] Coven | Sequences with minimal block growth[END_REF], proposed an analytical description of a Digital Straight Line (DSL) 0 ≤ ax -by + c < ω [START_REF] Reveillès | Calcul en Nombres Entiers et Algorithmique[END_REF], many papers have been devoted to its study. Indeed, the structure of DSL is rich, with immediate links to word theory, the Stern-Brocot tree, the Farey sequence, etc. See [START_REF] Klette | Digital straightness -a review[END_REF] for an historical perspective. The natural extension to higher dimensions has opened new venues for arithmeticians [START_REF] Berthé | An arithmetic and combinatorial approach to threedimensional discrete lines[END_REF].

Lately, the problem of characterizing a Digital Straight Segment (DSS), segment of a DSL with known characteristics, has gained some traction [START_REF] Said | Multiscale discrete geometry[END_REF][START_REF] Lachaud | Two ecient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF][START_REF] Sivignon | Walking in the farey fan to compute the characteristics of a discrete straight line subsegment[END_REF][START_REF] Ouattara | Remainder approach for the computation of digital straight line subsegment characteristics[END_REF]. This problem is linked to multiscale shape analysis [START_REF] Lachaud | Two ecient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF][START_REF] Said | Multiscale discrete geometry[END_REF][START_REF] Vacavant | A combined multiscale/irregular algorithm for the vectorization of noisy digital contours[END_REF]. When considering geometrical features at multiple scales, it is important to be able to recompute the new, scaled, characteristics as rapidly as possible. In this paper we are interested in the extension of this problem to dimension three: the Digital Subplane (DSP) Recognition Problem. Check the following papers for a general approach on Digital Plane Recognition [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Gérard | An elementary digital plane recognition algorithm[END_REF][START_REF] Largeteau-Skapin | Outils arithmétiques pour la géométrie discrète[END_REF][START_REF] Brimkov | Digital planarity -A review[END_REF][START_REF] Dexet | A generalized preimage for the digital analytical hyperplane recognition[END_REF]. In Section 2, we propose a recall on 2D results and the unsolved problems in 3D. Right now, minimal characteristics of a subplane are chosen as representative of the equivalence class formed by all the characteristics that t the Digital SubPlane (DSP) [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Gérard | An elementary digital plane recognition algorithm[END_REF][START_REF] Brimkov | Digital planarity -A review[END_REF]. In particular, we conjecture the existence of a class of Digital SubPlanes characteristics for which the remainder order property is respected. This means that by searching for the minimum and maximum of the remainders on a DSP, we can identify leaning points easily which would lead to the characteristics (a leaning point is a point of extremum remainder in the DSP that allows to compute its characteristics). In Section 3, we propose an algorithm for computing the minimum and maximum of a simple bilinear congruence sequence corresponding to the remainders of a DSP. This represents a rst step towards solving a particular subclass of the general problem of characterization of a Digital Plane Subsegment Recognition Problem. We conclude in Section 4. There is a unique DSL with a given set of characteristics but there are an innite number of nite Digital Straight Lines that contain a same, nite connected, Digital Straight Segment (DSS). All these DSL containing a DSS form an equivalence class. There is therefore a question of the unique characterization of a DSS. If one simply takes the known characteristics of a DSL containing a DSS, then we may end up with dierent characteristics for the DSS and have the problem of comparing them. There is a unique DSL among the class that has a minimal parameter b [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF]. The parameters (a, b, c), with minimal parameter b among all the DSL containing a same DSS, are chosen as characteristics for the DSS. These characteristics are called minimal characteristics of the DSS. The DSS can then be fully characterized by those parameters and two points A and B corresponding to the end points of the segment. These parameters happen also to be those that are given by the analytical recognition algorithm proposed by I. Debled-Renesson [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF].

The problem of the characterization of a Digital Straight Subsegment contained in a known DSL is dierent from the regular recognition problem of a DSS since we already know that all the points of the subsegment belong to a known DSL. Various approaches have been proposed [START_REF] Said | Multiscale discrete geometry[END_REF][START_REF] Lachaud | Two ecient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF][START_REF] Sivignon | Walking in the farey fan to compute the characteristics of a discrete straight line subsegment[END_REF] such as considering the Stern-Brocot tree or the Farey fans. These methods are logarithmic in the coecients of the input slope or the length of the segment. The main problem with these methods is that they do not oer an obvious extension to higher dimensions. In [START_REF] Ouattara | Remainder approach for the computation of digital straight line subsegment characteristics[END_REF] is the ordinate of the point of abcissa x belonging to the DSL. The remainders dene a simple congruence sequence noted R (a,b,c) . One of the main results that we showed is that for a DSL of characteristics (a, b, c) and a DSS of minimal characteristics (α, β, γ) dened on x ∈ [u, v], the remainder order is conserved on the DSS [START_REF] Ouattara | Remainder approach for the computation of digital straight line subsegment characteristics[END_REF]:

∀x, x ∈ [u, v], |x -x | ≤ b : R a,b,c (x) < R a,b,c (x ) ⇒ R α,β,γ (x) ≤ R α,β,γ (x )
This has some direct consequences such as the fact that the minimal and maximal values of the DSL remainders on the subsegment are leaning points. By computing a third minimal or maximal remainder, it allows to determine the minimal characteristics of the subsegment. Furthermore, the computation of these minimal and maximal values of the congruence sequence can be done in logarithmic time with a simple characteristic substitution and sequence reduction scheme (DSL collapse) akin to Euclid's Algorithm. The method is faster than previous ones [START_REF] Said | Multiscale discrete geometry[END_REF][START_REF] Lachaud | Two ecient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF][START_REF] Sivignon | Walking in the farey fan to compute the characteristics of a discrete straight line subsegment[END_REF] and oers a possible extension to higher dimensions. It is this extension we start exploring in the present paper.

State of the 3D problem

This paper is interested in the exploration of the Digital SubPlane (DSP) Recognition (characterization) Problem in dimension three. The paper is meant as a rst step as there are some signicant dierences with the problem in dimension two and, as we will see, many questions that remain open and that require future investigations. First of all, Digital Plane (DP) recognition problems in 3D can be way more dicult than in 2D. For instance, decomposing a 2D closed curve into a minimal number of 2D DSS can be performed in linear time [START_REF] Feschet | On the min DSS problem of closed discrete curves[END_REF] while the equivalent problem in 3D is NP-hard [START_REF] Sivignon | Minimal decomposition of a digital surface into digital plane segments is np-hard[END_REF]. The preimage of a 2D DSS is a polygon of a maximum of four vertices while there is no limit to the number of vertices for the preimage polytope of a DSP in 3D [START_REF] Brimkov | Digital planarity -A review[END_REF]. There are also some similarities: as in 2D, a nite connected digital subplane belongs to an innite number of digital planes containing the DSP (and thus dening an equivalence class). There exists a unique DP of characteristics (a, b, c, d) such that c is minimal among the characteristics in the equivalence class. This is called the minimal characteristics of a DSP. The DSP Recognition algorithms provide the minimal characterictics [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF][START_REF] Gérard | An elementary digital plane recognition algorithm[END_REF][START_REF] Largeteau-Skapin | Outils arithmétiques pour la géométrie discrète[END_REF][START_REF] Brimkov | Digital planarity -A review[END_REF][START_REF] Dexet | A generalized preimage for the digital analytical hyperplane recognition[END_REF]. For the problem that interests us, the problem of characterizing a plane subsegment of a known Digital Plane in dimension three, the Stern-Brocot exploration approach followed by Said and lachaud [START_REF] Said | Multiscale discrete geometry[END_REF][START_REF] Lachaud | Two ecient algorithms for computing the characteristics of a subsegment of a digital straight line[END_REF] and the Farey fan walk approach followed by Sivignon [START_REF] Sivignon | Walking in the farey fan to compute the characteristics of a discrete straight line subsegment[END_REF] are not easily extended to dimension three, while our remainder approach seems more appropriate [START_REF] Ouattara | Remainder approach for the computation of digital straight line subsegment characteristics[END_REF]. The extension of the 2D remainder sequence to 3D is straightforward and constitutes the starting point of this investigation. Let us consider a digital plane One could think that the 2D remainder properties extend naturally to 3D, but they do not, at least not always. The 2D remainder order conservation property (recalled in the previous subsection) is not veried anymore in 3D (see the conclusion of [START_REF] Ouattara | Remainder approach for the computation of digital straight line subsegment characteristics[END_REF] for an example). It is veried quite often but not systematically. The consequences are immediate: there are leaning points of the DP that may not be leaning point anymore in the DSP and vice-versa. It means also that the minimum and maximum remainder value on a DSP remainder sequence are not necessarily leaning points for the minimal characteristics of the DSP. However, it seems that there always exists characteristics for the DSP such that the minimum and maximum remainder are leaning points. Let us express this in the form of a conjecture: Conjecture 1. Let us consider a DP P = D(a, b, c, d), with gcd(a, b, c) = 1 and

0 ≤ a ≤ b ≤ c and a nite DSP of P dened on (x, y) ∈ [x 0 , x 1 ] × [y 0 , y 1 ],
then there exists characteristics (α, β, γ, δ) such that the points among those with the minimum and maximum values of the bilinear remainder sequence

R (a,b,c,d) (x, y) on [x 0 , x 1 ] × [y 0 , y 1 ] are leaning points of the DSP for the charac- teristics (α, β, γ, δ).
Actually, what that means is that the minimal characteristics for a DSP may not be the only choice as DP equivalence class characteristics' representative. While the remainder conservation property is not always veried for minimal characteristics, it seems that there are actually always characteristics (sometimes not minimal) that have this property. This needs to be looked upon more closely before we state it as a conjecture or simply prove it, but it opens the way to a subclass of DSP characteristics with some very interesting properties. On the opposite, the remainder conservation property seems to be the norm. For instance, when we consider a DSP with minimal characteristics, most DP that contain this DSP seems to verify the conservation property but not necessarily all. Are there always DP that do not verify this property and always some that do? How are those groups characterized? They represent after all the very same voxels so what makes them behave dierently? So, why considering characteristics that are not necessarily minimal? First of all, this may lead to characterization algorithms that are sublinear in the DSP number of voxels (for the Digital Subplane Recognition Problem). The insight in the characteristics classes may lead to new and better general understanding of Digital Planes. In this paper, we provide the rst algorithm with sublinear complexity to determine the minimum and maximum of a simple bilinear congruence sequence (DSP remainder sequence) and provide some thoughts on particular classes of Digital Plane collapses.

After some notations, we will present in Section 3 some extensions of the results presented in [START_REF] Ouattara | Remainder approach for the computation of digital straight line subsegment characteristics[END_REF] on linear congruence sequences. We show that one can determine in logarithmic time if a bilinear congruence sequence contains a given value . We provide an algorithm to compute the minimum and maximum of a bilinear congruence sequence. We conclude in Section 4 and give some clues on the computation of DSP characteristics and future work. Finding the minimum and maximum of a simple bilinear congruence sequence

We are looking for the minimum and maximum of a bilinear congruence sequence

ax+by+d c for (x, y) ∈ [x 0 , x 1 ] × [y 0 , y 1 ].
We suppose that gcd(a, b, c) = 1 and that 0 ≤ a ≤ b ≤ c. After the presentation of some notations, we will discuss properties of linear congruence sequences and especially linear congruence sequence collapses that preserve minimum or maximum values. This leads to a rst algorithm for the search of a minimum and maximum in a bilinear congruence sequence. We will end this section with some thoughts on digital plane collapses in order to obtain even better complexities.

Notations

A Digital Plane (DP for short)

P (a, b, c, d) of integer characteris- tics (a, b, c, d) is the set of digital points (x, y, z) ∈ Z 3 such that 0 ≤ ax + by -cz + d < max (|a| , |b| , |c|) with gcd (a, b, c) = 1.
This digital plane is 18-connected and called a naive digital plane [START_REF] Brimkov | Digital planarity -A review[END_REF]. The value d is sometimes called the translation constant. In this paper, without loss of generality, we assume that 0 ≤ a ≤ b ≤ c. In this case, we have one and only one point, denoted P D (x, y), in P with abscissa x and ordinate y. The z-coordinate is then z = ax+by+d c . A Digital SubPlane (DSP for short) S (P, x 0 , x 1 , y 0 , y 1 ) associated to the DP P = P (a, b, c, d) is the subset of P with points of abscissa and ordinate in [x 0 , x 1 ] × [y 0 , y 1 ]. A DSP is a nite 18-connected subset of a DP.

We will use the notation n m for n mod m [START_REF] Reveillès | Calcul en Nombres Entiers et Algorithmique[END_REF]. In 3D, the remainder at abscissa and ordinate (x, y) is the value R a,b,c,d (x, y) = ax + by -cz + d. For a point of the DP, we have

R a,b,c,d (x, y) = ax+by+d c . The bilinear remainder sequence R a,b,c,d (x 0 , x 1 , y 0 , y 1 ) is a set of remainders R a,b,c,d (x, y) for (x, y) ∈ [x 0 , x 1 ] × [y 0 , y 1 ]. In 2D, the remainder for a DSL of characteristics (a, b, c) is the value R a,b,c (x) = ax+c b at abscissa x. The linear remainder sequence R a,b,c (u, v) corresponds to the values R a,b,c (x) for u ≤ x ≤ v. Let us rst note that R a,b,c,d (x, y) = R a,c,d+by (x) = R b,c,d+ax (y).
The simpliest way of looking at a bilinear congruence sequences is to look at them as sequences of linear congruence sequences. The results presented here are slight extensions of properties already presented in [START_REF] Ouattara | Remainder approach for the computation of digital straight line subsegment characteristics[END_REF] for sequences of type R a,b,0 (x) with parameter c = 0. Here we are looking at the same properties for R a,b,c (x). As we will see, the extensions are pretty straightforward.

Linear Sequence collapse

Let us look at collapsed linear congruence sequences to R a,b,c (u, v) = Let us call a span, a set of pixels with same ordinate. The remainders between 0 and a -1 are located at the beginning of a complete span while the remainders between b -a and b -1 are located at the end of a complete span. Let us note as well that, in Figure 1, the rst span on the bottom left is not complete and the upper top span neither. Proof. In [START_REF] Ouattara | Remainder approach for the computation of digital straight line subsegment characteristics[END_REF] a similar result has been presented but with c = 0. We have therefore simply to prove that the result stands with c = 0. For the rst line, . The same goes for the maximum.

cient (α, β) of (a, b) such that aα -bβ = 1. It is easy to see that R a,b,c (u, v) = R a,b,0 u -cα b , v -cα b [13]. We know already that if m ∈ R a,b,0 u -cα b , v -cα b then m ∈ R { -b a },a,0 1 + a(u-{ cα b }-1) b , a(v-{ cα b }) b [ 13
Proposition 1 means that we can build two linear congruence sequences that maintain the minimum and maximum values respectively. Although the maximum value is only conserved indirectly via an accumulator value. The interesting aspect is that we replace a sequence of (v -u) values by a sequence with The proof is similar to the one that can be found in [START_REF] Ouattara | Remainder approach for the computation of digital straight line subsegment characteristics[END_REF]. With Lemma 1, we transform a sequence with a spans into a sequence with b -a spans and a DSS of slope a b > 1 2 into a DSS of slope b-a b < 1 2 . The spans are bigger and the computation time is reduced.

Lemma 2. R a,b,c (u, v) = R a,b,{ c b } (u, v)
This result is obvious since the remainder sequence has a periodicity of b. This lemma can help if c is big compared to b.

Right now we have supposed that for a DSL characteristics (a, b, c), we have gcd(a, b) = 1. This is reasonable since the DSL of characteristics (a, b, c), for g = gcd(a, b) > 1, is the same than the DSL of characteristics a g , b g , c g . However, if we are simply looking at the remainder sequence for gcd(a, b) > 1, the values in the sequence are dierent although related to the remainder values obtained by dividing the characteristics by the gcd, as the following lemma shows (note that the algorithm 1 works even if the GCD is not equal to one): We now have all we need for a complete 2D algorithm: see Algorithm 1 for the search of the minimum in a 2D sequence. This algorithm is an extension of the one proposed in [START_REF] Ouattara | Remainder approach for the computation of digital straight line subsegment characteristics[END_REF] as it computes the minimum and the maximum at the same time. Note however that we do not check if the value 0 or b -1 belong to the sequence for algorithm ComputeMinMax2D parameters (a, b, c, u, v). In 3D, there is an overall check for the presence of those values in the complete bilinear sequence. If the reader wants to use the algorithm ComputeMinMax2D to solve 2D cases, he may add these checks although it is not necessary. It requires to compute the Bezout coecients and thus it adds the complexity of this computation to the general case and substitutes it to the complexity of the algorithm (equivalent to the complexity of the Euclidean algorithm).

Example: Figure 1 ensures that the span considered is the rst complete span. The rst value in the minimum sequence will be 42 and not 71. The maximum sequence is dened on the interval

1 + a•0+20

151

, 31(13+1)+20 151 = [START_REF] Andres | Discrete analytical hyperplanes[END_REF][START_REF] Coven | Sequences with minimal block growth[END_REF] with accumulation value 131 -51 = 80. Note that the interval for the minimum sequence and the maximum sequence are not necessarily identical as can be seen in the last step. The second step is similar to the rst but applied on the minimum and maximum sequence: the DSS 0 ≤ 22x -51y + 20 < 51 is collapsed into the DSS 0 ≤ 15x -22y + 20 < 22 with both intervals 2 ≤ x ≤ 3, and accumulation value 80 + 51 -22 = 109. The third step corresponds to an inversion on the sequence: since 15 • 2 > 22, the DSS is transformed into 7x -22y + 20 < 7, with intervals -3 ≤ x ≤ -2. The accumulation value does not change. As can be seen in the gure, the values are now, for both minimum and maximum sequence, on a same span, and the minimum is given by the rst value in the span piece while the maximum value is given by the last value in the span piece.

Ecient search for a given value in a bilinear congruence sequence

We have now almost all we need for a rst 3D algorithm. There is however a last problem that we are going to address. Let us consider a bilinear congruence sequence ζ = R a,b,c,d (x 0 , x 1 , y 0 , y 1 ). We know that the minimum value in ζ cannot be smaller than 0 and the maximum not greater than c -1. So, by providing an ecient method that determines if a given value belongs to the sequence (in our case = 0 or = c -1), we will not have to search further for a minimum or a maximum. Of course, one can check row by row or column by column but one can actually do better than that using the following theorems (see Figure 2 for an example): Theorem 1. Let us consider the bilinear congruence sequence ζ = R a,b,c,d (x 0 , x 1 , y 0 , y 1 ) and a value , with 0 ≤ < c. Let us suppose that gcd(a, c) = 1 and (α, β) their Bezout coecients verifying aα -cβ = 1. Let us dene the sequence x (y), y ∈ [y 0 , y 1 ] of the smallest abscissa greater or equal to x 0 with remainder R a,b,c,d (x, y) = . Then:

x is given by the sequence x 0 + R -bα,c,α( -d-ax0) (y 0 , y 1 ) .

Proof. Let us consider a DSP dened by

0 ≤ ax + by -cz + d < c with (x, y) ∈ [x 0 , x 1 ] × [y 0 , y 1 ].
Let us suppose that gcd(a, c) = 1 and (α, β) their Bezout coecients verifying aα -cβ = 1. First, let us note that 0 ≤ ax + by -cz

+ d < c with (x, y) ∈ [x 0 , x 1 ] × [y 0 , y 1 ] is equivalent to 0 ≤ ax + by -cz + d + ax 0 < c with (x , y) ∈ [0, x 1 -x 0 ] × [y 0 , y 1 ] and x = x -x 0 .
For a given ordinate, we are searching for the abscissa x greater or equal to 0 with a remainder equal to . For a given ordinate y, the abscissa

x (y) with remainder R a,b,c,d (x , y) = ax + by -cz + d + ax 0 = veries ax -cz = -d -by -ax 0 . With the Bezout coecients (α, β), we have (α( -d-by-ax 0 )+kc)a-(β( -d-by-ax 0 )+ka)c = -d -by -ax 0 , k ∈ Z. This means that x ∈ {( -d -by -ax 0 )α + kc : k ∈ Z}.
The smallest abscissa x = x + x 0 , greater or equal to x 0 with remainder equal to is then given by x 0 + -bαy+α( -d-ax0) c . In Theorem 1, we have supposed that gcd(a, c) = 1 which is not necessarily the case. Let us now examine what happens when gcd(a, c) = g > 1.

Theorem 2. Let us consider the bilinear congruence sequence ζ = R a,b,c,d (x 0 , x 1 , y 0 , y 1 ) and a value , with 0 ≤ < c. Let us suppose that gcd(a, c) = g > 1. Let us suppose that (α, β) are the Bezout coecients for (b, g) such that bα -gβ = 1. Then, the bilinear congruence sequence ζ contains the value i the sequence R a g ,{ b g }, c g , d+b•y i -e g

x 0 , x 1 , 0, y1-yi g with

y i = y 0 + α(e-d-by0) g
, contains the value 0.

Proof. Let us consider the bilinear congruence sequence ζ = R a,b,c,d (x 0 , x 1 , y 0 , y 1 ) and a value , with 0 ≤ < c. Let us suppose that gcd(a, c) = g > 1.

Let us suppose that (α, β) are the Bezout coecients for (b, g) such that bα -gβ = 1. Of course, here, gcd(b, g) = 1 or otherwise we would not have gcd(a, b, c) = 1. It is easy to see that R a,b,c,d (x 0 , x 1 , y 0 , y 1 ) for y ∈ [0, y1 -y0] is the same as R a,b,c,d+by0 (x 0 , x 1 , 0, y 1 -y 0 ). We know that ax+by -cz +d+by 0 = , with y = y -y 0 , is only possible if by +d+by0- g = 0.

The smallest value y ≥ 0 verifying this is given by y = α( -d-by0) g . Let us

denote y i = y 0 + α( -d-by0) g
. The ordinate y i is the rst ordinate between y 0 and y 1 for which the sequence ζ may contain . The other ordinates where we may nd are then all the y i + kg for k ∈ 0, y1-yi g . Now we need to replace y by gy in order to have steps of 1 on the ordinates. We also need to start with the ordinate 0 as y i is not necessarily divisible by g. It is easy to see that ζ = R a,b,c,d+byi (x 0 , x 1 , 0, y 1 -y i ). Since the value can only be found on the lines with ordinate y i + kg, it is easy to see that can be found in ζ i it can be found in R a,bg,c,d+byi x 0 , x 1 , 0, y1-yi g . If we denote (a , c ) = (a/g, c/g) then we have a gx + bgy -c gz + d + by i = if a gx + bgy -c gz + d + by i -= 0 or a x + by -c z + d+byi- g = 0 (note that d + by i -is divisible by g). Here, if b is bigger than c, then it is easy to see that it can be replaced by b c . Theorem 3. Deciding if a value belongs to a bilinear congruence sequence can be decided in logarithmic time.

The proof is obvious. With Theorem 1 and Theorem 2, we exhibit linear congruence sequences. We can search for its minimum with Algorithm 1. If the minimum is smaller or equal to x 1 -x 0 then the sequence ζ contains the value . This search for the values 0 or c -1 can thus be done in logarithmic time. The proposition is a direct consequence of the complexity of the 2D algorithm [START_REF] Ouattara | Remainder approach for the computation of digital straight line subsegment characteristics[END_REF]. Figure 3 shows an example. As one can see, the collapse line by line does not produce a rectangle on (x, y). Also, one can see that the nal minimum or maximum values do not necessarily form a connected nal set. The problem comes from the sequences of the values (u, v) over the dierent lines. In this paper we were interested in the Digital SubPlane (DSP) Recognition Problem. We tried to extend our remainder approach for the recognition of straight line segments to the recognition of subplanes. The extension is not immediate. In particular, the remainder order property that is veried in 2D is not always veried in 3D. As a consequence, a point may be a Leaning Point for the Digital Plane but not for the Digital SubPlane and vice-versa.

There seems however to be classes of subplanes for which the remainder order property are conserved. The characterization of this subclass is an open question. It could represent an interesting candidate as representative of the equivalent class of Digital Planes containing a SubPlane. From this starting point, we proposed an extension of the search of a minimum and maximum of a linear congruence sequence to the third dimension. We showed in particular that one can determine if a given value belongs to a bilinear congruence sequence in logarithmic time. The minimum and maximum value in a bilinear congruence sequence ax+by+d

c , (x, y) ∈ [x 0 , x 1 ] × [y 0 , y 1 ] can be found, if m = x 1 -x 0 < n = y 1 -y 0 , in O(m log (min(a, c -a)) or O(n log (min(b, c -b)) otherwise.
This paper is only a very rst step in the investigation of the SubPlane Recognition Problem. As already discussed, we would like to prove that there are always subplanes that verify the remainder order property, namely, for a Digital Plane of characteristics (a, b, c, d) and a SubPlane of characteristics (α, β, γ, δ) dened on [x 0 , x 1 ] × [y 0 , y 1 ] ∀(x, y) and (x , y ) ∈ [x 0 , x 1 ] × [y 0 , y 1 ], : R a,b,c,d (x, y) < R a,b,c (x , y ) ⇒ R α,β,γ,δ (x, y) ≤ R α,β,γ,δ (x , y ). The question comes actually down to a construction problem. Starting from the Digital Plane, it is possible to erode it in such a way that we obtain a sequence of SubPlanes that verify the remainder order property and vice-versa?

The algorithm for the search of a minimum and a maximum in a bilinear congruence sequence searches for the minimum and maximum line by line (or column by column). This is possible because a line of a bilinear congruence sequence is simply a linear congruence sequence. One could try to improve this by alternatively searching for a minimum in a line or a column. This corresponds to a form of 3D digital plane collapse (see [START_REF] Palágyi | Generation and recognition of digital planes using multi-dimensional continued fractions[END_REF] for other forms of plane collapses). See Figure 4 when this is performed on an innite Digital Plane and Figure 5 where it is performed on a Digital SubPlane. Again, one can see that the collapse on a DSP does not preserve a simple shape. One would be able to achieve a logarithmic search for the minimum and maximum if one is able to characterize the shape of the collapsed DSP (See Figure 5).

There are however possibilities of improvement in terms of complexity. Firstly, one can see that the shape after one collapse (see Figure 3 and Figure 5) is not dened on a rectangle anymore but the sides that are not parallel to an axis form actually a Digital Straight Line (when projected on 2D). Another possible improvement could be done by repetitively searching for specic values in the bilinear congruence sequence: looking for values 0, 1, .. when a value is found in the sequence it corresponds then to the minimum. The complexity is then c times a log. This works best when the size of the DSP is important compared to the characteristics values. A ner study needs to be conducted to check when doing one is more ecient than the other, or mixing both.

2

  Recalls on the 2D problem and state of the 3D problem 2.1 Recalls of the 2D Digital Straight Subsegment Recognition Problem An 8-connected Digital Straight Line (DSL) in the rst octant, is dened by analytical inequalities 0 ≤ ax -by + c < c, with 0 ≤ a ≤ b and ω = b, gcd(a, b) = 1, a, b, c ∈ Z 3 .

  , the authors have proposed an alternative algorithm based on the remainder values. For a DSL D(a, b, c) of characteristics (a, b, c), if a point (x, y) belongs to the DSL, then the remainder ax -by + c is equal to ax+c b (where n m stands for n mod m). The integer R (a,b,c) = ax+c b is called a remainder in x as remainder of a Euclidean division where ax+c b

(

  DP) P(a, b, c, d) = (x, y, z) ∈ Z 3 ; 0 ≤ ax + by -cz + d < c of known characteristics (a, b, c, d), with, w.l.o.g. gcd(a, b, c) = 1 and 0 ≤ a ≤ b ≤ c. For all the points of the DP, one can dene a simple bilinear congruence sequence R a,b,c,d (x, y) = ax + by -cz + d = ax+by+d c [14, 1].

3

 3

  ax+c b : u ≤ x ≤ v that preserve the minimum and maximum values of the sequence. We suppose that 0 ≤ b and gcd(a, b) = 1. Let us remark that the sequence of remainders R a,b,c (x) corresponds to a naive DSL of slope a b in the rst octant. When one looks at such a sequence as a DSL, one can see that the minimal values and maximal values are located at specic places on the DSL.

Fig. 1 .

 1 Fig. 1. DSS of characteristics (51, 131, 71), 0 ≤ x ≤ 13. Minimum remainders are at the beginning of a span while maximum remainders are at the end of a span. Three steps are needed in this case to determine the minimum and maximum.

  ordinate of the points of abscissa u and v. If the ordinates are equal, both points are on the same span and the minimum is located at abscissa u and the maximum at abscissa v regardless if the span is complete or not.Let m = min(ζ). Now, let us consider the Bezout coe-

  ]. It is now easy to see that this is the same as m ∈ R { -b a },a,c 1 + a(u-1)+c b , av+c b

- 1

 1 values. However if the slope is close to 1, the number of points is equal to the number of spans and we do not gain much by replacing one sequence by the other. This is solved by performing the following substitution: Lemma 1. Let us consider the remainder subsequence ζ = R a,b,c (u, v), with 0 ≤ a ≤ b and gcd (a, b) = 1. Let us suppose that 2a > b then: min(ζ) ∈ ζ and max(ζ) ∈ ζ where ζ = R b-a,b,c (-v, -u)

Lemma 3 .

 3 Let us consider a DSL of characteristics (a, b, c) such that gcd(a, b) = g > 1, then: R a,b,c (u, v) = c g + gR a g , b g ,c (u, v) Algorithm 1: ComputeMinMax2D (In: a, b, c, u, v. Out: mini, maxi) -a, b, c: characteristics of the DSL; u, v: interval of denition of the DSS; mini, maxi: minimal, maximal remainder) begin minif ound ← F alse; maxif ound ← F alse; cumul ← 0 ; (* (u , v ) min sequence interval and (u , v ) max sequence interval *) u ← u ; v ← v ; u ← u ; v ← v ; while not (minifound and maxifound) do if 2a > b then (* Dealing with longer spans reduce computation time *) (a, b, c, u , v , u , v ) ← (b -a, b, c, -v , -u , -v , -u ) ; (a , b ) ← -b a , a ; c = c b ; if not(minifound) then yu ← au +c b ; yv ← av +c b ; if yu = yv (* only one span *) then mini ← au +c b ; minif ound ← T rue ; (* We have our minimal remainder *) else (u , v ) ← (1 + (a (u -1) + c )/b , (a v + c )/b ); if not(maxifound) then yu ← au +c b ; yv ← av +c b ; if yu = yv (* only one span *) then maxi ← cumul + au +c b ; maxif ound ← T rue ; (* We have our maximal remainder *) else (u , v ) ← (1 + (a u + c )/b , (a (v + 1) + c )/b ); (a, b, c) ← (a , b , c );

  shows an example of simple linear congruence collapse. The DSS is dened by 0 ≤ 31x -151y + 71 < 151 with 0 ≤ x ≤ 13. The rst step transforms the DSS characteristics in -151 31 , 31, 71 = (22, 51, 20). The translation constant is 71 51 = 20 (Lemma 2). We have now two sequences: the one that contains the minimum values and the one with the maximum values. The minimum sequence is dened on the interval 1 + 31(0-1)+20 151 , 31•13+20 151 = [1, 5]. The formula 1 + a(u-1)+c b

Fig. 2 .

 2 Fig. 2. Bilinear Congruence Sequence 4x+12y+4 17 on [3, 15] × [0, 5]. The blue rectangle shows the DSP subsequence. In Pink, the values = 0 with abscissa greater than x0 = 3. In Dark Blue, the values 0 with abscissa smaller than x0 = 3.

3. 4

 4 First algorithm for the minimum and maximum search in a bilinear congruence sequence Let us consider a bilinear congruence sequence ζ = R a,b,c,d (x 0 , x 1 , y 0 , y 1 ). The previous section let us check if the values 0 or c -1 belong to ζ. If both values are in ζ then the search is over. Otherwise, let us consider the smallest of the intervals n = x 1 -x 0 and m = y 1 -y 0 . W.l.o.g., let us consider that we have m < n. The rst 3D algorithm consists simply in applying algorithm ComputeMinMax2D(a,c,d + ay), for y ∈ [y 0 , y 1 ]. We keep the minimum and maximum over all these 2D sequences. Proposition 2. Let us consider a bilinear congruence sequence ζ = R a,b,c,d (x 0 , x 1 , y 0 , y 1 ) with n = x 1 -x 0 < m = y 1 -y 0 . The complexity of the search for the minimum and maximum value in ζ is bounded by O (n • log (min(a, c -a))).

Fig. 3 .

 3 Fig. 3. Bilinear Congruence Sequence 161x+191y+7 331

Fig. 4 .Fig. 5 .

 45 Fig. 4. Plane collapses


H El Haouzi

A Thomas

J F Pétin

Contribution to reusability and modularity of Manufacturing Systems Simulation Models: application to distributed control simulation within DFT context

Keywords: Discrete-event simulation, model reusability, model modularity, distributed control, ASDI

Requirements for manufacturing control evolve from traditional centralized approaches where decision making is hierarchically broadcasted to more complex distributed control architectures involving autonomous entities and processes. Moreover, manufacturing processes are facing to standardisation and globalisation such as promoted by the Demand Flow Technology (DFT) concepts. In order to evaluate these new architectures, discrete-event simulation seems the most appropriate tool. However, complexity of distributed architectures and DFT standardisation requires introducing modularity and reusability in the modelling process. This paper deals with a methodological approach, based on ASDI (analysis-specification-design-implementation), to develop a library of generic simulation components that can be, as automatically as possible, instantiated into a modular simulation model. This approach is illustrated using an industrial case study where simulation aims at evaluating the impact of operator's flexibility induced by DFT context.

Today manufacturing systems need to be adapted to the internal (e.g. machine breakdown) as well as the external disturbances (e.g. changes in demands or product specifications). Consequently research in manufacturing system control has moved away from traditional centralized approaches where decision making was hierarchically broadcasted from the higher decisional levels down to the operational units to more distributed architectures. In this way, heterarchical architectures promote production control by distributing every decision capacities in autonomous entities, without any centralised view of the shop floor status. To ensure the consistency of a decision making, more pragmatic approaches are based on hybrid control which combines the predictability of the centralized control with the agility and robustness against disturbances of the heterarchical control. Holonic Manufacturing Systems (HMS) has been suggested as a concept for these futur manufacturing systems [START_REF] Koestler | The Ghost in the Machine[END_REF].

In order to evaluate these new manufacturing systems or to choose a management production organization rather than another, [START_REF] Law | Simulation Modeling & Analysis[END_REF] showed that discrete-event simulation is the more adaptable method (in the following, the term simulation will always be related to discrete-event simulation). While simulation has much strength, it is difficult to identify in a given model the different flows that are processed by the system. Consequently, decisional and physical systems can't be separated in the model which is a serious limitation for evaluation of several control policies without a complete simulation model redesign. It emphases the need for an underlying modelling discipline or structured approach [START_REF] Douglas | A Structured Approach to Simulation Modeling of Manufacturing Systems[END_REF] to guarantee modularity and thus facilitate modification on the model. Moreover, nowadays the majority of companies are evolving towards a standardisation of their various physical and decisional processes to ensure coherence and interoperability of their processes. In this way, TRANE Company, which is our industrial case study, chose to implement the Demand Flow Technology (DFT) principles [START_REF] Costanza | Just-In-Time manufacturing excellence John Costanza Institute of Technology Inc[END_REF] to standardise all its 29 production sites. DFT methodology is a particular implementation of Just in Time concepts where, all production lines are structured in the same way in every shop floor . Consequently, all shop floor production lines have to be modelled in a similar way. This fact, justifies the need of reusability of process models to be used in simulation. Effectively, it is obvious that the time savings in simulation model design can be obtained if it is possible to reuse some simulation model modules to construct new assembly line models.

In this paper, we propose a structured approach (ASDI-dc) to build reusable and modular simulation models for manufacturing systems with distributed control. This approach is based on the ASDI (Analysis-Specification-Design-Implementation), Kellert and Force, (1998a), Kellert and Ruch, (1998b)methodology which implements the objectoriented concepts and a systemic modelling framework to the simulation techniques. The main goal of our study will be to give a framework to generate automatically specific models from generic one by using standards objects and automated functions in DFT context . According to the Trane objectives, this framework could be used by a person who is not necessarily expert in software tools. The remainder of this paper is organized as follows. In section 2, we highlight the reusability and modularity challenges in distributed control context. Section 3 presents the proposed methodological approach. Section 4 describes an industrial application related to an assembly line manufacturing. In section 5 we will discuss the credibility of the reuse and the modularity . Conclusions and open issues for future research will be presented in section 6.

2.Reusability and modularity challenges

In order to face requirements for distributed control in simulation models, this section stress reuse and modularity challenges, and presents a comparative study between some simulation modelling methodologies.

2.1.Simulation models modularity

The concept of modularity in software development refers to the encapsulation of key sub-systems, objects and components behind well-defined and relatively stable interfaces. This facilitates the integration of these components with multiple applications, as well as the evolution or possible re-implementation of these components with minimal impact on the applications using them.

Nowadays, the concept of modularity has been introduced as a logical choice in the complex systems organisation and it can be applied:

• to gather elements (model elements, meta-model elements, as meta-meta-model elements),

• to classify group modelling elements in different subject areas,

• to allow the representation of the extension of such groups (ability to describe a group as an extension of

• other group),
• to allow nesting of such groups (in order to clarify organization),

• to allow the representation of the dependencies between such groups (ability to describe the fact that elements defined in a group).

In the area of system modelling, modularity is used to improve system understanding, to reduce the model complexity, and to facilitate the reuse of standardised components. For example, systemic view subdivides the manufacturing system in three main subsystems: the physical factory subsystem, the informational subsystem (called logical subsystem in some simulation methodologies) and the decisional subsystem (Le [START_REF] Moigne | Issues in simulation model integration, reusability, and adaptability[END_REF].

In distributed control context, we believe that one appropriate rational to production system simulation should give a rise to modular models according to functional and structural criteria:



The functional criterion aims to separate physical, information and control flows. This can be very useful in order to evaluate different control policies without changing the physical system model (figure 1a) Fig. 1a: An example of functional criterion Fig. 1b: An example of structural criterion



The structural criterion aims to identify autonomous processes independently from their functional role. For example, in the case of distributed control, some entities or processes belong to physical subsystem and decisional one, rising the interaction and exchanges between the two subsystems. Thus, we must operate a particular merging that rises the autonomous processes having ability of local decision making and physical

acting. An example of those processes can be a worker who has decisional capabilities to make a local load levelling decision as well as physical capabilities to operate physical tasks. Another example can be the intelligent product having information, decisional and communication capabilities, thanks to Radio Frequency Identification (RFID) technology (Lee et al, 2004), to make itself active in the scheduling and execution of its manufacturing operations.(figure 1b)

Unfortunately, the actual simulation tools do not provide natural constructs for those kinds of modularity. Indeed, traditional discrete-event simulation models contain both the description of stochastic behaviour of the physical processes and the decisional aspects linked to product creation and parameters tuning. Bridging the gap from thecurrent practices in simulation toward modular simulation is the main goal of our approach.

2.2.Simulation Model Reuse

Reusability is one of the benefits of writing modular code, but it is also a separate goal in itself. For software objects, components or systems, to be reusable, their interfaces and implementations need to be designed so that functionality that is in an useful generic is separated from functionality that is specific to a particular application or domain. This allows the general functionality to be reused directly in other applications or domains, without the application-specific details getting in the way. This principle cuts across the interface and implementation of software elements for an object, component or service to be reusable in multiple situations, their interfaces need to be crafted using these principles, and their implementations need to be similarly organized, so that broadly useful methods and operations can be accessed separate from application-specific methods or specializations of methods.

The interest of reusability in simulation community issues is not new, lots of papers focusing on it appear in major conferences and journals (Sargent, 1986) Reese and Wyat, (1987) [START_REF] Wyatt | A framework for reusability using graph-based models[END_REF]. Recently, S. [START_REF] Richard E Nance | Simulation model reuse: definitions, benefits and obstacles[END_REF] gave a definition to the term "Simulation model reuse". He highlights the motivation to develop reusable models, the validity, the cost and credibility of reusability. The figure 2 illustrates different levels of reuse according to two axes: complexity and frequency. Reusability in the area of simulation models means capitalisation of generic knowledge about simulation models of systems that have common properties, instead of studying every system and developing specific components. This leads to generalise particular models through reference models (see figure 3) which provide generic and/or standardized representation for a given class of application. From this global vision we can extract a specific vision dedicated to simulation models for one system of this class.

Allowing reusability in simulation tools by providing a reference model for simulation of production system organised according to the DFT standard is one of our study's goals.

2.3.Literature review

In literature review, there are many persistent object-oriented methodologies for manufacturing modelling and simulation. In conceptual level, the reuse and modularity problems are partially solved by existing modelling methodologies as IDEF1X (Us Air Force,1993) and GRAI [START_REF] Doumeingts | Méthode GRAI : méthode de conception des systèmes productiques[END_REF], but they are focusing on knowledge formalization and they enable the modelling of industrial systems with a point of view that is not easily translatable to simulation models [START_REF] Galland | Methodological approach for distributed simulation: Life cycle of MAMA-S[END_REF]. In the opposite, a preoccupation with federated modelling and High-Level Architecture (HLA) (US Department of defence, 1996) has created a myopia concerning reusability but essentially at the implementation level.

Our aim is to give a methodological approach which involves conceptual and implementation levels. CM (Conical Methodology) [START_REF] Nance | The Conical Methodology and the Evolution of Simulation Model Development[END_REF], ASDI and recently ASDI-mi and MAMA-S (Multi-Agent Methodological Approach for Simulation) have explored this way. Initially [START_REF] Gourgand | Outils Logiciels Pour L'évaluation Des Performances Des Systèmes Informatiques[END_REF] highlighted the benefit for developing a knowledge model which organizes knowledge about a class of systems (called the domain) or problems, and an "action" model that instantiates the knowledge model. This decomposition will ensure the independence between the analysis phase and the choice of the tool or language used in the implementation. CM and ASDI are based on this rationale to propose modelling frameworks providing the developers with guidelines that facilitate elaboration, verification, and validation of complex simulation models. ASDI life cycle is today widely accepted in the scientific community. ASDI proposes to use the object paradigm from analysis phases towards implementation and deploys structured and consistent systemic approach throughout modelling.

The methodology ASDI-mi (m for multiple, i for incremental), proposed by [START_REF] Sarramia | ASCImi : "Une méthodologie de modélisation et de simulation multiple et incrémentielle[END_REF], adds to the initial ASDI methodology two main points: a multi-modelling approach for the domain and an incremental approach for While ASDI and CM methodologies resolve problems of modularity and formalization, they disregard the distribution aspect. The MAMA-S methodology gives a framework for building a consistent simulation platform from many independent simulation models, but does not represent distributed control within the model. At last, the HLA methodology can solve the problem of distribution at the implementation level.

Common features of these approaches are that they don't really match with modularity and reusability according to the requirements stated in sections 2.1 and 2.2. Indeed, the proposed approach ASCI-mi for modelling DSS through Multi-agents modelling concepts is mainly used for large systems composed of interacting entities, but it focuses only on structuring the decisional sub-system without taking into account the modelling of physical sub-system, and furthermore of autonomous processes merging physical and decisional capabilities.

Faced to this limit, our approach aims to propose a simulation model structure well adapted for distributed control by extending ASDI concepts to define an appropriate methodology called ASDI-dc (ASDI-distributed control).

Especially, concerning the modularity, we propose to use two criteria : not only the functional but also the structural criterion to differenciate several types of processes and concerning the reusabilty we implement special constructs allowing to build specific distributed decision models.

3.Proposed methodology

3.1.Simulation model structure

From the above research, we distil two decomposition principles for structuring simulation models:

• The separation of physical, information and control elements.

• The distinction between processes that are purely decisional or physical and the mixed processes that belong to physical and decisional systems. We named autonomous process the module which represents the association of a physical unit and a decision-making centre.

Fig. 4: A autonomous process

In the shop floor simulation, different flows of discrete entities circulate in a model made up of various processes, which will have an influence on the speed of flow, its nature or its advance within the model. These flows can represent logical or physical entities. A physical entity is a physical object, for example a product, which can be modified by physical processes such as a machine or workstation. In this case physical process is characterized by operating time, availability of resources, etc. while the product entity is characterised by arrival and departure dates, quality status, etc. (see figure 4). A logical entity is modified by control processes to make decision for creating and routing physical entities and/or launching, sizing, booking shop orders on physical processes. In discrete event simulation such a control process can be implemented by branch constructs. At last, we call "autonomous process" a process that combines physical and control processes and consequently are able to modify the physical flows and to make local control decision (see figure 4). The advantages adherence to these principles has been detailed in section 2.1. The separation of physical, informational and control elements is assumed to facilitate a higher degree of model reusability and modularity. For example, separation of physical and control processes enables to independently define the manufacturing processes and their control strategy. As a result, simulation models allow for flexible response to alternative control structures and rules without requiring a modification on the physical system models. Moreover, autonomous process concept enables a local modification of the control without modifying the global control strategy. For example, considering human operator as an autonomous process aims to simulate different task allocations taking into account operator's flexibility.

3.2.ASDI-dc methodology

The proposed methodology is an extension of ASDI, called ASDI-dc (ASDI-distributed control), to support the simulation models structure as defined below. Moreover, we add before a third principle: "the simulation framework will be used by manager who is not necessarily expert on simulation tools" that's required to use automation functions to instantiate the simulation model.

Fig. 6: ASCI-dc modelling process

In the ASCI-dc modelling process, we propose to distinguish two abstraction levels: the analysis and implementation levels (figure 6). Each of those levels is composed by two main parts: the first concerns the systems domain, the second is focused on one instance of this domain. Following we describe the main parts of the figure 6.

Domain study

The aim of Analysis step is to analyse domain and to develop a reference (or generic) model of knowledge. This model is built by identifying the common points of all the subsystems following functional and structural criteria for modularity.

• The logical subsystem is composed of the whole information about transactions flows. As an example we find the information about the raw materials, components, bills of material, and the associated set of manufacturing routing.

• The physical subsystem (PSS) is composed by the means of production and handling, their geographical distribution and their logical and physical interconnections.

• The decisional subsystem (DSS) called also the management system specifying the management rules and structured in hierarchical decision centre (strategic, tactical, operational or reactive).It acts at the same time on the physical subsystem (rules of breakdowns management, rules of resources allocation,…) and on the logical subsystem (rules of passage to an alternate routing,…).

• Communication model between the three subsystems is necessary. It permits to describe interactions between objects of subsystems.

• To ensure structural criterion of modularity, autonomous processes must be defined trough its behavioural model.

In Implementation level, in first way, we define rules to build action models or basic components; it is a very important step for reusability. We will explain this fact in the case study. In the second way; we build the software components library that will be used automatically to generate models for one system of the studied class.

Concerning the autonomous processes, we propose to associate the physical part and the decisional one. Different problems, like modification of the control strategy, will be simplified.

3.2.2Instances of domain model: System study

In analysis level, the experts use the reference knowledge model to analyze and specify their industrial system. This reference model can be adopted at the particular system by specifying the functionality of some system parts, add method or attributes.

The last phase, Implementation level, is about action model implementation using the software library components and automation function. This action model will be used to evaluate system performances.

4.Case study

4.1.Presentation

Trane Company provides indoor comfort systems and comprehensive facility solutions for residential, commercial and industrial building needs. As we present in the introduction of this paper, the 29 production sites are designed according to DFT concepts. The objective is to optimize production and also standardize processes. The production context is as follows: the shop floor is organized in pull production. To ensure a better balancing of an assembly line every worker must be able to work at three workstations: his workstation (i.e. initial affectation), the upstream workstation, and the downstream workstation. The objective is to model an assembly line and adapts it at all company assembly lines. The control system is globally centralized; i.e. every week the company compiles the Master Production Schedule which proposes finished products manufacturing orders; but some decisions are made locally by workers that represent the distributed aspect of decision. In order to resolve worker mobility problem, we can use two approaches. In the first one, we simplify modelling by using a "capacity factor", for example, if an operator spend 70% of his time at work station wi and 30% on the wi+1 or wi-1, at the first work station we will consider that the available capacity will be 70% of theoretical capacity and 30% at the second work station. This approach corresponds to the centralized one. The second way is to consider human operator as an "autonomous process", therefore, we take into account distributed aspect. That corresponds to the distributed control. In both approaches (centralized and distributed control), all necessary data for simulation (manufacturing time, products information, initial affectation of workers etc) are saved in a database and transferred to the simulation model. We have modelled the system using the two approaches. This enables us to compare distributed and centralized control results. To build simulation models for DFT manufacturing system we use our proposed methodology ASDI-dc. The following section describes the major steps of ASDI-dc methodology.

4.2.Domain Analysis Phase

To structure our analysis we describe a domain studied in natural language, and then we formalize it in UML in order to get a reference model of the domain. (See figure 7, 8 and 9).

In the decisional subsystem we represent a relational structure between organizational decision-making centres. We distinguish two types of decision-making centres: centralized system and distributed decision centres. The centralized system control centres can make decision in the short (operational), medium (tactical) or long (strategic) horizon. The relation between these centres can be hierarchical or at the same level (figure 7). The distributed decision centres can represent the decisional processes of "autonomous processes". The informational subsystem is based on the product. It describes its characteristics, its range (bill of materials) and in our case we find also the MPS which contains information on the number of products to be manufactured for one period given (in major case it will be one week), the order of product manufacturing, and the release date of each product (figure 9).

Fig. 9: A logical subsystem of an assembly line

4.3.Specification

In the first step, filtering operations of the domain reference knowledge model has been achieved to extract the particular vision dedicated to the simulation. Then, we added attributes and methods to the existing objects for the simulation models implementation. As we said before, in this phase, functions and behavioural model of system objects will be described. In this paper, we show only behaviour models of autonomous processes. The algorithm describing operator decision process is described after:

Operator j takes decisions according to variables of his environment that are: (Pwi) and (Swi) with wi indicating initial work station of operator.

Let Pwi be the availability of the product: Pwi є {0, 1} with Pwi=1 product in queue i; i=0 there is no product in queue.

Let Swi be the signal of work Swi є {0, 1} with Swi=1 work station state (wi) is free, Swi=0 work station (wi) is busy.

Let Dwij be a decision of operator j in work station wi. Dwijє {-1, 0, 1} with Dwij = -1 upstream displacement. Dwij =0 no displacement. Dwij = 1 Downstream displacement.

Let Oj be operator j has as attributes wi initial workstation competencies Cj є {C1, C2…Cn} and effectiveness Ej є {0...1}.

Let Affect (Oj, wi) be: operator j work in workstation i

Let Apt(Oj,wi) be: a Aptitude of operator j to work at workstation i (Apt(Oj,wi)=0 operator j don't be competent for work at workstation i).

The decision matrix for an operator i in workstation wi is the following (see table 1):

Cases 1 and 2 can be regrouped into one case. If Operator works station is busy the operator moves downstream.

Indeed in pull production shop floor the operator pull flow in priority.

We simplify this decision matrix by a simple function:

Dw (i,j): Pwi, Swi є {0,1} Dwij є {-1, 0,1} Dwij= Swij x (Pwij-2) + 1
Decision algorithm:

(1)Initialization Affect (Oj,wi) In this step we must also choose the tools used for the action model implementation. The choice is dependant of subsystem nature.

Cj = Competence є {C1,C2 .Cn} Ej=X // (X
• To model the physical subsystem, we were interested in the simulation software using an oriented-object approach for several reasons. First this approach leads to keep coherence between all the ASDI-dc cycle steps: for example the knowledge model in UML resulting of analysis phase will be easily exploited to build the action model. In addition, this approach makes it possible to identify each object of the actual system with an object of model [START_REF] Anglania | Object-oriented modeling and simulation of flexible manufacturing systems: a rule-based procedure[END_REF]. Several software exist (Arena, AutoMod, Modelica, and Witness). The choice is related to Arena, very used in the industrial and academic fields A.M.A Al-Ahmari and K. Ridgway. (1999), H. De Swaan Arons and Csaba Attila Boer.( 2000) [START_REF] Perera | Methodology for rapid identification and collection of input data in the simulation manufacturing systems[END_REF]) [START_REF] Kovács | Application of software reuse and objectoriented methodologies for modelling and control of manufacturing systems[END_REF]) (Guilherme, 2004) as well as in our company. The principle of this software is to generate one or more flows of discrete entities, which can represent flows of information or physical flows.

Arena has two interesting properties: a VBA interface to ensure communication with the other software, a "professional Arena" support which makes it possible to create its own library components and thus makes it possible to encapsulate the data of certain parts of the Arena model.

• For informational subsystem, we used Excel to store necessary information of Arena model (Nb of operator, competence on the stations, products to be manufactured.).

• Decisional subsystem has as rule the control of production and, in our case, the control of the Arena model, is developed in VBA.

4.5.Domain Implementation:

We design a basic components library: Object "work centre" that is materialized by a sub-model or process in Arena.

Each process has one or several objects "workstations". This architecture enables to keep a hierarchical vision of the assembly line.

For the distributed control, the autonomous process is the worker; the decisional process is represented mainly by a VBA block. When a product arrives at workstation wi a signal is sent to show availability of product, then a logical entity made up to the corresponding VBA block, the control of this entity is passed to the VBA Sub procedure created in the Visual Basic Editor. This procedure describes the autonomous process behaviour. The physical process is materialized by a resource in Arena (figure 10). The operator interface leads to enter the operator attributes and VBA Code if operator behaviour has been modified (figure 11).

4.6.Implementation: Action Model

In the following step, we use the library components to create the action model through Arena software facilities.

5.Discussion

5.1.Credibility of reusability

The reusability is ensured in several ASDI-dc process steps: in domain implementation level, by giving a library of constructs called "Template" in Arena environment, and in system level, the reusability is based on the automation function to build simulation models thanks to VBA facilities.

A new model will be a white screen where we can enter all the required model constructs (see figure 12). Arena provides several templates. The widely used are the "Basic Process" template, the "Advanced Transfer" template and the "Advanced Process" template. In this way, we are developing our template "Trane" which contain our own custom modules for specific highly repetitive issues as workstation, human operator, orders management etc. The process of developing a simulation model is by instantiating a module out of the template into the modelling area, via drag and drop or via VB interfaces thanks to automation function (for facilitate the use) on those interfaces we can set the parameters concerning to this module (for example, in module human operator: the name of operator, his competences, his first workstation allocation.

As an example of modularity benefit: on the same physical subsystem (Arena Model) we can simulate several strategies for example testing different rules from sequencing changing job sequences without changing the routing physical processes. The modification will be acting only on Excel product "spreadsheet" or /and VBA procedure and not on Arena model which present physical sub-system.

On the other hand, the concept of autonomous process leads to change behaviour model without changing a centralised control model. For example we can change mobility rules for operators without changing the numbers of operators and their attributes.

5.3.Tests and Validation

In any process modelling, the tests and validation phases are very important; they enable to measure the confidence interval between the simulated results and the actual data and evaluate the credibility of models. The figure 13 and 14 present lead time results relative to two tests done on sample of 15 products. The first one is interesting to centralized approach and the second to distributed approach. The two picks on the figure 13 (A,B) show that if one problem occurs at a work station wi, it has an influence on the lead time at stations wi-1 and wi+1.

Fig. 2 :

 2 Fig. 2: A spectrum of reuse Fig. 3: An example of reusability

  modelling a system of the domain. Chabrol et al. (2006) propose a multi-agents modelling based on the Decisional sub-system (DSS) class diagram to model a particular domain related to Urban Traffic System.

Fig. 5 :

 5 Fig. 5: The autonomous process meta-model In figure.5, we propose a meta-model of those entities and processes. An autonomous process is composed by a physical part (like resources or stations) and a decisional process; the decisional part controls the physical one according to the behaviour model. It has two different types of attributes: external and internal. The functions and the behaviour model of the system processes needs to be described.

Fig. 7 :

 7 Fig. 7: A decisional subsystem of an assembly line The physical subsystem concerns an assembly line. As we can see in figure 8 each assembly line is composed by a set of work centres each work centre is composed by one or several work stations. A work station can be connected to a feeder etc.). The communication model can be developed by the use of UML Sequences. It describes interactions and communication between the three systems.

Fig. 10 :

 10 Fig. 10: a autonomous process in Arena environment Fig 11: The operator interface

Fig 12 :

 12 Fig 12: The Arena environment At the left side we have the main model constructs called "Template" we can use different template to build a model. In fact,

Fig. 13 :

 13 Fig. 13: The centralized case Fig. 14: The distributed case This problem is due to workers mobility. As we said in preceding section, in centralized approach we model the workers mobility as the change of theoretical capacity on the work station. Indeed, in a stable environment this approximation gives relatively best result but if a problem arrives "on line" we are not able to change a work station capacity dynamically. Consequently, we use the distributed approach to refine the simulation model. We obtained with the same sample the results on figure 14. The distributed case results show that it will be possible to improve the shop floor simulation model and decrease the variability caused by local decision.

Fig. 5 :Fig

 5 Figure CaptionsFig. 1a: An example of functional criterion Fig. 1b: An example of structural criterion Fig. 2: A spectrum of reuse Fig. 3: An example of reusability Fig. 4: A autonomous process Fig. 5: The autonomous process meta-model Fig. 6: ASCI-dc modelling process Fig. 7: A decisional subsystem of an assembly line Fig. 8: A physical subsystem of an assembly line Fig. 9: A logical subsystem of an assembly line Fig. 10: a autonomous process in Arena environment Fig 11: The operator interface Fig 12: The Arena environment Fig. 13: The centralized case Fig. 14: The distributed case

  In the domain design phase, we define rules for building the "action model" basic components .The table 2 shows the more important objects.Other rules concern the name of Arena objects, for example: a work station resource is named Mij when i is a work centre and j is a work station in work centre i.

	End While
	While Apt (Oj, wi+D) =1 then
	Stop=True
	Affect (Oj, wi)
	"we affect the operator j at work station wi
	End While
	4.4.Domain Design
	will be in {0...1})
	(1)Waiting Event
	If Event then D=Dw(i, j)
	"Execute decision matrix
	End If
	(1)Research
	While (Stop = False)
	"While Stop condition is false
	If Apt (Oj, wi+D) = 0
	"We test the aptitude of operator j to work in station wi+D
	Then wi=wi+D
	"wi=wi+1 or wi=wi-1 according to D
	Else Stop=True
	End If

Tij: theoretical operational time in work station j work centre i Qij: queue in work station i and work centre j

Table 1 :

 1 The decision matrix for an operator i in workstion wi

	Domain Objects Arena Objects
	Work Centre	Process
	WorkStation	Resource
	Stock	Queue
	Path	Route
	Autonomous	VBA /resource
	process
	Convoyer	Convoyer
	Assembly line	Arena Model

Table 2 :

 2 the most important domain objects

The study of different simulation methodologies enabled us to answer limitations that must be addressed to improve their effectiveness in a distributed control context. The ASDI methodology enables to answers formalization, modularity and "reuse" problems. But it doesn't take into account the distribution aspect. Our contribution concerns all ASDI life cycle phases in the definition of autonomous processes and their conceptual model. In design and implementation, we used Arena and Visual Basic software for application to develop a generic component for control. The question of model validity can not be ignored. It seems widely accepted in the simulation community that models or modelling approaches can not be fully validated. It makes sense to have some form of model quality insurance to ensure that the model is fit for its intended purpose. In the future research we will interest to the following two objectives. The first one is to give a more formal setting for this approach and propose a simulation platform to build simulation model in DFT context. The second one deals within the scope of our laboratory research team, this scope concerns product driven manufacturing systems. In this project we consider that the product can storage its own information and can be an actor of its own transformations. This fact deals with intelligent products resulting from HMS architecture. In the DFT context, the concept of Product-Driven control is very developed. For example, the signal of work is given by the product state. However, physical flow and information flow synchronisation are not assured. To resolve this problem, new technologies of identification as RFID have appeared.

The goal of our next work will be to use simulation as a tool to integrate this technology in Trane Company legacy systems. In our current case, autonomous process concerned labour on the shop floor. Nevertheless, it would be interesting to analyse how to adapt the autonomous process concept to intelligent product concept.