Jully Jeunet
email: author.jully.jeunet@dauphine.fr

Federico Della Croce

Fabio Salassa

Heuristic solution methods for the selective disassembly sequencing problem under sequence-dependent costs

Keywords: Disassembly, Product recovery, Maintenance, Greedy algorithms, Matheuristics 1

The first Waste Framework Directive issued by the European Union dates back to the seventies but was drastically amended in the last decade to reduce environmental impacts of waste by encouraging reuse, recycling and remanufacturing. Product recovery starts with disassembly which results in high labor costs. Disassembly supports environmentally conscious choices like replacement of defective parts to extend the life span of products, removal of suitable components for reuse and extraction of hazardous substances to decontaminate materials for reprocessing. Besides, selective disassembly also accommodates maintenance and repairs. Optimizing the cost of disassembly is crucial to make this process an economically viable option. Due to change tools and parts reorientation, disassembly costs are sequence-dependent. Therefore minimizing the disassembly cost involves the search for an adequate sequence of disassembly tasks. Consequently, this paper addresses the disassembly sequencing problem for selective and sequential disassembly under sequence-dependent costs. As optimal formulations fail to handle real-world cases, we develop a randomized greedy algorithm (needing a very few number of parameters to be set and proving to be robust with respect to their value) and a matheuristic to solve efficiently medium to large-sized instances.

Introduction

Disassembly encompasses a wide variety of issues that mostly depend upon the decision level. On a strategic level, design for disassembly such as increasing modularity is meant for easier reuse of components and materials (see for instance Chiodo andIjomah, 2014 or Soh et al., 2014). Disassembly for remanufacturing using strategic perspectives has been studied in [START_REF] Tian | Operation patterns analysis of automotive components remanufacturing industry development in China[END_REF] and [START_REF] Priyono | Strategic operations framework for disassembly in remanufacturing[END_REF]. Also the problem has been studied in multi station environments with line balancing requirements [START_REF] Li | A branch, bound, and remember algorithm for the simple disassembly line balancing problem[END_REF] and when buffer allocation among stages is considered [START_REF] Alfieri | The buffer approximated Buffer Allocation Problem: A row-column generation approach[END_REF].

In disassembly planning problems, some recent works focus on joint optimization of collecting End-Of-Life products and disassembling them [START_REF] Habibi | Collection-disassembly problem in reverse supply chain[END_REF] or aim at reducing unnecessary inventories generated by products disassembly [START_REF] Godichaud | Collection-disassembly problem in reverse supply chain[END_REF].

In these planning models, the disassembly cost of products is a parameter since the disassembly sequencing problem is assumed to be already solved. Thus, adjacent and central to disassembly planning is disassembly sequencing where the main objective is to find a sequence of disassembly tasks so as to detach parts of interest (disassembly can be either selective or complete) while minimizing the dismantling cost or time, subject to precedence constraints between components. When disassembly is performed manually as is the case in this paper, the disassembly cost is equal to the disassembly time multiplied by the labour cost. Thus as the cost is proportional to the time, these terms can interchangeably be used. The disassembly time of each disassembly operation depends on the sequence, due to tool selection and part reorientation. That is, the disassembly time of operation j, if performed after disassembling part i, not only includes the time to dismantle j but also the time to change tool if different from the one needed for i as well as the time to move the product so as to access the fasteners of j. With sequence-dependent costs (or time), the sequential disassembly sequencing problem (DSP) is known to be a NP-hard problem [START_REF] Lambert | Methods for optimum and near optimum disassembly sequencing[END_REF] and as such, exact methods have limited real-world applicability.

