Oussama Ben-Ammar

Alexandre Dolgui
email: alexandre.dolgui@imt-atlantique.fr

Desheng Dash Wu

Planned lead times optimization for multilevel assembly systems under uncertainties

Keywords: Multi-level assembly systems, Assemble-to-order, Assembly contracting, Stochastic lead-times, Planned lead times optimization, Stochastic modeling, Branch and Bound

Planned lead times are crucial parameters in management of supply networks that continue to be more and more extended with multiple levels of inventory of components and uncertainties. The object of this study is the problem of determining planned lead times in multi-level assembly systems with stochastic lead times of different partners of supply chains. A general probabilistic model with a recursive procedure to calculate all the necessary distributions of probability is proposed. A Branch and Bound algorithm is developed for this model to determine planned order release dates for components at the last level of a BOM which minimize the sum of inventory holding and backlogging costs. Experimental results show the behaviour of the proposed model and optimisation algorithm for different numbers of components at the last level of the BOM and for different numbers of levels and values of holding and backlogging costs. The model and algorithm can be used for assembly contracting in an assembly to order environment under lead time uncertainty.

Introduction

In today's global marketplace, planners have to take appropriate actions in response to supply disruptions [START_REF] Snyder | OR/MS models for supply chain disruptions: a review[END_REF][START_REF] Speier | Global supply chain design considerations: Mitigating product safety and security risks[END_REF][START_REF] Kleindorfer | Managing disruption risks in supply chains[END_REF] and supply uncertainty [START_REF] Flynn | On Theory in Supply Chain Uncertainty and its Implications for Supply Chain Integration[END_REF], Simangungsong et al. 2012[START_REF] Wazed | Uncertainty factors in real manufacturing environment[END_REF]. In comparison to supply-demand coordination uncertainties, Revilla and Sáenz (2013) defined disruption as random, unplanned events that stop operation either completely or partially for a certain duration. [START_REF] Snyder | OR/MS models for supply chain disruptions: a review[END_REF] specified that disruptions can often be viewed as a special case of lead time uncertainty.

In the last few years, academics and decision-makers have recognised that supply chains have become extremely vulnerable due to uncertain lead times, demand prediction and price variability. For planners, it seems difficult to improve the efficiency of the supply chain when lead times frequently have uncertain values [START_REF] Bandaly | Impact of lead time variability in supply chain risk management[END_REF]. They therefore have to manage assembly and delivery as an uncertain process.

In the Assemble-To-Order (ATO) environment, finished products are assembled only after customer orders have been received. This kind of environment enables firms to assemble on customer orders with a specific quantity and due date, and so unwanted inventory of finished products can be zero.

Despite the widespread adoption of the ATO environment, there are considerable weaknesses. Some input data are often considered as deterministic parameters, but in reality are inherently uncertain. For example, the assembly process can be interrupted by machine breakdown and components replenishment lead times may be significantly longer than planned ones. Therefore, the stock-out of one component may delay the delivery of finished products.

The literature reports many investigations into production planning that consider the randomness of the finished product demand (see [START_REF] Peidro | Quantitative models for supply chain planning under uncertainty: a review[END_REF][START_REF] Mula | Models for production planning under uncertainty: A review[END_REF][START_REF] Koh | Uncertainty under MRP-planned manufacture: review and categorization[END_REF], but few studies have examined how to cope with the uncertainty of lead times (see [START_REF] Damand | Parameterisation of the MRP method: automatic identification and extraction of properties[END_REF][START_REF] Guide | A review of techniques for buffering against uncertainty with MRP systems[END_REF]Srivasta 2000). Safety stocks have largely highlighted how to handle different uncertainties, whereas safety lead times have not been sufficiently studied. Interested readers may refer to [START_REF] Van Kampen | Safety stock or safety lead time: coping with unreliability in demand and supply[END_REF], where the cases in which the use of safety stocks and/or safety lead times could be advantageous are explained, or to Jansen and de Kok (2011) for further details on the importance of lead time anticipation. More generally, readers who are interested in supply planning models under uncertainty may turn to [START_REF] Aloulou | A bibliography of non-deterministic lotsizing models[END_REF], [START_REF] Díaz-Madroñero | A review of discrete-time optimization models for tactical production planning[END_REF], [START_REF] Dolgui | A State of the Art on Supply Planning and Inventory Control under Lead Time Uncertainty[END_REF], [START_REF] Ko | A review of soft computing applications in supply chain management[END_REF], [START_REF] Peidro | Quantitative models for supply chain planning under uncertainty: a review[END_REF], [START_REF] Mula | Models for production planning under uncertainty: A review[END_REF] and [START_REF] Koh | Uncertainty under MRP-planned manufacture: review and categorization[END_REF].

Therefore, it is necessary to examine the influence of lead times on supply planning and to develop methods that minimize costs, considering the non-deterministic behaviour of lead times.

In this study, we consider an ATO environment. The whole supply network is configured for a given tailored finished product. This product is customized according to the customers' requests and composed of a given set of personalized components.

Our problem arises at contract negotiation step. A client orders a specific product, we need to design the corresponding supply network and decide both (i) the due date for client delivery and (ii) the date when the overall process is launched at the bottom level. All partners of the supply network (local assembly units or suppliers) are independent enterprises. Thus we cannot coordinate activities inside them. But we are responsible for client delivery at the fixed due date, and we know, at the supply network design stage, the statistics on lead times of all partners. We are thus able to give to the client an estimate of the total lead time, and launch the overall process at the bottom level.

In our case, the demand of clients is not known in advance, and no stocks of finished products or components are planned to anticipate this demand. As stated in [START_REF] Berlec | Predicting order lead times[END_REF], [START_REF] Chandra | Inventory management with variable lead-time dependent procurement cost[END_REF], [START_REF] Hennet | Inventory control in a multi-supplier system[END_REF], [START_REF] Golini | Moderating the Impact of Global Sourcing on Inventories through Supply Chain Management[END_REF], [START_REF] Farhani | Competitive supply chain network design: an overview of classifications, models, solution techniques and applications[END_REF], in this case, the planners need information about the tailored product, personalized components and assembly process to negotiate the delivery time with the customer, select suppliers and plan release dates based on cost and lead times.

Obviously, the lead time are uncertain because of different factors including capacity constraints, machine breakdowns, stochastic variations on operation processing times, etc. However, at the considered stage, we know only the distributions of probability for partners' lead times (based on statistical data). Different components produced by different partners need to be assembled to obtain a finished product. So to decide the client delivery due date and the start times for supply chains, a model based on the probability distributions of the partner lead times is developed. This is a common approach in contracting and planning under uncertainty [START_REF] Song | Contract assembly: Dealing with combined supply lead time and demand quantity uncertainty[END_REF][START_REF] Fiala | Information sharing in supply chains[END_REF][START_REF] Berlec | Predicting order lead times[END_REF][START_REF] Yoo | New product development and the effect of supplier involvement[END_REF], which is commonly used owing to the complexity of the problem (Guide and Srivasta 2000[START_REF] Koh | Uncertainty under MRP-planned manufacture: review and categorization[END_REF][START_REF] Dolgui | Supply planning under uncertainties in MRP environments: A state of the art[END_REF][START_REF] Damand | Parameterisation of the MRP method: automatic identification and extraction of properties[END_REF][START_REF] Dolgui | A State of the Art on Supply Planning and Inventory Control under Lead Time Uncertainty[END_REF][START_REF] Díaz-Madroñero | A review of discrete-time optimization models for tactical production planning[END_REF].

The rest of the paper is organized as follows. Firstly, we make a short review of previous work on the optimization of assembly systems under lead time uncertainty (Section 2). A description of the problem is presented in Section 3. The analytical model is given in Section 4. In Section 5, a technique is given to reduce the initial space of research. It will be used with a Branch and Bound algorithm to optimize the mathematical expectation of the total cost (Section 6). Some results are shown in Section 7. Finally, we outline the work done in a conclusion, and give some perspectives for future research.

Related publications

An analysis of the literature shows that in the case of assembly systems, the lead time is most often considered deterministic and rarely uncertain. To handle the uncertainty of lead times, the studies found in the literature can be split into two categories: one-level and multi-level assembly systems [START_REF] Dolgui | A State of the Art on Supply Planning and Inventory Control under Lead Time Uncertainty[END_REF]. Yano (1987a) was among the first to study assembly systems with supply timing uncertainties after her studies on serial production systems [START_REF] Yano | Setting Planned Leadtimes in Serial Production Systems with Tardiness Costs[END_REF]. In Yano (1987a) only the case of the single-period model was considered. The assembly system is composed of one component at level 1 and two components at level 2. The lead times of these three components are considered stochastic. An algorithm was developed to find optimal planned lead times, which minimize holding and backlogging costs. This study has been cited 148 times and in subsequent publications, models have been limited to one or two-level assembly systems [START_REF] Chu | Supply management in assembly systems[END_REF][START_REF] Tang | The detailed coordination problem in a two-level assembly system with stochastic lead times[END_REF][START_REF] Mohebbi | The impact of component commonality in an assemble-to order environment under supply and demand uncertainty[END_REF], Hnaien et al. 2008a[START_REF] Fallah-Jamshidi | A hybrid multi-objective genetic algorithm for planning order release dates in two-level assembly systems with random lead times[END_REF][START_REF] Dolgui | A State of the Art on Supply Planning and Inventory Control under Lead Time Uncertainty[END_REF], Hnaien et al. 2016[START_REF] Borodin | Component replenishment planning for a single-level assembly system under random lead times: A chance constrained programming approach[END_REF]. [START_REF] Chu | Supply management in assembly systems[END_REF] addressed the same problem, but in the case of one-level assembly systems. The convexity of the expected total holding and backlog costs was proven, and an iterative algorithm was used to minimize it. [START_REF] Dolgui | Planification de systèmes d'assemblage avec approvisionnements aléatoires en composants[END_REF] and [START_REF] Dolgui | A model of joint control of reserves in automatic control systems of production[END_REF] developed an approach based on the coupling of an integer linear programming and a simulation to model a multi-period problem. They studied one-level assembly systems under a deterministic demand and random lead times in the case of the lot-for-lot policy. The authors considered several types of finished product. Several types of component are needed to assemble a finished product, and for each component, an inventory holding cost is considered. In this study, both the number of components to be ordered at the beginning of each period and the number of products to be assembled during each period are determined.

Ould [START_REF] Louly | Generalized newsboy model to compute the optimal planned lead times in assembly systems[END_REF], [START_REF] Dolgui | Supply planning for single-level assembly system with stochastic component delivery times and service level constraints[END_REF] and Ould Louly et al. (2008) were focused on one-level assembly systems for one product under component lead time uncertainties. The demand for the considered product was assumed to be known and fixed and the capacity was considered unlimited. A multi-period under component lead time uncertainties was considered. A generalization of the discrete Newsboy model was suggested to find optimal release dates which maximize the customer service level for the finished product and minimize the expected inventory holding cost for the components for a specific case where the distributions of probability of lead times and holding cost are the same for all components. A Branch and Bound procedure was developed to solve it for a general case of distributions of probability and costs. In [START_REF] Shojaie | A Study on MRP with Using Leads Time, Order Quality and Service Level over a Single Inventory[END_REF], the same model was studied, but for the case of POQ policy, service level constraints and over a single inventory. The authors explain that the proposed model can function with no major restriction on the type of the lead time distribution. However, a concrete example is missing in the study.

A two-level assembly system was studied by [START_REF] Tang | The detailed coordination problem in a two-level assembly system with stochastic lead times[END_REF] in the case of both stochastic lead times and the process time for components at level one of the BOM. Both the demand and the due date are assumed to be known. The capacity is considered unlimited. To determine the optimal safety lead times, which minimize the total backlogging and inventory holding cost, a Laplace transform procedure was introduced. Later, Hnaien et al. (2008a) treated only a one-period demandor a two-level assembly system and developed a genetic algorithm to minimize the total expected cost, which equal to the sum of the backlogging cost for the finished product and the inventory holding costs for components. The authors assumed that the components at level 1 of the BOM were stored and the finished product was assembled only after the given due date. [START_REF] Fallah-Jamshidi | A hybrid multi-objective genetic algorithm for planning order release dates in two-level assembly systems with random lead times[END_REF] exploit the same problem in a multi-objective context. An electromagnetism-like mechanism is proposed to reinforce the GA and to determine minimal expected costs. However, the authors focused on the number of components at the last level and neglected the influence of different costs. The case of a one-period inventory model for a one-level assembly system under stochastic demand and lead times was studied by [START_REF] Hnaien | Single-period inventory model for one-level assembly system with stochastic lead times and demand[END_REF]. A mathematical model and a Branch and Bound procedure were developed to determine optimal quantity and optimal planned lead times for components. Drawing on this work, [START_REF] Borodin | Component replenishment planning for a single-level assembly system under random lead times: A chance constrained programming approach[END_REF] proposed a joint chance constrained model and an equivalent linear formulation to solve this problem.

Recently, Atan et al. (2015) considered a parallel multi-stage process feeding of final assembly process. To determine optimal planned lead times for different stages minimizing the expected cost for a customer order, an iterative heuristic procedure was developed. It could be considered as a special case of our problem.. [START_REF] Bollapragada | Component procurement and end product assembly in an uncertain supply and demand environment[END_REF] examined a multi-product, multi-component, procurement and assembly problem under supply and demand uncertainty. A numerical example illustrates the impacts of lead times and capacity on the performance of the assembly system. However, no resolution method is provided.

To our knowledge, in the literature, there is no other multi-level model that determines optimal order release dates with several levels in the BOM, several types of components and stochastic lead times for each component at each level. The existing models are limited:

 to one-level assembly systems, continuous random lead times, real decision variables and one-off demand [START_REF] Chu | Supply management in assembly systems[END_REF],

 or to one-level assembly systems, discrete random lead times, discrete decision variables and a constant demand which is the same for all periods (Ould- Louly et al., 2008 andOuld-Louly and[START_REF] Dolgui | A State of the Art on Supply Planning and Inventory Control under Lead Time Uncertainty[END_REF],

 or to two-level systems with only one component at level 1 and two components at level 2, continuous random lead times and one period planning (Yano 1987a),

 or to two-level assembly systems and several types of components at each level (Hnaien et al., 2008a[START_REF] Fallah-Jamshidi | A hybrid multi-objective genetic algorithm for planning order release dates in two-level assembly systems with random lead times[END_REF].

In the field of project planning, [START_REF] Trietsch | Optimal feeding buffers for projects or batch supply chains by an exact generalization of the newsvendor result[END_REF] performed a study on a problem closest to our problem. It focused on the role of gates by creating safety time cushions, and optimized the later by optimizing gates. These gate times are considered as lower bounds on the actual start times of activities, and the final activity is completed at the earliest on the due date (as in [START_REF] Chu | Supply management in assembly systems[END_REF]Hnaien et al. 2008a). [START_REF] Trietsch | Optimal feeding buffers for projects or batch supply chains by an exact generalization of the newsvendor result[END_REF] considered a centralized model of a supply network. The decision-maker can decide the start times at every level. By contrast, our model was developed for the case of decentralized decisions in the supply networks where all partners are independent enterprises. Thus we cannot decide the start times at all levels. We decide only the due date for the final product and release dates for the components of last level of BOM, i.e. the dates of launching of the corresponding supply chains. The decisions which can be made with our model are useful at the assembly contracting step in ATO decentralized environments. We have selected a modeling approach based only on lead time distributions of probability for all partners. To obtain these distributions of probability, we use statistics and consider that a partner lead time starts when all components for the considered partner are available. Thus the difference from [START_REF] Trietsch | Optimal feeding buffers for projects or batch supply chains by an exact generalization of the newsvendor result[END_REF] is in the modelling approach, which is based on a different objective, and in the system studied (decentralized in our case).

Moreover, in [START_REF] Trietsch | Optimal feeding buffers for projects or batch supply chains by an exact generalization of the newsvendor result[END_REF], the duration of activities is assumed to be continuous random variables (they are discrete in our model), the costs for starting activities earlier are linear, and a linear project tardiness penalty cost is also introduced. The objective function of the proposed project-gating model is convex under gate constraints. An optimal solution is found by simulation. The author does not specify the number of simulations, the size of the studied problem, or the limits of the approach. In addition, to obtain the convexity of the cost function, specific assumptions on costs were proposed. By contrast, in our model, there is no specific assumption on costs and decision variables are discrete.

In the present paper, there is no specific assumption on costs. The supply planning and plan execution activities are decentralized and only the aspect of synchronization between partners of supply chains is considered. We cannot manage the coordination issues inside of each partner. At our decision level, we know only the distributions of probability of partner lead times. At this level of abstraction, considering the available information, all other aspects are assumed to be integrated into the probability distributions of partner lead times. This is a standard assumption made by several scholars worked in this field [START_REF] May | Applying inventory classification to a large inventory management system[END_REF][START_REF] Kuang | A Dynamic Programming Approach to Integrated Assembly Planning and Supplier Assignment with Lead Time Constraints[END_REF][START_REF] Ding | A simulation optimization methodology for supplier selection problem[END_REF][START_REF] Petrovica | Modelling and simulation of a supply chain in an uncertain environment[END_REF]. We assume that the lead time of a partner starts when all needed components are available. A partner manages its own production process considering capacity and coordination issues. But we cannot take into account these decisions because we do not know them at the considered planning stage. We have only the distributions of probability of lead times obtained by using the statistics that are also results of similar past decisions.

To summarize, the available information for us is only the probability distributions of lead times. Based on this information, we search for planned lead times for all components of last supplier level for every new customer order. In other words, taking into account the supply network design and the distributions of probability of partner lead times obtained with statistics or estimated by partners themselves, we need to define the client delivery due date and when at the latest the supply network should start all the supply chain processes.

Based on the approaches presented in the literature, this paper proposes a new generalized model to study multi-level assembly systems under lead time uncertainty in an ATO environment. To the best of our knowledge, our paper reports the first study of a model for multi-level assembly systems with stochastic lead times with the number of level greater than two. Moreover, the model and algorithm developed in this paper are different from the model and Branch and Bound procedure presented in Ould- [START_REF] Louly | Calculating safety stocks for assembly systems with random component procurement lead times: A branch and bound algorithm[END_REF] and [START_REF] Hnaien | Single-period inventory model for one-level assembly system with stochastic lead times and demand[END_REF]. The later have required specific assumptions about costs: (i) the inventory holding cost of a component is greater than the sum of unit inventory holding costs of all the individual components which make it up; and (ii) the unit inventory holding cost of the finished product is greater than the sum of unit inventory holding costs of the individual components which make it up. In our paper, these constraints are lifted.

Notation and background

To get closer to the industrial methods of planning, we consider a discrete temporal environment and integer decision variables. Fig. 1 shows that the finished product is produced from components themselves obtained from components of the next level and so on.

The assembly system is constituted by levels and components at each level ( = 1, … , ). ∑ is the number of components necessary to assemble the finished product. It is necessary to define the order release dates for components , ( = 1, … ,

) at level (the last level). No decision is possible on the start date for intermediate levels. At intermediate levels, , ( = 1, … , , = 1, … , -1) components are assembled.

Without loss of generality, we assume that the finished product demand is known and equal to one, and exactly one unit of each component is required to produce the finished product. The unit backlogging cost and the unit inventory holding cost for the finished product, and the unit inventory holding cost ℎ , for the component , are known. Note that we assume that each supplier or local assembly unit is independent. Overall, we know relatively a little about how they manage production. Nevertheless, we suppose that distribution of probability of lead time for each component and partner are available to assess lead times. They can be obtained from the statistics or estimated by partners. In the case of statistics, the time statistics automatically include not only processing times, but also additional times depending on load, capacity constraints and variations, local planning decision, etc. This is a common approach at the contracting stage to predict lead times under uncertainty. The lead times , of components are modelled as independent random discrete variables with known probability distributions and finite upper values.

Figure 1. A multi-level assembly system

For each level , when all the necessary components are available, level delivers the components to level -1 after a random discrete lead time. When a semi-finished product arrives at the final level (level 0), it undergoes the necessary final assembly operations and afterwards the finished product is delivered to the customer in order to satisfy the demand . The assembly capacity at every level is considered as infinite. It is assumed that each component of level is used to assemble only one type of component at level -1. Thus, for this model, only planned order release dates , for components , at level are unknown parameters and are the set of our decision variables. • Maximum between and the due date : = ( , )

• Minimum between and the due date :

= ( , ) • = ℎ , - ℎ , , ∈ , • = ℎ , + • = - ℎ ,

Mathematical model

We search to know when the overall processes should be launched to satisfy the demand of our customer for a due date. This model is used at the stage of contracting with our customer in an assembly to order environment. Note that for the considered problem, taking into account that all partners of supply networks are independent enterprises and the network will be managed in a decentralized manner, we search only for values of decision variables , .

From the moments , when we order components , from suppliers at the last level , and until the date when we deliver the finished product to our customer, all the processes at different levels are considered to be launched when all necessary components from previous levels are available. The assembly capacity is considered infinite. We know the distributions of probability of lead time for each level and component.. we use the infinite capacity model. There is no decision variable for internal levels (no possibility to take into account the future local decisions only the distributions of probability of lead times of our partners are known).

The production cycle extends from order release dates , of , to the delivery date ( , ) of the finished product.

Inventory holding costs are considered if components arrive before the triggering of the assembly process.

Figure 2. The composition of the total cost (the case of backlog)

Then, the total cost ( , ) is the sum of inventory holding costs for components and inventory holding or backlogging costs for the finished product. An example when the finished product is assembled after the due date is given in Fig. 2.

The proofs of the following theoretical results are in the Appendix.

Property 1.

An explicit form for the total cost is the following: The objective is to find the order release dates for components at level minimizing the expected value of the total cost ( , ). This total cost is a random discrete variable (because the lead times , and assembly dates ( , and ) are random variables, ∀ = 1, … , and ∀ = 1, … , ). Thus, we can calculate the mathematical expectation of the total cost ⟦ ( , )⟧. In Fig. 3, different mathematical expectation costs are presented.

( , ) = ℎ , - , - ℎ , , - ℎ , , + × --× ( - ) (1
From Eq. ( 1), the total expected cost, which is noted by ⟦ ( , )⟧ can be formulated:

⟦ ( , )⟧ = ℎ , ⟦ ⟧ - × , - ℎ , , - ℎ , , + × -+ × ( -⟦ ⟧) (2)
The expressions , ⟦ ⟧, ⟦ ⟧ and , are calculated and the exact expression of ⟦ ( , )⟧ is given in the Appendix.

Figure 3. Composition of the total expected cost

The intervals -, ≤ , ≤are the initial space of research. It depends on maximum and minimum lead times and the number of levels. In the next section, a technique is proposed to obtain upper limits for decisions variables.

Reducing the space of research

The main idea is to decompose the multi-level assembly system (Fig. 1) to (the number of components at level ) multi-level linear supply chains (Fig. 4). Each linear chain , ∈ {1, . . , }, delivers a finished product on a specified delivery date . There are (i) backlogging costs if the finished product is available after the due date and (ii) an inventory holding cost if it arrives before. The optimal order release date for one linear chain will be used to reduce the initial space of research for the corresponding component release date at last the level in the BOM. Therefore, it can be inferred that the total expected cost ( , ) is equal to:

( , ) = × --× -From Eq. (A.7) and Eq. (A.8) we can deduce that = + ∑ 1 -≤ and = ∑ 1 -≤ . Then, the total expected cost can be written as:

( , ) = × 1 - ≤ + × - 1 - ≤ Subsequently, let = ≤
and for each linear chain , * * be the optimal order release date which minimizes this total expected cost ( * * , ) .

, , ,

Finished Product m , , , , Finished Product j , , , , Finished Product 1 , , , , , Property 3.
The optimal order release date * * satisfies the optimality condition for the discrete Newsboy model, where the cumulative distribution function (. ) of the total lead time is used:

- * * -1 ≤ + ≤ - * * (3)
The complete proof is detailed in Appendix A.3.

Remark 1.

It is worthwhile to mention that in our case, each multi-level linear supply chain is composed of levels (successive production stages) with random processing times and without planned production dates (see [START_REF] Elhafsi | Optimal leadtimes planning in serial production systems with earliness and tardiness costs[END_REF] for the case when there are planned production date for each stage). A due date for the final product is known, and each production process starts the moment the previous one is completed. Therefore, inventory-holding costs for intermediary processes do not exist and only backlogging and inventory-holding costs of the finished product appear in expression (3).

Numerical example

To illustrate the procedure for reducing the research space, the example in Fig. 5 is studied. A three level assembly system is considered ( = 3). Two components , and , constitute the first level. The second one contains four components ( = 4) and the third one contains eight components ( = 8).

Level 2 Level 1 Finished product

The due date is equal to 15. The unit inventory holding cost of the finished product is equal to 10. The unit backlogging cost of the same product per period is fixed to 11 values: 10 , 10 , 10 , 1, 10, 10 , 10 , 10 , 10 , 10 and 10 . The unit inventory holding costs for components per period are given in the following table:

Table 2. The unit inventory holding costs for components per period

The maximum lead time of each component , is equal to 5 and each lead time varies between 1 and 5. Its probability distributions are given in the Table 3.

Initially, each order release date , varies between 0 -, and 13 ( -). The initial cardinality of research space is equal to 13 (( -+ 1) ) solutions.

The multi-level assembly system is decomposed to 8 linear chains. The cumulative distribution function of in each linear chain can be obtained. Only the first one ( , → , → , →

) is presented as follows:

F(3)=0

Table 3. The probability distributions of lead times

For the first supply chain , → , → , → the optimal release date * * depends on and and is given by the expression (3). For example for = 10 and = 10 : (2) ≤ (15 - * * -1) ≤ 10 ≤ (15 - * * ) ≤ (3). Thus, * * = 12. For = 10 : (13) ≤ (15 - * * -1) ≤ 0.999990 ≤ (15 - * * ) ≤ ( 14) and * * = 1.

Then, the value of * * it is the upper limit , for the order release date , for the component , in the assembly system. Thus, for = 10 the initial research space of possible solutions [0; 12] is the same. For = 10 , it is reduced to 0. * * , * * , … , * * are determined in the same way.

For the same example, the influence of and is studied. Table 4 andFig In the first case ( / = 10 ), the reduced space of research is equal to one. In the second case ( / = 10 ), the proposed technique to reduce the space of research decreases it by 99.99% (from 13 to 2 ). In the seventh case ( / = 1), the space of research is reduced by 90.57%. In the last one ( / = 10 ), the space of research is not reduced. This seems be logical, for a small / (the inventory holding cost for the finished product is much greater than the backlogging cost for the same product) components have to be ordered as late as possible. The research space of possible solutions can have a significant impact on the choice of resolution methods. For a high unit backlogging cost a Branch and Bound procedure can be sufficient to resolve this problem independently of the system and the number of components at the last level of the BOM.

Optimization

In this section, a Branch and Bound approach is developed. The total expected cost ⟦ ( , )⟧ mentioned in Eq. ( 2) is minimized under:

-, ≤ , ≤ * *

Branch and Bound procedure

A Branch and Bound procedure was proposed by Ould- [START_REF] Louly | Calculating safety stocks for assembly systems with random component procurement lead times: A branch and bound algorithm[END_REF] and [START_REF] Hnaien | Single-period inventory model for one-level assembly system with stochastic lead times and demand[END_REF]for an one-level assembly and a one-level production problems, respectively. Nevertheless, it is only valid if

⎩ ⎪ ⎨ ⎪ ⎧ ℎ , - ℎ , , ∈ , ≥ 0 - ℎ , ≥ 0
In other words, only if: (i) the inventory holding cost of a component is greater than the sum of unit inventory holding costs of components which make it up; and (ii) the unit inventory holding cost of the finished product is greater than the sum of unit inventory holding costs of components which make it up.

We will use the idea of such a Branch and Bound procedure, adapt it to our problem and prove upper and lower bounds as well as additional recursive properties to obtain an efficient Branch and Bound algorithm for our problem and without these restrictive assumptions about costs and system that were employed in Ould- [START_REF] Louly | Calculating safety stocks for assembly systems with random component procurement lead times: A branch and bound algorithm[END_REF] and [START_REF] Hnaien | Single-period inventory model for one-level assembly system with stochastic lead times and demand[END_REF]..

Upper bound

An upper bound ( ) is calculated by the following procedure and the algorithm is detailed in Fig. 7. It equals to the minimum between two variables and . As in section 5, the multi-level assembly system is decomposed to (the number of components at level ) multi-level linear supply chains (Fig. 3). The different Let two vectors Φ = , , … , = ( -, ; -, ; … ; -, ) and = , , … , = ( * * ; * * ; … ; * * ). We start by delaying the order release date (respectively by advancing ), the same operation is executed until the ⟦ (Φ, )⟧ does not decrease anymore. Moreover, there we do the same operations for order release date of the next component. Let = ( ,,… ,,,… , , ) a vector composed of order release dates for components , . Each decision variable is between , = -, and , = -. This horizontal dependency can easily be proven.

Lower bound

Numerical example

The proposed methods have been implemented in C++. The experiments are executed on a computer with a 2.93 GHz CPU and 4 GB of RAM. We analysed the results obtained in the example introduced above where: the number of components in the last level is equal to 8 ( = 8) and the ratio between (the unit backlogging cost of the finished product per period) and (the unit inventory holding cost for the finished product per period) is known and variable.

Levels of search tree

Table 6. Percentage of cut branches at each level of search if RSR is used (%)

In Table 5 and Fig. 11, are reported the results for the case where the Branch and Bound procedure does not use the reduced space of research (RSR). In Table 6 and Fig. 12, are given the results with RSR procedure. For a ratio / > 1, RSR reduces considerably the percentage of branches to be cut (null for / > 10 and < 3% for / = 10). Then, the efficiency of this technique decreases according to the ratio / and the percentage of branches to be cut when the RSR is considered (Table 5) and tends to the same percentage when this RSR is not used (Table 6). This finding is confirmed when / is equal to 10 .

The heuristic mentioned in Fig. 7 calculates an upper bound. This bound is equal to ( , ). Table 7 shows the gaps between the exact solution, provided by the Branch and Bound procedure, and (

) and between the exact solution and ( ). The is equal to ( , ) and for all / , it is less than 21%. We see from Table 7 that the upper bound is generally determined by when the unit backlogging cost for the finished product is more important than the unit inventory holding cost for the same product; and is determined by in other cases. It is worthwhile to mention that for this example, it seems to be possible to get optimal solutions only using both RSR and a heuristic (as the one given in Fig. 7, which calculates an upper bound) in less than 0.01 seconds. This assertion is valid only if the unit backlogging cost of the finished product is 100 times more than the unit inventory holding cost of the same product. CPU times (Table 8) vary significantly according to the ratio / . For a very large ratio, the space of research is small (see Table 4) and the vast majority of nodes in the tree are cut. When the ratio decreases, the cardinality of the reduced space of research (RSR) tends to the cardinality of the initial space of research. This explain that the CPU times required for the Branch and Bound procedure reinforced by a RSR tend to the CPU times required for the Branch and Bound procedure that used the initial space of research. In other words, reducing the space of research is not necessary when the unit inventory holding cost is much greater than the backlogging cost for the finished product. Lower limits for order release dates could possibly be developed, using properties and techniques proposed in [START_REF] Trietsch | Optimal feeding buffers for projects or batch supply chains by an exact generalization of the newsvendor result[END_REF], to further reduce the initial space of research taking into account a very small / . To understand the effect of dispersion variability on the robustness of the solution, the effect of variance is studied. The example in Fig. 5 is employed. The following parameters are unchanged: the due date , the unit inventory holding cost of the finished product, and the unit inventory holding costs for components per period. The unit backlogging cost of the finished product per period is set at 3 values: 1, 10 and 100. To consider a large variation in the variance of the lead time, we assume that the probability distributions are the same for all components: * , * = 1 = 0.245, * , * = 2 = 0.48, * , * = 3 = 0.255, * , * = 4 = 0.01 and * , * = 5 = 0.01.

In Table 9 and in Fig. 13, the effect of variance, between -200% and 200%, is studied. The evaluation of the relative solution proves that the variation of the total expected cost remains below 3% when the variance is between -100% and 100%, and below 13% when the variance is between -200% and 200%. This analysis proves that the variability of the lead time (a variance less than 200%) affects slightly the expected total cost whatever the ratio / . 9. The effect of variance on the best solution (%)

Variation of variance

Figure 13. The effect of variance of lead times on the variance of the total expected cost

In the next section, we analyse the results obtained by instances where the number of levels of the BOM tree varies between 1 and 5 levels and the ratio / varies between 10 and 10 . We note also that the number of components at the last level is fixed to eight components ( = 8).

Tests on randomly generalized examples

The influence of the ratio / has been studied for multi-level assembly systems, it varies in {10 , 10 , … , 10 }. We consider the results of 150 examples that are generated by a randomized algorithm and grouped into five families, according to the number of levels ( = 1,2, … ,5). In each family, 30 different instances are generated. The input data are due dates, the distribution function of the component lead times, unit holding costs of components, and unit backlogging and unit inventory holding costs for the finished product.

The 150 examples are generated randomly as follows:

 Each component lead time , , ∀ ∈ {1, … , 5}, ∀ ∈ 1, … , varies between 1 and 5 with discrete uniform probability distribution;  The unit inventory holding cost ℎ , , ∀ ∈ {1, … , 5}, ∀ ∈ 1, … , for component

, ranges from 1 to ∑ ;

 The unit inventory holding cost for the finished product ranges from 10 to 10 ;

 The unit backlogging cost for the finished product is calculated according to .

Table 10 shows the influence of the number of levels of the BOM and the ratio / on the cardinality of research space ( is the initial cardinality of the research space and is the average cardinality of reduced research space). We note that if the ratio decreases, tends to . 3.10 10 10 2.35 10 10 1.02 10 10 2.62 10 9 3.74 10 8 5.51 10 7 6.86 10 6 4.37 10 5

Spaces of search

Table 10. Cardinalities of the initial and reduced spaces of research

Table 11 shows the gap ( ) between the upper bound (is equal to ( , )) and the exact solution provided by the Branch and Bound procedure, only if optimal solutions are provided for all instances in the corresponding family. We note that, for each instance, an upper limit of calculation time of one hour was allowed to find optimal solutions. The value of this gap depends on both the ratio / and the number of levels . When / tends to +∞ or -∞, tends to 0. For one-level assembly systems from a ratio equal to 10, the upper bound is very often equal to the exact solution, Nevertheless, for five-level assembly systems, the ratio / has to be more than 10 to go under 0.5%.

In other words, the upper bound used in the Branch and Bound procedure has a good quality when the unit backlogging cost for the finished product is greater than the unit inventory cost for the same product.

Table 12 reports the percentage of nodes visited by the Branch and Bound procedure at the last level over the reduced space of research. For one-level assembly systems and for a ratio / equal to 100%, most of the nodes are visited. For five-level assembly systems and for a ratio equal to 10 , this percentage drops to 83.99%.

That proves the importance of the reduced space of research for the performance of the Branch and Bound procedure. On the one hand, for the unit backlogging cost of the finished product, which is much bigger than the unit inventory holding cost for the same product, the RSR reduces the cardinality of the initial space of research immensely and the few remaining nodes are then visited. In the opposite case, the RSR reached its limits but the Branch and Bound procedure seems to be effective: a great percentage of branches is cut and a small percentage of nodes is visited. To study the influence of the number of components at the last level, we tested the solution approach on a randomly generated instance set. We created 12 examples grouped into three families according to the number of levels ( = 1,2,3). The number of components at the last level varies in [10,20,30,40]. In each family, 10 test instances for each example are generated as instances defined in the first part of section 7. Only the unit backlogging cost is equal to 5 times the unit holding cost for all instances. We note that, for each instance, an upper limit of one hour on calculation time was fixed and CPU times are given only if all optimal solutions are provided for all instances in the corresponding family. For these instances, the performance of the Branch and Bound procedure decreases according to the number of components and the number of levels (Table 14). From three-assembly systems with more than 10 components, more than one hour is required to find exact solutions. Therefore, metaheuristics should be developed to generate good quality approximate solutions for larger instances.

Conclusion and perspectives

The paper deals with the modelling and optimization of multi-level assembly systems under uncertainty of components lead times. We have proposed a one-period planning model with infinite assembly capacity at all levels and for a known demand. The model calculates the mathematical expectation of the total cost composed of inventory holding costs for components at all levels and for the finished product and a backlogging cost for the finished product. The proposed lower and upper bounds and recursive function which expresses the dependence among levels, enabled us to study assembly systems with more than two levels and thus extend the results of (Yano 1987a[START_REF] Chu | Supply management in assembly systems[END_REF][START_REF] Tang | The detailed coordination problem in a two-level assembly system with stochastic lead times[END_REF], Hnaien et al. 2008a[START_REF] Fallah-Jamshidi | A hybrid multi-objective genetic algorithm for planning order release dates in two-level assembly systems with random lead times[END_REF], Hnaien et al. 2016[START_REF] Borodin | Component replenishment planning for a single-level assembly system under random lead times: A chance constrained programming approach[END_REF]. Specific techniques were introduced to reduce the initial cardinality of research space, they considerably decreases the percentage of branches to be pruned. In particular, an original technique, based on the Newsboy model, was developed to reduce the initial space of research. In addition, bounds were developed and a Branch and Bound procedure was suggested to determine planned lead times when the component lead times are independent and identically distributed discrete random variables.

The proposed model and optimisation algorithm were developed to furnish a help to decision maker at the assembly contract negotiation with a customer in an ATO environment under a complex multi-level structure of supply network and uncertain partner lead times. They help the decision makers to define a due date for the finished product delivery and release dates for the components of last level of BOM.

The numerical results analyse the influences of the number of levels of the BOM, the number of components in each level, and backlogging and the inventory holding costs for the finished product. The efficiency of the proposed algorithm does not depend only on the number of components in the last level, but also on other parameters, such as finished product backlogging and holding costs and the number of levels. The proposed method is efficient for solving small and medium-sized problems, and its performance increases if, the backlogging cost greatly exceeds the inventory cost for the finished product.

Our approach is based on a one-period inventory model: for a given demand and due date, the optimization is done to determine optimal order release dates. This approach can be applied not only at the contract negotiation stage for Assembly-to-Order systems under lead time uncertainty when distributions of probability of lead times are available. For the multi-period inventory model, for example for MRP parameterization, it can be used to obtain approximate values of planned lead time parameters for MRP tables. The recursive functions developed and proved in this paper can be also used to generalize different known models, for example, those proposed by Ould [START_REF] Louly | Generalized newsboy model to compute the optimal planned lead times in assembly systems[END_REF], [START_REF] Dolgui | Supply planning for single-level assembly system with stochastic component delivery times and service level constraints[END_REF] and [START_REF] Shojaie | A Study on MRP with Using Leads Time, Order Quality and Service Level over a Single Inventory[END_REF], for multi-period models of one-level assembly systems under lead time uncertainty. The uncertainty of the demand can be also integrated as in [START_REF] Song | Contract assembly: Dealing with combined supply lead time and demand quantity uncertainty[END_REF].

The contributions of our study are to be seen in the light of the state-of-the-art results, because similar problems have already been studied in the management science literature. Our model is based on existing work, and we have proved that our model is more general, and that our method outperforms the existing ones.

From a practitioner's point of view, the interest in our approach lies in the fact that it can be used in many industrial situations, because there is no assumption on cost functions and distributions of probability of lead times. For example, we worked with ZF in France (Saint-Étienne), a German company that manufactures gearboxes. ZF classifies suppliers according to the statistics, and a safety coefficient is determined for each supplier to set the corresponding planned lead times in their MRP system. This coefficient is multiplied by the contractual lead time to obtain the planned one. This enables the company to anticipate delays by estimating the reliability of suppliers. In other words, the less reliable a supplier, the higher its coefficient. However, suppliers were considered independently, and coefficients were empirical. The synchronization aspects and costs were not taken into account. From the outcome of our investigation it is now possible to use our model to better estimate these coefficients by considering inventory and backlogging costs, the independence (synchronization) of suppliers via the assembly operations, and distributions of probability for supplier lead times.

It is clear that if some assumptions of our model are not respected, the solution obtained will therefore be approximate and not optimal. However, in real applications (with complex structures), decision makers often do not seek optimal solutions; approximate ones may be satisfactory if they propose good quality decisions.

Our future work will focus on the coupling of the analytical method with a genetic algorithm. The Branch and Bound procedure seems to be limited to small and medium sized problems.

To study assembly systems with many more components and levels, metaheuristics are necessary. A second objective is to extend this model and different proposed techniques to study coordination between parameters of different replenishment calculation tables in a complex MRP system, and in particular to calculate parameters of planned lead times for multi-level multi-period case. The main difficulty will be to express the total expected cost for multi-period planning of assembly systems.

  Note the following notations: Parameters Due date for the finished product, > 0 Demand (known) for the finished product at the date , without loss of generality, let = 1 Level in the bill of material (BOM), = 1, … ,,

Figure 4 .

 4 Figure 4. Decomposition of the assembly system to several multi-level linear chains

Figure

  Figure 5. A three-level assembly system

  . 6 present the upper limits , of the reduced research space of possible solutions according to the backlogging and inventory holding costs of the finished product.

Figure

  Figure 6. Upper limits

Figure 7 .

 7 Figure 7. Calculation of the upper bound

  to the costs of linear chains. So, the first ,

..

  Nodes in the first level of the search tree correspond to different release dates of the first component , at level . Vectors associated with these nodes are defined as follows: ∀ ∈ 0; , , It will be noted , = , + . The first value , + corresponds to the order release date of the first component , and the other values , correspond to the order release dates of the other components , , = 2, … , , … , . The search tree nodes are illustrated in Fig.8.

Figure 10 .

 10 Figure 10. Horizontal dependencies between nodes.

Figure 12 .

 12 Figure 12. Percentage of cut branches at each level of search if RSR is used (%)

Table 4 . Upper limits of the space of research

 4

	1,E+04
	1,E+03
	1,E+02
	1,E+01
	1,E+00
	0.1
	0.01
	0.001
	1,E-04

Table 5 . Percentage of cut branches at each level of search if RSR is not used

 5

		1	2	3	4	5	6	7
		91.67 96.00 96.00 88.00 94.12 94.12 84.62
		75.00 88.24 86.67 80.95 92.52 92.52 74.13
		66.67 78.13 71.65 62.59 92.33 82.30 65.71
		50.00 70.00 62.26 47.02 92.32 63.37 49.58
		41.67 54.37 46.23 30.39 84.00 58.45 39.88
		25.00 38.76 30.80 14.91 74.41 49.67 29.25
		8.33 38.06 26.98 37.90 79.58 51.90 30.67
	.	0.00 30.36 27.27 78.56 80.53 55.96 32.88
		0.00 27.38 24.41 84.13 78.00 54.34 30.27
		0.00 27.38 23.78 84.82 77.41 54.12 29.50
		0.00 27.38 23.78 84.82 77.39 54.21 29.43

Table 7 . The gap between the exact solution provided by the Branch and Bound procedure and the upper bound (%)

 7

	/

Table 8 . CPU times (seconds)

 8

	/

Table 11 . The gap between the exact solution and the upper bound (%)

 11

Table 12 . The percentage of nodes visited by the Branch and Bound algorithm (%)

 12 In Table13, the average time in which the algorithm finds the exact solution is presented. It depends on the number of levels and the ratio / . For one level assembly systems, exact solutions are found in less than one second. For the five-level systems and for a / less than 10 , more than one hour is required to solve the problem. Finally, the CPU times do not depend only on the number of components in the last level , but on other parameters as different costs and the number of levels.

	/
	1	10

Table 13 . Average CPU times

 13

Table 14 . Average CPU times for B&B

 14

Acknowledgements: This work is partially supported by Chinese Academy of Science Visiting Professorship for Senior International Scientists, grant number 2013T2J0054, the Ministry of Science and Technology of China under Grant 2016YFC0503606, by NSFC under grant number 71471055 and 91546102.

Let the vector



, are fixed and belong to , ;

,

 ∀ ∈ [ + 1; ], , are fixed and equal to ,

We introduce the following additional notations:

 The component , is necessary to assemble the component , , it is the component in the search tree.

 is defined as follows :

(7)

 If , is the last component necessary to assemble , then is equal to .

 If

, is not the last component necessary to assemble , so is equal to the sum of the number of components necessary to assemble the components , ∀ ∈ [1;

] from ( -1) level of the BOM. . We note that if = , = .

• , ∀ ; , , :

The assembly date of the component , . Components in the last level of the BOM of the assembly subsystem of , have order release dates , equal to or greater than , .

:

The maximum between and with the assembly date of the finished product. The order release dates , belong to the search intervals , ; , with , = -, and , = -.

The maximum between and with the assembly date of the finished product. The order release dates , are detailed in expressions (4), ( 5) and ( 6).

Proposition 4.

The lower bound corresponding to the vector , , is equal to:

The complete proof of the previous lower bound is detailed in Appendix A.4. Please also note that a depth-first search, a reduced space of research and other strategies based on vertical and horizontal dependencies between nodes are used to reduce the search complexity.

Vertical dependencies

Each lower bound is cut into three parts. This technique has already been used to calculate a lower bound for the Knapsack problem [START_REF] Kellerer | Knapsack Problems[END_REF][START_REF] Martello | Knapsack problems: algorithms and computer implementations[END_REF][START_REF] Martello | Knapsack problems: algorithms and computer implementations[END_REF]. The idea is not to redo some calculations where we explore in the depth. Let a node . To determine the lower bound ( ) related to this node, a part ( ) is calculated every time, another part ( ) is recovered from the parent node and a last part is calculated and is added to ( ) ; it constitutes the fixed part related to this node and to be used by son nodes. An illustration is given in Fig. 9.

Figure 9. Vertical dependencies between nodes.

Then, the lower bound ( ) is equal to the sum of ( ), ( ) and ( ) with:

It can be easily proven by devising the upper bound of a given node according to the upper bound of a son node.

Horizontal dependencies

As with vertical dependencies, it is easy to prove that a given node can be composed of fixed and varied parts. We note that is the quantity which is calculated and added to ( ) to determine ( + 1). So, ( + 1) = ( + 1) + ( ) + ( + 1) with:

• ( + 1) = -ℎ , In the first case, the gap between the upper bound (the minimum between and ) and the exact solution is null. The Branch and Bound procedure is not required to find the optimal solution that is determined directly from the reduced space of research (0, 0, 0, 0, 0, 0, 0, 0).

Figure 11. Percentage of cut branches at each level of search if RSR is not used (%)

/

Levels of search tree

Appendix A. Proofs of the theoretical results

A.1. Proof of Property 1

The total cost is the sum of:  Inventory holding or backlogging costs for the finished product. There will be a stockout of the finished product if, at least, one type of component at level 1 is delivered after the due date . Then the backlogging cost is equal to:

If all components , ∀ = 1, … , , are available before , the finished product may be assembled and stored. The corresponding inventory holding cost is equal to:

 Inventory holding cost for components. There are inventory for components

, during the time period between its arrivals at , + , and the assembly date for the finished product. The corresponding inventory holding cost is equal to:

There are inventory for components , , = 2, … , -1, , ∈ , , during the time period between their arrival at , + , and , the assembly date of the component , . The corresponding holding cost The components , at the last level are ordered at the date , and are delivered at the date , + , . The assembly of the components , begins when all necessary components , ∈ , are available, i.e. at the date , . The corresponding components holding cost is equal to:

Then, the total cost is the sum of , , ,

,…, and .

A.2. Proof of Property 2

To calculate the mathematical expectation of the total cost ⟦ ( , )⟧, we calculate , ⟦ ⟧, ⟦ ⟧ and , .

Let the following recursive function ; it allows the expression of the dependence among levels:

≥ Let a positive random discrete variable with a finished number of possible values. Its expected value is equal to:

This expression (A.6) is used to calculate , ⟦ ⟧, ⟦ ⟧ and , .

Knowing that:

And that ∀ = 1, … , , the random variables , + , are independents, so:

is calculated in the same way. By introducing the recursive function, we can easily deduce that ⟦ ≤ ⟧ = , , , 1 .

Then:

We note that ⟦ ⟧ is calculated in the same way and is equal to:

The expression of ⟦ ⟧ is calculated using expressions (A.7) and (A.8) and is equal to:

The assembly dates , are positive random discrete variables with a finished number of possible values:

Knowing that:

And ∀ = 1, … , and ∀ = 1, … , -2, the random variables , + , are independents, so:

The recursive function , , , is called each time when it is necessary to determine the probability related to , . The expression of , can be written as follows:

Then, using expressions (A.7, A.8, A.9 and A.10), the total expected cost mentioned in expression (2) can be directly found. It is given by the next expression:

A.3. Proof of Property 3

The expression (3) can also be deduced from expression (11) in Hnaien et al. (2008b) by replacing ℎ by . * * can be an upper limit for , of the component , from the multilevel assembly system and the initial research space of possible solutions -, ;can be reduced to -, ; * * . For this, let us suppose that the vector * = , * , … , , *

, which is composed of order release dates, minimizes ⟦ ( * , )⟧. ∀( , ) ∈ [1;

] , this vector is defined as follows: The optimal solution * * has to satisfy, otherwise a neighbouring solution better than * * exists:

- * * -1 ≤ 0 Then, expression (3) can be proven. Therefore, to say that all order release dates are between -, and * * , we have to prove that ( * , * ) ≥ 0.

with:

Then after some algebraic transformations, we obtain: According to the expression (3), ∀ -≤ < :

We finally deduce that ( * , * ) ≥ 0. ∎

A.4. Proof of Proposition 4

The Lower bound corresponded to the vector whose values are defined in expressions (4), ( 5) and ( 6):