In this paper, we address the DSP with the aim of obtaining target components from a product for the purpose of maintenance, recycling or remanufacturing, where parts are sequentially and manually disassembled and disassembly times are deterministic and sequence-dependent. For this problem, an optimal solution method has been developed by [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF] that can be applied to DSP with up to 50 parts. For large scale problems, these authors have proposed simple priority rules, therefore leaving room for the development of more efficient heuristic solution methods. We thus propose a Randomized Greedy Sequencing Algorithm and a Matheuristic approach. Our greedy algorithm generates feasible sequences by filling one by one the empty positions with components probabilistically selected according to their disassembly time. Random repetitions are performed and insertion of disassembly operations is considered for further improvements. Our greedy approach only needs a very few number of parameters to be set and proved to be robust with respect to their values. Matheuristics are based on a decomposition of the problem into sub-problems of limited size for which an optimal solution can be quickly obtained. So far, they had not yet been tested on the DSP, despite their ability to solve efficiently many combinatorial problems in production and operations management (e.g. [START_REF] Iassinovskaia | The inventory-routing problem of returnable transport items with time windows and simultaneous pickup and delivery in closed-loop supply chains[END_REF][START_REF] Della Croce | A hybrid heuristic approach for single machine scheduling with release times[END_REF] and 2014(b); [START_REF] Raa | A matheuristic for aggregate production-distribution planning with mould sharing[END_REF][START_REF] Guerrero | Hybrid heuristic for the inventory location-routing problem with deterministic demand[END_REF]. As Matheuristics make use of mathematical programming models, they can provide near optimal solutions only to moderate-sized problems. The advantage of our Matheuristic for the DSP is its ability to find better solutions than the exact approach of [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF] that often failed to find the optimal solution to medium-sized problems in a reasonable computation time. For large-sized problems with hundreds components to disassemble, [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF] showed the superiority of the Nearest Neighbor algorithm over other simple priority rules. However, when compared with our Greedy algorithm and our Matheuristic, the Nearest Neighbor algorithm performed so poorly that we suggested an improved randomized version of this algorithm. We used a rigorous simulation framework to generate realistic instances for which we showed the superiority of our methods over that of [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF]. For many instances with product structures with 50 components, the exact approach of [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF] most often failed to find the optimal solution, in which cases our heuristic solution methods beat by far the solution of the optimal method obtained after one hour of CPU. For large instances with several hundreds of parts, the Nearest Neighbor algorithm which was assessed as the best heuristic in [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF] showed deviations to our Randomized Greedy Search Algorithm from 30 to 75% whereas these deviations did not exceed 10% on average for our Randomized version of the Nearest Neighbor algorithm.

In real-world problems, disassembly is generally selective because (i) remanufacturing processes require retrieval of cores only over non-remanufacturable parts; (ii) maintenance is implemented on specific usury parts; (iii) not all materials can be recycled or can only be recycled a limited number of times. The most frequent situation is that of a single worker sequentially dismantling a product to obtain one part at a time. Therefore, parallel execution of disassembly operations to remove several parts simultaneously has been seldom studied in the literature (see e.g. [START_REF] Ren | An asynchronous parallel disassembly planning based on genetic algorithm[END_REF][START_REF] Zhang | Parallel disassembly sequence planning for complex products based on fuzzy-rough sets[END_REF][START_REF] Edmunds | Using constraint-satisfaction to optimise disassembly sequences generated from AND/OR information[END_REF]. Besides, disassembly remains a labor intensive process because automation demands high investment costs and implies a loss of flexibility in accessing fasteners. Actually, human intervention will always be needed to choose proper tools for removing fasteners when damaged by corrosion for instance [START_REF] Chang | Approaches and challenges in product disassembly planning for sustainability[END_REF]. As the labor cost is proportional to the disassembly time, minimizing the cost is equivalent to minimizing the total disassembly time (see [START_REF] Gonzalez | A scatter search approach to the optimum disassembly sequence problem[END_REF]Adenso-Dìaz, 2006 or Wang and[START_REF] Johnson | Design for disassembly and recyclability: A concurrent engineering approach[END_REF]. In addition to time or cost minimization, other objectives are sometimes considered like removing components according to a priority list [START_REF] Adenso-Dìaz | A path-relinking approach for a bi-criteria disassembly sequencing problem[END_REF] or maximizing the profit gained from recycling [START_REF] Ren | An asynchronous parallel disassembly planning based on genetic algorithm[END_REF] or maximizing this profit and minimizing the energy consumption related to disassembly [START_REF] Tian | Modeling and Planning for Dual-Objective Selective Disassembly Using and/or Graph and Discrete Artificial Bee Colony[END_REF]. More recently, the quality of disassembled components has also been included [START_REF] Bentaha | A decision tool for disassembly process planning under end-of-life product quality[END_REF][START_REF] Tian | Disassembly Sequence Planning Considering Fuzzy Component Quality and Varying Operational Cost[END_REF].

As previously mentioned, the cost of a disassembly operation is sequence-dependent and is usually assumed to be deterministic in sequential disassembly settings. Several papers consider this dependence through geometric aspects like rotation or more generally disassembly directions to access fasteners [START_REF] Tseng | A block-based genetic algorithm for disassembly sequence planning[END_REF][START_REF] Yeh | Simplified swarm optimization in disassembly sequencing problems with learning effects[END_REF][START_REF] Go | Genetically optimised disassembly sequence for automotive component reuse[END_REF][START_REF] Smith | Disassembly sequence structure graphs: An optimal approach for multiple-target selective disassembly sequence planning[END_REF][START_REF] Gonzalez | A scatter search approach to the optimum disassembly sequence problem[END_REF]Güngör and[START_REF] Güngör | An evaluation methodology for disassembly processes[END_REF][START_REF] Güngör | Disassembly sequence plan generation using a branch-and-bound algorithm[END_REF]. Solution methods developed in these papers are mainly metaheuristics. [START_REF] Yeh | Simplified swarm optimization in disassembly sequencing problems with learning effects[END_REF] developed a simplified swarm optimization with costs integrating learning effects; [START_REF] Go | Genetically optimised disassembly sequence for automotive component reuse[END_REF] adopted a Genetic Algorithm and [START_REF] Gonzalez | A scatter search approach to the optimum disassembly sequence problem[END_REF] proposed a scatter search algorithm.

Other papers are based on disassembly cost or time estimates between each feasible pairs of operations [START_REF] Luo | Integrated multi-layer representation and ant colony search for product selective disassembly planning[END_REF][START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF][START_REF] Lambert | Methods for optimum and near optimum disassembly sequencing[END_REF][START_REF] Lambert | Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs[END_REF][START_REF] Lambert | Optimizing disassembly processes subjected to sequence-dependent cost[END_REF][START_REF] Huang | Disassembly sequence generation using a neural network approach[END_REF][START_REF] Johnson | Economical evaluation of disassembly operations for recycling, remanufacturing and reuse[END_REF]. [START_REF] Luo | Integrated multi-layer representation and ant colony search for product selective disassembly planning[END_REF] used an ant colony approach to solve small instances of the DSP, whereas [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF] developed an optimal formulation similar to the modified two-commodity network flow model of [START_REF] Lambert | Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs[END_REF].

Besides, in parallel disassembly environment, some contributions deal with random disassembly costs or times, developing heuristic and exact approaches (Kim and Lee, 2018;Kim et al., 2018;[START_REF] Kim | An optimal algorithm for selective disassembly sequencing with sequence-dependent set-ups in parallel disassembly environment[END_REF]Tian et al., 2012aTian et al., , 2012bTian et al., , 2013)).

The remainder of the paper is organized as follows. The next section provides the problem description and the representation of precedence constraints. Section 3 gives the optimal formulation of the DSP as proposed by [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF]. The randomized greedy sequencing algorithm is detailed in Section 4 and Section 5 describes the matheuristic algorithm. The simulation framework and results analysis are presented in Section 6. Section 7 summarizes our findings and suggests directions for further research.

Problem description

As in [START_REF] Lambert | Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs[END_REF], we adopt a disassembly precedence graph, G, to represent disassembly operations and their precedence relationships. Such a graph is a set of n + 1 nodes where root node 0 corresponds to the start of disassembly and n is the total number of parts that can be obtained through disassembly operations whose precedence relationships are symbolized by arcs.

Figure 1(a) displays two graphs G 1 and G 2 each representing a product with n = 20 components. Graph G 1 , including only arcs in solid lines, exhibits a complete divergent structure where disassembling one component never requires more than one direct predecessor to be dismantled before, immediately or not in the sequence. In addition to arcs in solid lines, G 2 involves dotted arcs and thus has a general structure where detaching one component can need several operations to be performed before. Letting 1 (j) be the set of direct predecessors of node j, in a complete divergent structure we have 1 (j) = 1, 8j = 1..n whereas 1 (j) 1 in a general structure. For instance 1 (16) = {9} in G 1 and 1 (16) = {4, 6, 9} in G 2 . We introduce the notion of mandatory components to designate not only target components but also all the components that have to be disassembled before these targets to meet the precedence constraints. The set M of mandatory components is simply defined as M = T [ j2T ˆ 1 (j), where T is the set of targets and ˆ 1 (j) is the set of ancestors of j (direct and non direct predecessors) in the graph. Ancestor matrix ˆ 1 is obtained from predecessor matrix 1 by setting first ˆ 1 := 1 and then

ˆ 1 := ˆ 1 _ 1 i , i = 1..n.
Set M is a straightforward feasible sequence to the disassembly problem and also provides the minimum disassembly rate of a product, (|M| 1)/n, which gives a better picture of the complexity of the problem than the sole number of target components does. Indeed, depending upon its location in the graph and on the structure of it, one target component may require from one to up to all components to be disassembled. In G 1 or G 2 , if the target component is 5, the disassembly problem is quite easy to solve whereas candidate sequences are far more numerous if component 18 is a target. In Figure 1(a), bold circles represent mandatory parts in G 1 with M 1 = {0, 1, 2, 3, 5, 7, 8, 9, 11, 13, 16} and underlined numbers are mandatory components numbers in G 2 with M 2 = {0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 16} leading to a minimum disassembly rate of 50% and a minimum of three targets in both cases (T 1 = {8, 13, 16} in G 1 and T 2 = {5, 10, 16} in G 2 ). The recycle rate thus varies from 3/20 to 0.5 and more if all components in the optimal sequence can be recycled. As disassembly times are sequence-dependent, it can be optimal to disassemble one or more non mandatory parts between two mandatory ones. A matrix of disassembly times t i,j is provided in Figure 1(b), where t i,j is the disassembly time in seconds when i immediately precedes j in the sequence. With these Figure 1: Disassembly precedence graphs and disassembly times times, optimal sequences for G 1 and G 2 both include non mandatory component 6. They are obtained using the formulation of the disassembly sequencing problem we present in the next section.

Mathematical programming formulation of the disassembly sequencing problem

We adopt the formulation of [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF] for it proved to be at least as efficient on several instances as two other formulations of lower complexity that we developed and in which variables express the position of components in the disassembly sequence, with either a linear or a quadratic objective function. These alternate formulations are given in Appendix A. [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF] make use of the variables defined in Table 1 in which we also summarize the notations for the parameters.

Variables xi,j

Binary variable equal to one if i immediately precedes j in the sequence, and zero otherwise yj

Binary variable equal to one if j is disassembled, and zero otherwise zi,j

Binary variable equal to one if i must be disassembled before j in the sequence and zero otherwise Parameters (j) Set of direct successors of j in the precedence disassembly graph 1 (j) Set of direct predecessors of j in the precedence graph ˆ 1 (j) Set of ancestors of j in the precedence graph (direct and non direct predecessors)

T

Set of target components M

Set of all mandatory components to be disassembled which includes set T and all their ancestors in the graph. We have

M = T [j2T ˆ 1 (j) M Set of non mandatory components, M = {0..n} \M ti,j
Disassembly time (in sec.) of operation j when i immediately precedes j in the sequence

Table 1: Notations

The objective is to minimize the total disassembly time min

X i=0..n X j=0..n t i,j • x i,j , (1)
subject to the following constraints.

Input and output flow conservations are written as X i=0..n

x i,j = y j , 8j = 1..n.

(2) X j=0..n

x i,j  y i , 8i = 0..n, j = 0..n.

(3)

Mandatory components must be disassembled

y j = 1, 8j 2 M. ( 4
)
If i is a direct predecessor of j in the graph and if j is disassembled (y j = 1) then i must be disassembled as well (y i = 1)

y j  y i , 8j = 1..n, i 2 1 (j). ( 5
)
If i is a direct predecessor of j in the graph then j cannot be disassembled before i in the sequence

z j,i = 0, 8j = 1..n, i 2 1 (j). ( 6
)
If j is disassembled before i, the opposite is false and conversely

z j,i + z i,j = 1, 8i = 1..n, j = 1..n, i 6 = j. (7)
Constraints ( 7) are redundant with (6) but increase the tightness of the formulation.

If, in the sequence, component i is disassembled before j and j before k thus i is disassembled before k

z i,j + z j,k z i,k  1, 8i = 0..n, j = 1..n, k = 1..n, i 6 = j, k 6 = j. ( 8
)
If i is not disassembled before j (z i,j = 0) thus i cannot be disassembled immediately before j (x i,j = 0)

z i,j x i,j 0, 8i = 0..n, j = 0..n. (9)
Let us note that constraints (9) allow for z i,j = 1 and x i,j = 0 meaning that z i,j = 1 if i must precede j in the sequence even if j is not sequenced right after i (x i,j = 0). Finally a disassembly operation cannot be performed on one component itself

x i,i = 0, 8i = 0..n. ( 10
)
4 Randomized Greedy Sequencing Algorithm (RGSA)

At the core of our RGSA is a sequencing procedure that generates a feasible sequence by filling one by one the empty positions with mandatory components probabilistically selected according to their best cumulative disassembly time.

The cumulative time of any component is defined as its disassembly time from its immediate predecessor in the sequence, to which is added that of its quickest successor operation. A pass of the sequencing procedure consists in repeating this procedure on a same set of mandatory components until no improvement of the sequence is found during the last N repetitions. Over the whole repetitions, we record the maximum time loss associated with each non mandatory operation and the position in the sequence at which this maximum occurs. In this way we get a proxy of opportunity time losses as a result of the exclusion of non mandatory operations from the sequence. Based on these losses, non mandatory components are then considered one by one for possible insertion in the sequence in subsequent passes. To describe our RGSA we adopt the notations and definitions in Table 2. Obviously, root node 0 is sequenced in the first position (Pos = 1) of the sequence. The pseudocode of the whole algorithm is given in Table 3 where Table 3(a) provides the main steps of the RGSA and Table 3(b) details the sequencing procedure.

To illustrate, let us consider the example in Figure 1. With graph G 1 , RGSA Initialization consists in setting S best := M 1 = {0, 1, 2, 3, 5, 7, 8, 9, 11, 13, 16} which is the straightforward feasible sequence that we provided in Section 2. The corresponding disassembly time is Obj(S best ) = t 0,1 + • • • + t 13,16 = 776. A first application of the Sequencing procedure is implemented on set M without insertion (i ⇤ = 1). In position Pos = 1, we have S 1 = {0}, s = 0.

In position Pos = 2, the set K of candidates is K = (0) = {1, 2}, with M = {1, 2} since both operations are mandatory. In sub-procedure Select mandatory compo we first compute t m for m 2 {1, 2}. Using Eq. ( 11) and Eq. ( 13) for m = 1, we get F (1) = (1) = {3, 5} and F 1 = K \ {1} [ F (1) = {2, 3, 5}, meaning that from operation 1, component 2 or 3 or 5 can be disassembled. From Eq. ( 14), we obtain the cumulative disassembly time of operation 1, t 1 = t 0,1 + min{t 1,2 , t 1,3 , t 1,5 } = 131. This time t 1 reflects the minimum time we could obtain if operation 1 was performed between 0 and its quickest following operation, namely 5. Applying the same reasoning on candidate m = 2, we get t 2 = t 0,2 + min{t 2,1 , t 2,4 , t 2,6 , t 2,7 } = 57.

SPos 1

Set of previously sequenced operations, with SPos 1 = {s1, s2, . . . , sPos 1} and s1 = 0

s Last sequenced component in SPos 1 (s ⌘ sPos 1) F (k)
Set of immediate successors of component k in the graph that can be dismantled if k is disassembled. These feasible successors are such that all their direct predecessors in the graph (except k) are already detached. We have

F (k) = j 2 (k) | 1 (j) \{k} ⇢ SPos 1 (11)
In a complete divergent graph, we always have

F (k) = (k).
K Set of all candidate components that can be detached in position Pos with

K := K \ {s} [ F (s) (12)
In position 2, we have

K := {0} \ {0} [ F (0) = (0) Fk Set of feasible successors in the sequence of candidate k 2 K if k is disassembled, with F k = K \ {k} [ F (k) (13)
tk Cumulative disassembly time if k is sequenced after s and before its successor in the graph with minimum time. We have

t k = t s,k + arg min j2F k t k,j (14)
= T [ j2T ˆ 1 (j) s = 0 Compute |M| S 1 = {0} S best := M Obj(S 1 ) = 0 Obj(S best ) = P (i,j)2M t i,j j = 0, 8j = 1..n for Pos = 2.. |M| 1 best j = 1, 8j = 1..n Update sets i ⇤ = 1
Determine K using Eq. ( 12)

Multi-pass sequencing if i ⇤ > 0 and best i ⇤ > 0 do if Pos = best i ⇤ Initialization M := M [ {i ⇤ } j = 1, 8j = 1..n else NoImprovement=0 M := M \{i ⇤ } ImproveInsert=0 Update |M| do Select mandatory compo Sequencing procedure ! for all candidates m 2 M , M = K \ M if Obj(S) < Obj(S best ) Compute cumulative time tm Obj(S best ) = Obj(S)
Determine set F (m) with Eq. ( 11) S best := S Determine set Fm with Eq. ( 13)

best j := j , 8j = 1..n Compute tm with Eq. ( 14) NoImprovement=0 ImproveInsert+ = 1

Compute t M = min m2M {tm} else NoImprovement+=1 for all candidates m 2 M while NoImprovement < N

Compute pm with Eq. ( 15)

RGSA updates Draw r = ⇡ + u, where u ⇠ U [0, 1 ⇡] and if i ⇤ > 0 ⇡ is a parameter depending on n if ImproveInsert > 0 M := M [ {i ⇤ } Select m ⇤ accordingly M := M \{i ⇤ } if m ⇤ = i ⇤ else |M| + = 1 i ⇤ := 1 Update score and insertion position Compute = max m2 M { m} for all candidates m 2 M , M = K \M if > 0 Compute cumulative time t m Determine i ⇤ = arg max m2 M { m} Compute t M = min m2 M {t m} while > 0 if t M < t M Determine m⇤ = arg min m2 M {t m}) if m⇤ < 1 t M /t M and m⇤ 6 = 1 Update m⇤ := 1 t M /t M m⇤ = Pos Update sequence S Pos = S Pos 1 [ {m ⇤ } Obj(S Pos ) := Obj(S Pos 1 ) + t s,m ⇤ s := m ⇤ Last position (Pos = |M|)
Fill it with the remaining mandatory component The minimum t M = min{t 1 , t 2 } = 57 leads to a probability of selecting operation 1 equal to p 1 = (57/131)/((57/131)+ (131/131)) w 0.31 and consequently p 2 = 0.69. To give the algorithm a better chance to pick the best option, the random draw is set to a minimum value ⇡. Preliminary experiments showed that a better performance is obtained when ⇡ is increased with n since with more operations, the selective pressure must increase to limit the choice to a few number of good operations. If for instance ⇡ = 0.60 and r = 0.70 then m ⇤ = 2 is selected. The sub-procedure Update score and insertion position is skipped in Pos = 2 since set M of non mandatory operations is empty. Update sequence leads to S 2 = {0, 2}, Obj(S 2 ) = t 0,2 = 29, s = 2.

In position Pos = 3, the set K of candidates is updated using Eq. ( 12) so we get

K := {1, 2} \ {2} [ F (2) with F (2) = (2) = {4, 6, 7}, that is K = {1, 4, 6, 7}.
The set of mandatory components is M = {1, 7} on which we apply sub-procedure Select mandatory compo. We obtain F 1 = {1, 4, 6, 7}\{1}[{3, 5} = {3, 4, 5, 6, 7}, thus t 1 = t 2,1 + min{t 1,3 , t 1,4 , t 1,5 , t 1,6 , t 1,7 } = 100. The set of feasible successors of component 7 is F 7 = {1, 4, 6, 8, 10}, thus t 2 = 69. We therefore have t M = 69 so p 1 w 0.41 and p 7 = 0.59 leading to the selection of m ⇤ = 7 (since ⇡ = 0.60). As the set of non mandatory candidates is not empty, M = {4, 6}, sub-procedure Update score and insertion position is implemented. We have F 4 = {1, 6, 7}, t 4 = 190 and F 6 = {1, 4, 7} so t 6 = 63. Time t 6 provides the minimum t M = 63, as it is lower than t M = 69. This suggests that it might be better to insert non mandatory operation m⇤ = 6 instead of m ⇤ = 7 in Pos = 3. To reflect this potential loss of opportunity, a score 6 = 1 63/69 w 0.087 is assigned to operation 6 and 6 = 3 is recorded as the corresponding insertion position. Update sequence gives S 3 = {0, 2, 7}, Obj(S 3 ) = 57, s = 7.

In position Pos = 4, the set of candidates is K := {1, 4, 6, 7} \ {7} [ F (7), that is K = {1, 4, 6, 8, 10}. The sequencing procedure proceeds by placing operation 1 in position 4 and sub-procedure Update score and insertion position provides a score 4 = 1 57/74 w 0.23 for operation 4 and 4 = 4 is recorded.

Let us note that for graph G 2 , in position Pos = 3 the set of mandatory candidates is M = {1, 4, 6, 7} instead of {1, 7} for G 1 . Focusing solely on component 4, we have (4) = {16, 18, 20} but F (4) is empty since none of the operations {16, 18, 20} can be performed even if component 4 was disassembled. Indeed, dismantling component 16 requires not only operation 4 to be performed before but also operations 6 and 9 that are not sequenced yet (the set 1 (16) \{4} = {6, 9} is not included in S 2 = {0, 2}); and the same holds for components 18 and 20.

The sequencing procedure stops when all mandatory components in M are included in the sequence, the last one being added outside of the loop for Pos = 2.. |M| 1 to avoid wrong updates of scores and positions for non mandatory operations. The first complete sequence we obtain for G 1 is S = {0, 2, 7, 1, 5, 11, 13, 3, 9, 8, 16} with a total disassembly time Obj (S) = 478 < Obj(S best ) = 776 s. Following the instructions in RGSA right after the sequencing procedure (see Table Table 3(a)), we set S best := S and we save the insertion positions of non mandatory components in best j . At the end of the first pass, the best sequence remains unchanged but scores and insertion positions have been updated several times. In RGSA updates we determine the overall best score which is attributed to component i ⇤ = 4, 4 = 0.719, with an insertion position best 4 = 6. Thus, another pass of the sequencing procedure is performed with component 4 being considered for possible insertion. Sub-procedure Update sets in the Sequencing procedure specifies that component i ⇤ = 4 will possibly be inserted in position best 4 = 6 and nowhere else, reminding its selection is probabilistic. At the end of the pass, following RGSA updates, if the best sequence has improved, operation 4 is added to the set of mandatory components M, be this operation included or not in S best . Otherwise i ⇤ = 4 is definitely excluded from further inclusion in M by setting its score 4 to an arbitrary negative value ( 4 = 1). The RGSA stops when all non mandatory components with positive scores have been assessed in this way, that is after 6 passes in our example where operations 4, 20, 6 and 18 are examined successively. Note that operation 20 is finally inserted between operations 9 and 8 during the third pass, which leads to an improvement of the objective function (Obj(S best ) = 472). Another pass with part 20 is performed but with a negative insertion position so as to prolong the search. After the third pass, we do not record any further improvement of the sequence.

It should be noted that a candidate i ⇤ for insertion in position best i ⇤ > 0 can contribute to reach a better solution as it allows for a shuffling of selection probabilities, be i ⇤ inserted or not in S best . Positions j are reset to 1 at the beginning of each pass whereas scores j keep their maximum value. Thus, it is possible that a component with the best score so far has a negative insertion position in which case the algorithm amounts to perform another pass of sequencing on an unchanged set of mandatory components. Further improvements can be reached for the search is simply prolonged over N and if so, the component will finally be included in M and excluded from M in order to create diversity. Otherwise the component will definitely stay in set M.

Positive insertion positions best j correspond to positions where the maximum scores were reached in any sequence, be this sequence the best so far or not. Thus, position best j can be negative if the best score j recorded over all previous passes is not reached in any sequence of the current pass. This approach has proved to perform better than other options we tested, such as using always a positive insertion position corresponding to the best score, or recording the best scores and corresponding positions for the best local sequence over one pass. Besides, we also unsuccessfully tried to constraint the sequencing procedure to possibly insert a component from its best position, when positive, to all subsequent positions.

Matheuristic (MH)

Starting from an initial sequence S, the matheuristic considers each pair of adjacent operations (a, b) in S and determines a subset L of components to be optimized, with a as a root node, a > 0. This list L is first made of the direct successors of all components already sequenced before b to which we add {a, b}. Second, the list involves all the direct successors of the components previously determined, that is descendants of candidates. Once L is optimized (L ⇤ ) we replace in S the subsequence in L ⇤ from a to b. In this way some operations can be inserted between a and band to update S, we delete duplicates after b. If the updated sequence is improved, we record it. Another pair (a, b) is then selected in the updated S, by setting a := b and b = s Pos (a)+1 . Optimization of subproblems stops when Pos(b) reaches the value of |S| 1.

To allow for a simple writing of the pseudocode of our matheuristic, we generalize the definition of the set of feasible successors F (k) given in Eq. ( 11). Set K keeps the same definition, thus including all candidate components to be sequenced at any iteration. Let us now define S as the set involving not only K but also the previously sequenced components at any iteration. Set F (k) is rewritten as

F (k) = j 2 (k) ; j / 2 K | 1 (j) \{k} ⇢ S . (16)
Let us note that in our RGSA, in Eq. ( 16) condition j / 2 K is never activated, and S = S Pos 1 . Table 4 displays the pseudocode of our matheuristic.

To illustrate, let us consider graph G 2 in Figure 1(a). In step MH Initialization, we choose S initial = S RGSA = {0, 2, 6, 1, 7, 10, 5, 4, 3, 9, 16}, so we set S best = S RGSA ; S = S best and Obj (S best ) = Obj (S RGSA ) = 444. We have a = 2; b = 6 , with Pos(a) = 2; Pos(b) = 3.

At the first iteration of MH, we set K = S 3 = {0, 2, 6} and S = S 3 = {0, 2, 6}. In sub-procedure Determine new feasible succ. we use Eq. ( 16) to obtain F (0) = {1} since successor 2 of node 0 is already included in K and predecessor of 1 is 0 which is already sequenced. We get F (2) = {4, 7} as (2) = {4, 6, 7} but {6} 2 K and for j = 4, 7 we have 1 (j) \{2} = {2} \{2} = ? and the empty set is necessarily included in S. Set F (6) = ? since 6 has 16 as a successor in the graph but predecessors of 16 are 4, 6 and 9 and operations 4 and 9 are not in set S.

We now set

K = S k2K F (k) [ {a, b} = F (0) [ F (2) [ F (6) [ {2, 6}
, so we have K = {1, 2, 4, 6, 7}. We thus have S = S Pos(a) 1 [ K = {0, 1, 2, 4, 6, 7}. Set K contains all components that will be re-sequenced and set S includes all operations sequenced so far and those that will be re-sequenced in the current iteration. Again, in sub-procedure Determine new feasible desc. we use Eq. ( 16) in the same way as before to obtain S k2{1,2,4,6,7} 2,3,4,5,6,7,8, 10} with 10 being the only one non mandatory component. To apply the formulation of [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF] on this subproblem, we take a = 2 as the root node and we extract from matrices

F (k) = {3, 5} [ ? [ ? [ ? [ {8, 10}. Set L of components to be optimally resequenced is therefore L = K S k2{1,2,4,6,7} F (k) that is L = {1,
1 and (t i,j ) i,j lines and rows l i 2 L. Calling for CPLEX, we get L ⇤ = {2, 7, 6, 1, 3, 4, 10, 5} which leads to S = {0, 2, 7, 6, 1, 7, 10, 5, 4, 3, 9, 16} with Obj (S) = 474, so S best is not updated.

time. Preliminary simulations showed that such "easy-to-solve" instances are related to specific combinations of parameters, like a high product structure complexity, a low number of items to disassemble or disassembly graphs with less than 50 components. In practice however, disassembly graphs have a low product structure complexity and recycling rates should be as high as possible. Thus, our simulation experiment encompasses more realistic instances for which CPLEX actually often failed to find an optimal solution, therefore emphasizing the need for heuristic solution methods. Like in [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF], our second phase considers large-sized instances (100 to 500 components) that cannot be solved to optimality. For large instances, these authors used exclusively several priority rules amongst which the Nearest Neighbor algorithm (NN) proved to be the most efficient. Therefore, along with our Randomized Greedy Sequencing Algorithm RGSA and our Matheuristic MH, we also included NN. Due to the very poor performance of NN, we tested a randomized version of that algorithm (RNN), in which the selection probability p m of each mandatory component m was set equal to exp (|M| • min j2M {t s,j } /t s,m ), with p m = 0 (non mandatory operations) and then normalized. RNN was repeated for an execution time equal to that of RGSA and the best solution was recorded. As RNN provided much better results than NN, we chose to include it as well in the first phase.

Results of the 2 phases are presented and discussed in Subsection 6.2.

Instances generation and parameters setting

Number of components. For the sake of comparison with the optimal formulation of Han et al. ( 2013) a first set of experiments was conducted with a number of components n = 50 which is the maximum number that CPLEX could handle. As in [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF], larger problems from 100 to 500 components were then considered.

Disassembly precedence graphs. We set the lowest level of each graph to the reasonable value of ⌅ (n + 1) 0.5+0.01•Rep ⌥ where Rep is the seed used for replications with Rep = 1..5. To generate disassembly graphs, we used the product structure complexity index C of [START_REF] Kimms | Multi-Level Lot-Sizing and Scheduling[END_REF], with C = 0 for complete divergent graphs in which the number of arcs equals the number of components. We have C = 1 when each component is connected to all components at lower levels. In practice disassembly graphs tend to have complexity indices close to zero because minimizing the number of connections is one of the strategies of design for disassembly. We therefore considered C = 0, C = 0.05 and C = 0.031, this positive value corresponds to the structure complexity of an electronic calculator used as a real case in [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF]. Our graph generator randomly allocates components at each level, arcs are then created one by one at random until all nodes are connected with the desired structure complexity.

Recycling rate / minimum disassembly rate. The European directive on electrical and electronic equipment wastes (WEEE) set for year 2015 a minimum recycling rate of 50% for most categories of WEEE such as small household appliances, electrical and electronic tools or medical devices. We thus considered a minimum disassembly rate ⇢ = 0.50 in all instances, leading to a number of mandatory components to be disassembled |M| = b⇢ • ne. More ⇢ values were examined for n = 50 components as we set ⇢ 2 {0.20, 0.35, 0.50, 0.65, 0.80}.

The set M of mandatory components was iteratively filled at random based upon their number of ancestors. At each iteration, the desired number of ancestors of a mandatory operation is a uniformly distributed random fraction of the maximum possible number of ancestors.

Disassembly time. Following [START_REF] Gonzalez | A scatter search approach to the optimum disassembly sequence problem[END_REF], the disassembly time t ij is defined as

t ij = t j • 1 • 2 ,
where t j is the disassembly time of component j and ✓ 1 and ✓ 2 are correction factors to account for a possible speed reduction occurring respectively when moving/rotating component j is necessary and when tool changing is required, with ✓ 1 2 {1.00, 1.15} and ✓ 2 2 {1.00, 1.10} picked at random with equal probabilities. Based on case studies [START_REF] Go | Genetically optimised disassembly sequence for automotive component reuse[END_REF][START_REF] Luo | Integrated multi-layer representation and ant colony search for product selective disassembly planning[END_REF], disassembly times t j in seconds were uniformly drawn at random in the range {10, . . . , 100} with probability 0.85 and in the range {101, . . . , 150} with complementary probability.

Parameters of the RGSA. The number of repetitions of the sequencing procedure with no improvement was set to N = 300 for all instances, whatever the number of components. Pilot studies showed that the best minimum probability ⇡ for selecting a mandatory component was equal to 0.60 for 50 components, 0.70 for 100 components, 0.80 for 200 and 300 components, and 0.85 for 400 and 500 components.

Simulation results

Medium-sized instances

In this first set of experiments with n = 50, we generated disassembly precedence graphs with a complexity C 2 {0, 0.031, 0.05} and we considered five values of the minimum disassembly rate ⇢ 2 {0.20, 0.35, 0.50, 0.65, 0.80}. Performing 5 replications for each combination of parameters led to 75 problems to solve. The MILP of [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF] was coded in C and linked with the CPLEX callable optimization library version 12.5. We run CPLEX with a time limit of 3600 s, RGSA, RNN (with same execution time as RGSA), and the Matheuristic with RGSA and RNN as initial solutions. We also applied the Nearest Neighbor algorithm (NN) but we finally excluded it from the results due to its quite poor performance (total disassembly times were about 64% higher than those of CPLEX on average). Detailed results on the 75 problems are provided in Table 8, Appendix B. Table 5 displays the average Gap/deviations and execution times over replications, for each combination of parameters values, as well as averages over all cases.

Table 5: 50 components -average results over replications

There is a clear inverse relationship between the performance of CPLEX and that of the heuristics. CPLEX reached the optimal solution only in 12 cases over 75, all of them being obtained with low disassembly rates (⇢  0.35). CPLEX gaps to optimality increase with ⇢ for the search space is augmented accordingly. However an improvement of the CPLEX solutions is always observed as the complexity index increases because more constraints of type ( 5) and ( 6) are activated, which tightens the formulation. For the lowest ⇢ value, ⇢ = 0.20, the best heuristic is MH-RNN with an average deviation of 2.58% from CPLEX and a quite low average CPU time of 7.72 s versus 2015.36 s for CPLEX. With ⇢ = 0.35, the best heuristic is again MH-RNN with an average deviation of -6.59% and a CPU time of 16.94 s, whereas CPLEX required on average 3474.56 s. When ⇢ 0.50, all heuristics outperform CPLEX. MH-RGSA becomes the best heuristic possibly because the inclusion of non mandatory components in the sequence ameliorates the performance when the disassembly rate is increased. Let us note that in all cases, MH takes longer to produce a solution when C = 0 than it does for instances with C > 0 in which subsets of components to be optimized are always smaller (some operations have more than one predecessor to be dismantled). Likewise, the performance of MH is greater when C = 0.

Large instances (from 100 to 500 components)

For large problems with n 2 {100, 200, 300, 400, 500}, we fixed ⇢ = 0.5 and C = 0.031 throughout. Performing 5 replications for each n value, we got 25 problems on which we applied RGSA, RNN and the matheuristic with RGSA as an initial solution. The rationale for this choice comes from the significantly better performance of RGSA for large problems, with an average improvement of 6.25% over RNN. For our instances with 50 components, the average improvement of RGSA over RNN was only 1.13% which made it worth to try both heuristics as initial solutions for MH. From n 300, MH-RGSA was no longer used since some subsequences to optimize included more than 50 components. We thus applied MH\D, a version of the matheuristic without considering descendants of candidates. In the pseudocode given in Table 4, MH\D simply skips sub-procedure Determine new feasible desc. RGSA was used as a benchmark since it represents the best compromise between solution quality and execution time. Detailed results for the 25 problems are given in Table 9 in Appendix B.

Table 6 displays for each heuristic and each n value the average over all replications of the deviations of solutions to RGSA as well as the average CPU. Note that the CPU for RNN is not reported since the running time of RNN was set equal to that of RGSA. The execution time of NN was negligible (2.14 • 10 4 s on average) so we did not report it. Below the deviations we also indicated in brackets the number of times RGSA was outperformed over the 5 replications. And below the CPU for MH, we give the time limit we had to set for CPLEX to avoid out of memory issues. For MH, in column "Neighb.", we provide an indicator of the neighborhood size explored by CPLEX, defined as the average of maximum number of components to be optimally sequenced, expressed in percentage of the number of mandatory components. For instance, with n = 100 and MH-RGSA, the average maximum size of components optimally sequenced in each replication is equal to 25. For n < 300, MH-RGSA is able to provide substantial improvements over RGSA but at the price of dramatic execution time increases. With a much more reasonable CPU time, MH\D-RGSA can outperform RGSA but in a limited number of cases (one case over five for each n, except for n = 300). It should be noted that when n increases, the performance of MH degrades for the explored neighborhood relative to the problem size decreases.

Finally, let us note that an additional pass of the MH did not change the results.

Conclusion

For real-world instances, the disassembly sequencing problem has been primarily solved using metaheuristics which require fine tuning to obtain good quality solutions. To the best of our knowledge this paper is the first that develops a randomized greedy heuristic and a matheuristic that are easy to implement and capable to efficiently solve medium to large scale instances. For medium-sized problems, our randomized greedy sequencing algorithm (RGSA) outperformed CPLEX whenever it was unable to reach the optimal solution, that is as soon as the minimum disassembly rate was greater than 50%. Starting from the RGSA solution, our matheuristic offered further significant improvements. From 300 components, improvements of the RGSA solution by the matheuristic MH-RGSA become less significant and execution times are pretty high but the use of MH\D is always worthwhile since it might ameliorate the solution in a quick execution time.

Possible enhancements of our solution methods include a refinement of the selection process of non mandatory components in RGSA, especially for low disassembly rates as well as exploration of other neighborhoods in the matheuristic, like picking pairs of non adjacent operations, eventually at random, between which the optimal subsequence is inserted.

In the quadratic formulation, the objective is written as

X i=0..n X j=0..n X k=1..n+1 c i,j • u i,k • u j,k+1 , (21)
subject to the same constraints as before except constraints (17) that link variables x i,j and u j,k since variables x i,j no longer exist in this formulation.

Table 7 gives the number of variables and constraints for each formulation. Although our linear formulation has less constraints than that of [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF], preliminary testing showed that both formulations were comparable in terms of execution time so we kept the existing published formulation. Even though the quadratic formulation saves a significant number of constraints, it led to very large execution times compared with the formulations.

Formulation

#Variables #Constraints [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF] 2(n + 1) 2 n 3 + 5n 2 + 8n + 5 Our linear 2(n + 1) 2 n 3 + 3n 2 + 3n + 1 Our quadratic

(n + 1) 2 + n + 1 n 2 + 2n + 1

B Tables of detailed results

Table 8 provides the results for each of the 40 instances with 50 components. There are 10 problems per minimum disassembly rates ⇢ 2 {0.20, 0.35, 0.50, 0.65}. For each ⇢ value, 5 replications are performed with the two complexity indices C 2 {0, 0.031}. For CPLEX 3600 s, we give the objective value which is the total disassembly time of the sequence, the gap to best bound in % and the CPU in seconds. For the other methods, we provide the deviation (Dev.) in % of the solution to that of CPLEX 3600s as well as the execution time in seconds.

Table 8: Detailed results for instances with 50 components Table 9 displays the results for the 25 instances with ⇢ = 0.50 and C = 0.031 throughout and n 2 {100, 200, 300, 400, 500}. The RGSA is used as a benchmark and for the matheuristics we provide in column "Size" the maximum number of components that was optimally sequenced.

Mm

  Set of mandatory components in K with M = K \ M M Set of non mandatory components in K with M = K \M and obviously we have K = M [ M t M , t M Minimum of cumulative times over mandatory candidates and non mandatory ones, respectively (t M = minm2M {tm} and t M = min m2 M {t m}) pm Probability of mandatory candidate m to be sequenced in position Pos Score of non mandatory candidate m based upon the maximum time loss associated with its non inclusion in the sequence m Position in the sequence at which the maximum m occurs best m Saving of position m each time we obtain an improved sequence S best i ⇤ Index of the non mandatory component considered for possible insertion in set M

Table 2 :

 2 Notations and definitions for the heuristic

Table 3 :

 3 Pseudocode of the RGSA and the sequencing procedure

  80, which leads to a neighborhood size of 51.60% (25.80/50).

		RGSA	NN(*)	RNN		MH-RGSA	MH\D-RGSA
	n	Obj.	CPU s	Dev. %	Dev. %	Dev. %	CPU s	Neighb. %	Dev. %	CPU s	Neighb. %
	100	1269.2	0.27	75.32	9.10	-3.02	134.84	51.60	-0.93	11.63	31.60
				(0)	(0)	(2)	(no)		(1)	(no)
	200	2339.8	0.87	52.67	9.40	-7.98	4130.42	32.60	-1.43	44.86	18.40
				(0)	(1)	(4)	(no)		(1)	(no)
	300	3078.8	1.76	44.70	8.81	-0.52	1578.87	23.60	0	35.81	13.20
				(0)	(0)	(1)	(120 s)		(0)	(no)
	400	4111.2	3.33	31.92	3.42				-0.22	68.66	11.40
				(0)	(1)				(1)	(240 s)
	500	4921.0	4.70	31.70	3.90				-0.42	86.41	9.28
				(0)	(1)				(1)	(240 s)
	(*) Han et al. (2013)

Table 6 :

 6 Results for large instances

Table 7 :

 7 Number of variables and constraints for the three formulations

Table 9 :

 9 Detailed results for large-sized instances with ⇢ = 0.50 and C = 0.031

			RGSA	NN (Han et al.)	RNN	MH-RGSA		MH\D-RGSA
	n	Rep	Obj CPU	Dev.	CPU	Dev.	CPU	Dev.	CPU Size	Dev.	CPU Size
	100	1	1407	0.34	77.68	0.00	12.22	0.34	0.00	72.69	24	0.00	1.85	17
		2	1114	0.17	43.36	0.00	10.59	0.17	0.00	78.59	25	0.00	17.08	16
		3	1001	0.38	89.81	0.00	8.39	0.38	0.00	178.30	24	0.00	14.87	15
		4	1436	0.23	64.97	0.00	3.13	0.23	-14.07	128.24	26	-4.67	5.65	15
		5	1388	0.22	100.79	0.00	11.17	0.22	-1.01	216.38	30	0.00	18.69	16
	200	1	2350	1.12	39.96	0.00	6.47	1.12	-6.98 3119.51	35	0.00	21.65	19
		2	2078	1.03	52.50	0.00	17.18	1.03	0.00 4616.25	35	0.00	44.28	22
		3	2068	0.78	46.23	0.00	6.62	0.78	-5.46 4620.41	30	0.00	13.20	18
		4	2905	0.59	66.06	0.00	-0.41	0.59	-17.31 2459.83	30	-7.13 109.06	16
		5	2298	0.85	58.62	0.00	17.15	0.85	-10.14 5836.08	33	0.00	36.10	17
	300	1	3113	2.02	34.24	0.00	5.14	2.02	0.00 1860.56	35	0.00	48.60	18
		2	3106	1.82	66.55	0.00	16.74	1.82	0.00	672.52	42	0.00	45.29	21
		3	3014	1.45	44.13	0.00	9.52	1.45	-2.59 2820.28	33	0.00	21.04	19
		4	3164	2.00	54.08	0.00	8.85	2.00	0.00 1493.69	34	0.00	34.00	20
		5	2997	1.48	24.49	0.00	3.80	1.48	0.00 1047.31	33	0.00	30.13	21
	400	1	4161	3.81	20.81	0.00	-1.92	3.81				0.00	74.88	25
		2	4205	2.83	49.23	0.00	11.03	2.83				-1.09 123.34	25
		3	3946	2.79	29.40	0.00	3.40	2.79				0.00	37.86	19
		4	4163	3.19	34.30	0.00	0.58	3.19				0.00	52.62	24
		5	4081	4.04	25.85	0.00	4.02	4.04				0.00	54.62	21
	500	1	4951	5.27	31.04	0.00	3.49	5.27				0.00	85.96	23
		2	4848	4.68	26.57	0.00	6.64	4.68				0.00	67.13	24
		3	4851	3.05	30.39	0.00	-1.44	3.05				-2.08 156.53	25
		4	4980	5.81	37.29	0.00	5.56	5.81				0.00	69.03	21
		5	4975	4.66	33.23	0.00	5.27	4.66				0.00	53.38	23

Acknowledgments

Jully Jeunet is grateful for her time as a visiting researcher at DIGEP, Politecnico di Torino, where this research has been conducted.

At the second iteration, we have S = {0, 2, 7, 6, 1, 10, 5, 4, 3, 9, 16}. We set a = 6 with Pos (a) = 4 so b = s 5 = 1. We optimize L = {6, 1, 3, 4, 5, 8, 9, 10, 11, 14} and we obtain L ⇤ = {6, 1, 3, 9, 4, 10, 5} so S is left unchanged.

At the third iteration, S = {0, 2, 7, 6, 1, 10, 5, 4, 3, 9, 16}, with a = 1 and b = 10. The subsequence that we optimize is L = {1, 3, 4, 5, 8, 9, 10, 11, 14} and we obtain L ⇤ = {1, 3, 9, 4, 10, 5}. Thus S = {0, 2, 7, 6, 1, 3, 9, 4, 10, 5, 16} and Obj (S) = 383 < 444, so we set S best = S.

The next iterations do not lead to any additional improvement. Thus, MH finally provides Obj (S best ) = 383 whereas the optimal total disassembly time is 334. However MH reaches the optimal solution for G 1 .

It should be mentioned that in our MH, we do not control the size of the subset of operations to be optimized. In the simulation experiments we present in the next section, the maximum proportions of these operations compared to mandatory components n with n 2 {50, 100, 200, 300, 400, 500} were respectively {2.80, 0.60, 0.35, 0.28, 0.125, 0.10}. For instance, in one instance with n = 50 and 10 mandatory components, the maximum size of the subset was equal to 2.8 • 10 = 28 components.

Simulation experiments

We first describe the instances and parameters setting in Subsection 6.1. The experimental design involved 2 phases. In the first phase, our incentive is to test the efficiency of our heuristics against the optimal solution provided by the MILP formulation of [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF], for disassembly graphs with 50 components.

We decided not to include the Branch and Fathoming algorithm (B&F) that [START_REF] Han | Mathematical model and solution algorithms for selective disassembly sequencing with multiple target components and sequence-dependent setups[END_REF] developed to solve instances with a maximum number of 50 components, due to its performance. For the most complex DSP the authors solved to optimality, the B&F was not always able to find the optimal solution whereas applying CPLEX to their MILP formulation provided the optimum in several seconds only on average. Our incentive is not to provide an alternative to the exact approach when CPLEX can reach the optimal solution in a reasonable computation

A Alternate formulations to the DSP

In these formulations, we define u j,k as the binary variable that takes a value of one if operation j occupies position k in the sequence. Variables z i,j no longer exist and other variables keep the same definition as in Table 1.

In the linear formulation, the objective to minimize is the same as in Eq. ( 1) subject to the following constraints.

Constraints to link variables x i,j with variables u j,k . The variable x i,j takes a value of 1 if i immediately precedes j in the sequence which means that i occupies position k (u i,k = 1) and j occupies position k+1 (u j,k+1 = 1). In all other cases x i,j must equal zero: i occupies k (u i,k = 1) and j does not occupy k + 1 (u j,k+1 = 0); i does not occupy k (u i,k = 0) and j occupies k + 1 (u j,k+1 = 1); i and j do not occupy position k and k + 1, respectively (u i,k = u j,k+1 = 0). Obviously we have x i,j = u i,k • u j,k+1 which can be linearized as follows u i,k + u j,k+1 x i,j < 2, 8i = 0..n, j = 0..n, k = 1..n.

(17)

As x i,j is in the objective function to be minimized, x i,j will take a value of zero when u i,k + u j,k+1 = 0 or 1.

Disassembly and position. If component j is not disassembled (y j = 0) then it does not occupy any position in the sequence. Conversely, if j is disassembled (y j = 1) then j occupies one and only one position in the sequence. This is written as

It should be noted that we necessarily have y 0 = 1 and node 0 occupies position 1 in the sequence thus we have u 0,1 = 1 and u 0,k = 0, 8k = 2..n + 1 and u j,1 = 0, 8j = 1..n.

Adjacency constraints between occupied positions. Since disassembly is selective, all disassembled components must occupy adjacent positions in the sequence. This means that if position k is such that P j=1..n u j,k = 0 thus all subsequent positions must not be occupied. This is written as X Precedence constraints. If j is disassembled (y j = 1) and if j occupies position k in the sequence (u j,k = 1) thus all its direct predecessors i 2 1 (j) must have been disassembled before, which is written as


Pioneer Janine Beisson

Linda Sperling
email: linda.sperling@i2bc.paris-saclay.fr

Born Janine Schecroun in French Algeria, Janine survived Nazi occupation (the family fled the Paris region to Algeria in 1940) and tuberculosis (while at University) and was doing fine dodging the current COVID pandemic until the car in which she was touring the French Alps crashed into a ravine last Sunday.

Janine returned to France in 1964 and was able to set up her own Paramecium genetics group within Rizet's laboratory at the University of Orsay, down the road from Gif. Her team moved to the Centre de Génétique Moléculaire (CGM) on the Gif CNRS campus in 1972, when she accepted the Direction of one of the three departments of the Center upon the retirement of the former department chair, Boris Ephrussi.

Janine's group used the classical genetic approach of isolation and analysis of mutants to study cytoplasmic heredity. First, mitochondrial heredity and nucleo-mitochondrial interactions in the 1970s. This fit well with the CGM's strength in yeast mitochondrial genetics, the subject of the Center's director Piotr Slonimski, who became a life-long friend. Paramecium mitochondrial genetics was however abandoned after the PhD theses of André Adoutte and Annie Sainsard-Chanet.

The team could then concentrate efforts on the study of cortical heredity. Amazing mutants were isolated on the basis of cell shape, cell size and swimming trajectory that showed defects in the morphogenesis of the cell cortex. This was possible because the cortex is covered by thousands of motile cilia arranged in a precise pattern. The cilia grow from thousands of cortical basal bodies which organize the complex cortical cytoskeleton. During the 1980s Janine's group developed methods for immunocytochemistry of the cytoskeleton as an indispensable tool to characterize the mutants, and established the chain of morphogenetic events involved in vegetative cell division, when the precise surface pattern is restored in the daughter cells after binary fission.

Although there clearly were transcellular signals that controlled the duplication or elongation of the different structures, Janine and her colleagues, PhD student then CNRS researcher Jean Cohen, research associate Françoise Ruiz, André Adoutte and colleagues in Orsay, and Maria Jerka-Dziadosz from the Nencki Institute in Warsaw, were staunch proponents of the importance of local events that relay cortical morphology. In other words, Janine considered that local molecular interactions --as opposed to long-range reaction-diffusion effects first modeled by Alan Turing --were the major determinants of pattern formation in Paramecium.

Janine began every day of her career by starting an experiment. During the years of her administrative responsibilities as Department Chair, she did not always finish the day's experiment. This changed for the better over the twenty happy years (1998-2018) she spent in the lab as Emeritus research director, freed of the tedium of administration. During this period, she had the joy of finally discovering the molecular identity of the genes behind the network of morphogenesis mutants and suppressors, most notably genes encoding known and novel tubulins (gamma-,delta-,eta-,…). She also developed, with colleagues Catherine Klotz, Luisa Madeddu, Delphine Gogendeau and France Koll, an entirely new subject involving a cortical lattice composed of centrin proteins, small calciumbinding contractile proteins ancestral to the actin/myosin based motility that prevails in multi-cellular organisms. Those beautiful studies were a fertile substrate for developing ideas about pattern formation. Janine's long career allowed her to participate in and benefit from Paramecium genome sequencing in the opening years of the 21 st century. The genome annotation revealed why it had not been possible to saturate a function of interest with mutations to achieve complete genetic dissection: the Paramecium genome was shaped by a succession of ancient whole genome duplications, and many genes are still present in two or more redundant copies.

The school of French Paramecium geneticists Janine had founded also tackled and eventually solved the long-standing mystery of non-Mendelian inheritance of Paramecium mating types. Janine followed with great interest all the steps of that adventure, from genetic studies in her laboratory in the 1970s to the recent demonstration, by Eric Meyer and colleagues in Paris, of the key role of small RNAs in mating type determination.

Janine devoted her life to research. But she also enjoyed, with her husband Georges, being a licensed airplane pilot, often flying herself to meetings or vacation spots in Europe and Northern Africa. Her literary talent made her an avid reader of English and French classic and contemporary fiction and allowed her to publish beautifully written papers and a book about Genetics in the collection "Que sais-je?".

Link to generate a list of Janine's publications using PubMed: https://pubmed.ncbi.nlm.nih.gov/?term=Beisson+J+OR+Schecroun+J+OR+BeissonSchecroun+J&sort=pubdate&sort_order=asc

Georges Rizet, first at the IBPC (


Jean-Baptiste Lebigue

Martha W Driver

Among liturgical books, the ordinal is the least understood, because it is the most difficult to characterize. Its name comes from the Latin word ordo, a generic term that can mean both the description of a ceremony and the list of texts to be read. Unlike the missal, the antiphonary or pontifical, an ordinal is not used in the celebration of a service. It does not contain the complete text of the prayers, chants or readings that the celebrant or the other clergy pronounce during the mass, the office, or for the sacrament. It is a sort of general guide to the liturgy for a particular church.

I. Exploration of an ordinal

For all the days of the year, feasts, Sundays and ferial days within the week, the ordinal gives an abbreviated list of the chants, readings and prayers, in the form of incipits:

[2]

Here is a page from an ordinal from the collegiate church of Saint-Géry in Cambrai, a city in the north of France; it is datable to the third quarter of the thirteenth century. The incipits of the liturgical texts, written in red in this manuscript, are particularly visible.

[3]

-Each article begins with an indication of the liturgical day: Feria quarta, which means Wednesday, and in this case Wednesday of Holy Week.

-Next are the details of the liturgical pieces: Invitatorium, antiphone, psalmi de feriawhich are the invitatory, antiphons and psalms for the ferial day. Since they are the same as those recited every Wednesday at Matins, it is not necessary to mention the incipits.

-On the other hand, the manuscript gives the incipits of the texts recited only on the Wednesday of Holy Week: the verse-Ne perdas cum impiis; the readings for Matins -Sacramentum dilectissimi; the three responses that must accompany the readings: Primum responsorium 'Ecce vidimus', secundum 'Una hora', tertium 'Ecce turba'.

-Then come the pieces for Lauds: the antiphon Libera me, with the psalm Miserere, and so on.

But an ordinal is not simply a list of texts. It also contains a description of the liturgical acts, such as processions, and certain unusual rites such as the Easter Vigil, the diocesan synod or the distribution of alms on certain occasions.

[4]

Here you see in the right-hand column a long passage, written in brown ink, which contains very few incipits of liturgical texts. It is the itinerary of a procession through the city of Cambrai. It begins at the hour of Prime, the moment of the washing of the feet, which took place every day during Lent.

Facto mandato

After the washing of the feet pulsatur ter campanula capituli the bell must be rung three times in the chapter house et convenient domini in choro and the canons (of Saint-Géry) assemble in the choir cum clericis et pueris. with the clergy and children.

Incipitur psalterium in choro.

The recitation of psalms begins in the choir. Quod dicendo processio pergit ad Sanctum Lazarum. While they are read, the procession advances to Saint Lazarus, puero induto alba precedente led by a child wearing an alb et ferente cruce coopertam. and carrying a veiled cross.

The procession then visits most of the churches in the city of Cambrai, before returning to the collegiate church of Saint-Géry.

[5]

A little further in the same manuscript, here is the ordo of another procession in honour of the Virgin. It took place on the Monday following Trinity Sunday, and all the major churches in Cambrai participated: the canons of the cathedral, those of the abbey of Saint-Aubert and the collegiate church of Saint-Géry. I have framed in yellow the mention of liturgical objects, such as, in the left-hand column, the reliquary in silver containing the arm of Saint Géry (brachium argenteum) and, a bit lower, a dragon holding a live rooster in its mouth (dracho tenens gallum vivum in ore suo). The names of the places and streets where the procession passed are framed in blue: for example, in the right-hand column, the name of the street: per vicum Mainsendis le Viniere.

This topographical information is particularly important for the city of Cambrai, which was partially destroyed in the sixteenth century, and then completely levelled during the First World War. Likewise, all the reliquaries mentioned on this page disappeared at the French Revolution. Passages like this are extremely interesting for historians. They help reconstruct the ground-plan and place-names of a medieval city and they are an archaeological witness to the cultural furnishings and interior disposition of the church, with its altars and its adjacent buildings: the chapter house, cloister, treasury and so on.

The ordinal also settles the problem of the convergence of several offices on the same day. For example, when a feast falls on a Sunday, one has to decide which of the two offices should be celebrated on that day. For the one that is judged secondary, should it be transferred to another date, or be the object of a simple commemoration on the given Sunday, or be completely omitted? These situations vary from year to year. The role of the ordinal is to foresee what should be done in each case.

[6]

This is an ordinal for Amiens Cathedral from the late thirteenth century. At the end of the article is the feast of Saint Nicaise, which falls on the fourteenth of December. The drafter of the ordinal needed almost an entire page in order to foresee all the possible situations. Depending upon the year, the feast of Saint Nicaise can conflict with seven other offices in the temporal, between the Thursday of the second week in Advent and the Wednesday of the third week, called Embertide Wednesday in Advent. The two first cases are not treated, because they pose no problem: the Thursday and Friday of the second week in Advent have no particular texts apart from the antiphons at the Benedictus and Magnificat. If these days fall on the fourteenth of December, their office will simply be commemorated at the end of Lauds and Vespers of the office for the feast of Saint Nicaise. The other situations are more complex and have to be dealt with one by one. For example, the office of the third Sunday in Advent cannot be displaced (this is number four in the outline). Thus, if it falls on the fourteenth of December, the feast of Saint Nicaise will be transferred to the following day. But the Vespers of Sunday evening will then conflict with the first Vespers of the feast of Saint Nicaise.

The case of Saint Nicaise is relatively simple, because it may conflict with only seven offices. Imagine all the possible combinations that can occur during the Easter cycle, where the date of the movable feasts varies over a full month! And the use of the cathedral of Amiens includes feasts for over two hundred and fifty saints, without counting the vigils and octaves!

II. Why are ordinals written in the Middle Ages?

This is one of the reasons ordinals were needed in the Middle Ages, but it is not the only one. This is the prologue for the ordinal of the abbey of Saint-Victor in Paris, composed in the first decade of the thirteenth century. It summarizes rather well the motivations that led to the making of this kind of book.

[7]

First, one had to resolve the difficulties stemming from the infinite variations in the office due to the mobility of temporal celebrations, which could easily provoke errors.

[8]

Secondly, the ordinal made up for the deficiencies in other liturgical books. The chants, prayers and readings for the mass and the office are dispersed in many books: lectionaries, homilaries, passionaries, collectars, antiphonals, missals, graduals, and so on. This prologue states that it was necessary to complete the antiphonal (ordinem antiphonarii), namely the books of chants for the office and the mass, with the texts taken from other books (alia ex aliis libris necessaria colligentes).

Furthermore, the manuscripts are not as complete as modern printed books. When a liturgical text, such as a response, is used for several offices in the year, it is copied in extenso only on its first occurrence in the manuscript. Thereafter it is sometimes recalled by an incipit, but generally it is omitted. In this case, only the ordinal allows one to know which response to use or where to find it.

[9]

Finally and most importantly, the ordinal serves to avoid conflicts within communities of canons or monks.

Congruum enim est ut usus ecclesiasticus semper uniformiter teneatur et totius altercationis molestia in posterum excludatur.

"It is indeed a good thing that the ecclesiastical usage always be observed in a uniform manner and that hereafter the inconvenience of any dispute be avoided."

All prologues insist on this point. The ordinal is not only a practical instrument. It is a normative code that has authority, approved and published at diocesan synods or general chapters. These assemblies were the occasion for clearing up liturgical problems, like the introduction of a new feast in the calendar after the canonisation of a new saint. The diocesan statutes and capitularies contain many decisions concerning the cult, treated in the same manner as legal matters.

[10] This legal aspect pertains specially to the communities of monks and regular canons, who try to maintain a unified liturgy convent to convent. In the third quarter of the twelfth century, the Cistercians, for example, composed a customary called Ecclesiastica officia, which contained many liturgical prescriptions, but not the details for the offices, as would be provided by the ordinal. You can see here the table of contents of this book.

-The temporal is underlined in red. These chapters deal with problems of scheduling and give no liturgical texts.

-The sanctoral is absent, with the exception of the Feast of the Purification (underlined in yellow).

-All the other feasts for saints are treated in the 'thematic' chapters (underlined in blue), such as De festis in quibus laboramus… "Feast days on which we work…", etc.

-Most of the liturgical questions are treated independently of the calendar. For example: Quando canitur 'Gloria in excelsis Deo' et 'Ite missa est' (When one must sing Gloria in excelsis Deo and the Ite missa est).

[11] When one looks at the content of a text, here the article for the feast of the Purification of the Virgin, it contains almost no incipits, but is limited to the details concerning the benediction of candles. Therefore you cannot confuse the Ecclesiastica officia with an ordinal.

In the second half of the twelfth century, Cistercians did not need an ordinal, because their liturgical books were copied directly on the very complete models at Cîteaux. [12] The situation changed in the course of the thirteenth century. The decisions taken by the general chapter became so numerous that the Cistercians were obliged to gather them together and write an ordinal 1 .

[13] But the liturgical legislation grew so large that, in the early fourteenth century, they had to write a new ordinal, entitled Quoniam multi, after its incipit. The prologue tells us that this is a vast synthesis integrating the material of the Ecclesiastica officia and all the statutes and definitions of the general chapter that complete or cancel them. By the end of the Middle Ages, the Cistercians are completely out of control. They copy enormous compilations that bring together the Ecclesiastica officia, the ordinal Quoniam multi, and new collections of statutes.

[14] The ordinals of secular churches show the same desire to unify and synthesize the legislation of the cult. The liturgy of the cathedral is the model for all the parish churches in the diocese. This can be shown by two ordinals from Troyes. At first glance, they look the same. Both have the title ordinarium secundum usum ecclesie Trecensis: "Ordinal for the use of the Church of Troyes". But the one on the right is an abridged version of the one on the left. All the ceremonies that take place only in the cathedral, like certain offices and solemn masses where the bishop is present, are not reproduced in the diocesan ordinal.

III. Conclusion and projects

By showing you these manuscripts, my purpose has been to demonstrate the interest of medieval ordinals, which are still so little known. You have seen that they are a mine of information for the archaeology, place names and certain aspects of daily life in the Middle Ages. But more specially, they give the measure of the power and identity of the ecclesiastical institutions with relation to one another. The fact that a collegiate church like Saint-Géry has a liturgical usage that is quite distinct from that of the cathedral of Cambrai is proof of its independence. In a very centralised order like that of the Cistercians, the particularities of the local diocese never influence the liturgy of their abbeys. On the other hand, diocesan practice has far more influence on the abbeys of Premonstratensian or Victorine canons. This permeability of local use is evidence of a lesser cohesion in these congregations. The history of religious institutions in the Middle Ages is too often limited to the study of their spirituality and their temporal power. In the eyes of their contemporaries, their identity was defined in the first place by their liturgy. This historiographical blind spot can only be filled by the study, analysis and dating of these manuscripts.

[15] This is why Olivier Legendre, Pascal Collomb and I have undertaken a catalogue of ordinals in French libraries. It will include around two hundred and fifty entries, drawn from a list of some eight hundred manuscripts compiled by Eric Palazzo. The manuscripts that are eliminated are briefly described in an on-line catalogue that you can consult on the website Telma, developed by IRHT and the École des chartes. Of course it is difficult to analyse these fascinating documents without wanting to edit one or two. The ordinal of Saint-Germain-des-Prés, composed by the abbot Guillaume Lévêque in 1395, and known from two copies at the Bibiliothèque nationale in Paris, will be published in 2010. It is a marvellous document because it gives us a graphic description of monastic life, including non liturgical details, such

as the distribution of fur-lined boots in October, or the menu for certain meals. It also contains an exceptional type of calendar, in which the hagiographic readings for Matins have precise references to seventeen books of readings used at the office, designated by the common title and the number of the text. This has permitted the identification of the collections of lives of saints, passionaries and homilaries used for the office at Saint-Germain-des-Prés at the end of the fourteenth century.

[16] In conclusion, I would like to remind you of our website, which provides an "Introduction to liturgical manuscripts", not as yet translated into English. I hope nonetheless that it will help you to become familiar with these documents, which are indeed complex, but so promising for future discoveries.

Jean-Baptiste LEBIGUE