Efficient replenishment planning is a very important problem in Supply chain management. A poor inventory control policy leads to overstocking or stockout situations. In the former, the generated inventories are expensive and in the later there are shortages and penalties due to unsatisfied customer demands.
Material Requirements Planning (MRP) is a commonly accepted approach for replenishment planning in major companies (Axsäter, 2006). The MRP software tools are accepted readily, the majority of industrial decision makers are familiar with them through all the existing production control system software. MRP software has a well developed information system and has been proven over time.
However, MRP is based on the supposition that the demand and lead times are known. This premise of deterministic environment seems somewhat off base since most production occurs stochastically. Component and semi-finished product lead times and finished product demands are rarely forecasted reliably. This is because there are some random factors such as machine breakdowns, transport delays, customer demand variations, etc. Therefore, in real life, the deterministic assumptions embedded in MRP are often too limited.
Fortunately, the MRP approach can be adapted for replenishment planning under uncertainties by searching optimal values for its parameters. This problem is called MRP parameterization under uncertainties.
The planned lead times are parameters of MRP. For the case of random lead times, the planned lead times are calculated as the sum of the forecasted and safety lead times. These safety times are obtained as a trade-off between overstocking and stockout while minimizing the total cost. The search for optimal values of safety lead times, and, consequently, for planned lead times, is a crucial and challenging issue in Supply chain management with MRP approach.
In this chapter, we present a methodology for optimal calculation of planned lead times in the MRP approach. This methodology was developed in our previous works (Dolgui et al., 1995; Dolgui, 2001; Dolgui & Louly, 2002; Louly & Dolgui, 2002; Louly & Dolgui, 2004, Louly et al., 2007) for supply chains with random lead times where holding and backlogging costs are not negligible.
2. Inventory control in supply chains
Supply chain management is a collection of functional activities that are repeated many times throughout the process through which raw materials are transformed into finished products (Ballou, 1999). An illustration of a Supply chain is given in Fig. 1.
As reported in number of papers, various sources of lead time uncertainties may exist along this chain. To avoid these uncertainties, the companies use safety stocks (safety lead times), which are rather expensive. Therefore, it is desirable to develop special methods of supply planning which focus on the stochastic properties of lead times (Maloni & Benton, 1997).
Supply management in industrial applications is mainly based on Material Requirements Planning (MRP), which provides a framework for inventory control. In the MRP approach, an important distinction is drawn between demand for the end product, i.e. independent demand, and demand for one of its items, i.e. dependent demand (Baker, 1993). The independent demands are known or forecasted by the methods which are developed in the framework of "sales forecasting". The dependent demands can be calculated from the independent ones by using Bill of Material and planned lead times.
Under MRP logic, time is viewed in discrete intervals called time buckets. The lead time is equal to the elapsed time buckets from the order release date to the delivery (procurement, production, etc.) of the corresponding item. The lot size is the quantity of items to be ordered.
The MRP method is based on the deterministic calculation: all the orders of items are released at the latest possible moment, so total cost will automatically be minimal. But, if random factors exist, the meaning of "at the latest possible moment" is uncertain. In this case, for each specific value of MRP parameters (concretely: planned lead times) we can have a backlog or overstock probability. The larger the probability of backlog is, the bigger the average backlogging cost over time. The same is true for overstock, the larger the probability of overstock is, the greater the holding cost. Therefore, a challenging problem is MRP parameterization, in particular, the choice of optimal values for planned lead times.
3. Related works
Yeung et al. (1998) propose a review on parameters having an impact on the effectiveness of MRP systems under stochastic environments. Yücesan & De Groote (2000) did a survey on supply planning under uncertainties, but they focused on the impact of the production management under uncertainty on the lead times by observing the service level. Process uncertainties are considered in (Koh et al., 2002; Koh & Saad, 2003).
The problem of MRP parameterization under lead time uncertainties has been often studied via simulation. For example the study of Whybark & Williams (1976) suggests that a safety lead time’s mechanism may perform better than that of a safety stock in a multi-level production-inventory system when the production and replenishment times are stochastic. Nevertheless, Grasso & Taylor (1984) reached another conclusion and prefer safety stocks for both quantity and lead-time uncertainties. Weeks (1981) developed a single-stage model with tardiness and holding costs in which the processing time is stochastic and demand is deterministic. The author proves that this is equivalent to the standard “Newsboy” problem. Gupta & Brennan (1995) show that lead time uncertainty has a large influence on the total inventory management cost. Ho & Ireland (1998) illustrate that lead time uncertainty affects stability of a MRP system no matter what lot-sizing method used or demand forecast error obtained. The statistics from simulations by Bragg et al. (1999) demonstrate that the lead times influence the inventories substantially. Molinder (1997) study the problem of planned lead times (safety lead time/safety stock) calculation via simulation and proposes a simulated annealing algorithm to find appropriate safety stocks and/or safety lead times. The simulations show that the overestimated planned lead times is conducive to excessive inventory, and underestimated planned lead times introduce shortages and delays. (Grubbström, & Tang, 1999) study optimal safety stocks in single and multi-level MRP systems, assuming the time interval of end item demand to be stochastic.
For serial multilevel production systems, i.e. where the previous level supplies the next and only one supplier is at each level, Yano (1987a,b) suggests an approach to determine optimal planned lead times for MRP. In this study, the lead times are stochastic, and finished product demand is fixed. The author presents a general procedure for two stage systems based on a single-period continuous inventory control model. The objective was to minimize the sum of inventory holding costs, rescheduling costs arising from tardiness at intermediate stages, and backlogging cost for the finished product. One of the main obstacles for this approach consists in the difficulties to express the objective function in a closed form for more than two stages.
In assembly systems there are several suppliers at each stage, and so, there is dependence among the different component inventories at the same stage. Yano (1987c) considers a particular problem for two-level assembly systems with only two types of components at stage 2 and one type of components at stage 1. The delivery times for the three components are stochastic continuous variables. The problem is to find the planned lead times for MRP minimizing the sum of holding and tardiness costs. A single period model and an optimization algorithm were developed. Tang & Grubbström (2003) consider a two component assembly system with stochastic lead times for components and fixed finished product demand. This study is similar to (Yano, 1987c). However, here, the process time at level 1 is also assumed to be stochastic, the due date is known and the optimal planned lead times are smaller than the due date. The objective is to minimize the total stockout and inventory holding costs. The Laplace transform procedure is used to capture the stochastic properties of lead times. The optimal safety lead times, which are the difference between planned and expected lead times are derived.
Another interesting single period model was proposed in (Chu et al., 1993) which deals with a punctual fixed demand for a single finished product. The model gives optimal values of the component planned lead times for such a one-level assembly system with random component procurement times.
Wilhelm & Som (1998) studied a two-component assembly system using queuening models and showed that a renewal process can be used to describe the end-item inventory level evolution. The optimization of several component stocks is replaced by the optimization of finished product stock. To perform this replacement, a simplified supply policy for component ordering was introduced. Another multi-period model is proposed in (Gurnani et al., 1996) for assembly systems with two types of components and the lead time probability distributions are limited to two periods. In (Dolgui & Louly, 2002; Louly & Dolgui, 2004), a similar one-level planning problem with random lead times and fixed demand is studied, but for a dynamic multi-period case. The authors give a novel mathematical formulation and propose a generalized Newsboy model which gives the optimal solution under the assumption that the lead times of the different types of components follows the same distribution probability, and the unit holding costs are identical. In Louly et al. (2007) the authors generalize their studies of 2002 and 2004. They present a more universal case, when the unit holding costs aren’t the same for all components and the component lead times are not i.i.d. random variables.
4. MRP approach
4.1. The basic principles of MRP systems
The goal of MRP is to determine a replenishment schedule for a given time horizon. For example, let’s consider the following bill of materials - BOM (see Fig. 2) for a finished product. The needs for the finished product are given by the Master Production Schedule – MPS (Fig. 3), and those for the components are deduced from BOM explosion (Dolgui et al., 2005).
Let’s introduce the following notation:inventory for the period net needs for the period gross needs for the period released orders for the period planned lead time.
The available inventory for the period 1 is given. For each subsequent need, the value is calculated from the net needs of the previous period:
net needs of the period are obtained as follows:
The released order quantity:
4.2. MRP under uncertainties
The demand uncertainty means that the demand isn’t exactly known in advance and, so the planned quantities for a period may be different from the actual demand. The lead time uncertainty means that the actual lead time may be different from planned lead time, so an order planned for a period may not arrive at the appropriate date.
As aforementioned, in literature, the majority of publications are devoted to the MRP parameterization under customer demand uncertainties. As to random lead times, the number of publications is modest in spite of their significant importance. The motivation of this chapter is to contribute to the development of new efficient methods for MRP parameterization under lead time uncertainties (see Fig. 5).
The core of this approach is the calculation of planned (safety) lead times. When we increase these parameters, the stocks increase also. However, stocks are expensive. In contrast, if the planned lead times are underestimated, the risk of stockout and consequently the backlogging cost increases along with decreasing the service level. The goal is to find the planned lead time values which provide a trade-off between holding and backlogging costs while minimizing the total cost under random actual lead times. In the next section, we suggest a mathematical model for this optimization.
5. MRP parameterization
5.1. Mathematical model description
In the MRP approach, replenishment order dates, i.e. release dates, for each component are calculated for a series of discrete time intervals (time buckets) based on the demand and taking into account a fixed planned lead time: the release date is equal to the due date minus the planned lead time. For the case of random actual lead times, in industry, a supply reliability coefficient ( 1) is assigned to each supplier. The planned lead times for MRP are calculated by multiplying the contractual lead time by the corresponding supplier reliability coefficient. The choice of these coefficients (which give safety lead times) is based on past experience. However, this approach is subjective and can be non optimal if we need to minimize the total cost for an MRP system. The supplier reliability coefficients (safety lead times and so planned lead times) can be calculated more precisely taking into account inventory holding and backlogging costs, with a inventory control model. Such an inventory control model must be simple (to be solvable), but representative, integrating all major factors influencing the planned lead time calculation.
For component planned lead time calculation for assembly systems with several types of components and random component lead times, we have introduced (Dolgui & Louly, 2002) the following model and assumptions. This model will help us to solve the considered problem of MRP parameterization, i.e. to find optimal planned lead times for components when the actual lead times are random variables. Fig. 6 gives an illustration of the suggested abstract model.
For this model, we assume that the finished product demand per period is known and constant as well as the assembly capacity is infinite. Several types of components are needed to assembly one finished product. The unit holding cost per period for each type of component and the unit backlogging cost for the finished product are known. The lead times for orders made at different periods for the same type of component are independent and identically distributed discrete random variables. The distribution of probabilities for the different types of components can be not identical. These distributions are known, and their upper values are finite.
The finished products are delivered at the end of each period and unsatisfied demands are backordered and have to be treated later (when sufficient numbers of components of each type are in stock). The supply policy for components is Lot for Lot: one lot of each type of component is ordered at the beginning of each period.
Because the supply policy is the Lot for Lot and the demand is considered as constant, the same quantities of components are ordered at the beginning of each period. Thus, only planned lead times are unknown parameters for this model. Hence, they are the decision variables in our optimisation approach. The model considers random component lead times and also the dependence among inventories of the different components suitable for assembly systems (when there is a stockout of only one component, consequently, there is no possibility to assemble the finished product).
To simplify the equations, without lost of generality, we assume that the finished product demand is equal to one unit per period, and that one finished product is assembled from one unit of each type of component.
Let’s use the following model notations:function equal to 1 if f is true, and 0 otherwise, number of types of components used for the assembly of one product, mathematical expectation operator, unit holding cost for the component per period, unit backlogging cost for the finished product per period, reference of a period (period index), lead time of the components (discrete random variable), lead time of the components ordered at period (discrete random variable), upper value of the lead time for components ( ; ); number of orders for the component that have not yet arrived at the end of the period steady state number of orders for the component that have not yet arrived at the end of a period, vector of the decision variables function equal to the maximum of and 0: .
Considering that the component ordered quantities are the same for all periods, the planned lead time multiplied by the ordered quantity, which is equal to the finished product demand, gives also the initial inventory for the corresponding component.
The optimal planned lead times do not depend on the finished product demand (the same values of optimal planned lead times will be obtained for different demand amounts, if the demand is constant and other characteristics of the problem are fixed).
Given the fact that the order quantities are constant, i.e. the same for all periods, the crossing of orders does not complicate the problem.
Taking into consideration the objective of this study – to calculate optimal planned lead times for MRP controlled assembly systems under lead time uncertainties - the assumptions on the fixed demand and infinite assembly capacity are necessary and natural simplifications.
Taking into account the assumptions on the constant demand and infinite capacity of the assembly system, we are in a Just in Time (JIT) environment, i.e. there is no stocking of finished products.
Considering that the component lead times cannot exceed the random variables and can have only the following values: 0, 1, 2, …,
The orders are given at the beginning of each period and delivered components are used at the ends of periods (so an order made at period k can be used at the end of the same period k, if the actual lead time is equal to 1).
Let’s introduce the following additional notations:are decision variables, the value signifies that the component is ordered at the beginning of the target period (i.e. when assembly must be made),
As shown in (Louly et al., 2007), the objective function and constraints for this multi-period model for the optimization of planned lead –times can be formulated as follows:
The maximal value of component lead time is equal to so only the previous -1 orders may not yet be received. Earlier orders have already arrived, therefore:
whereis s-th variable (these variables are iid).
The main difficulty of the optimization problems (4)–(5) is that the decision variables, are integers and the objective function is non linear. Thus, this is a complex optimization problem.
5.2. Optimization algorithm
For the problem (4) – (5), we propose the approach illustrated in Fig. 7. From practical point of view, an approximate solution of this problem can be sufficient. So we developed several techniques to calculate lower and upper limits for the value of decision variables. By applying these techniques we reduce the space of admissible values for these variables. Often, the obtained space is relatively small, so an approximate solution is relatively easy to find.
The proposed techniques for reduction of the space of admissible values for decision variables are also useful as a pre-processing procedure for an exact optimization algorithm (Branch and Bound in our case). The smaller the search space for the exact procedure is, the quicker the solution can be found.
Pre-processing procedure to reduce search space.
We propose a pre-processing procedure which should be used before optimisation.
Let’s present the space of all feasible solutions by [A, B], where A= ( ,…, ), B = ( , , …, ), where , are minimal and maximal possible values for . We will show some techniques that reduce these intervals: , .
We proved (Louly et al., 2007) that the optimal solution X= ( ,…, ) satisfies the following conditions:
Therefore, the maximum value of which satisfies the condition (8) gives a upper limit and the minimum value of which satisfies the condition (7) gives a lower limit for this decision variable . Then, the optimal value of must respect the following relation: ≤ ≤
The pre-processing procedure based on the verification of the conditions (7) and (8) can reduce the search space before applying any optimisation algorithm.
We use a Branch & Bound approach to find the optimal values of the parameters .
It is known that dominance properties can improve a Branch & Bound algorithm.
In our previous works, we have introduced the following partial increment functions:
The following two dominance properties (i) and (ii) were proved in (Louly & Dolgui, 2007):
These dominance properties can be used to develop efficient cut procedures. Indeed, after the division of a node, in a Branch and Bound algorithm, two son-nodes (descendants) are created. For each son-node, some cuts can be applied to reduce again the corresponding search spaces before the next branching.
Lower bounds on the objective function.
Since, we use a Branch and Bound algorithm to solve the optimization problem (4) – (5), we need efficient Lower bounds for each tree node and root. In this sub-section, we develop these bounds.
In (Louly et al., 2007), we have the two following Lower Bounds on the objective function in the space [A, B]:
The parameter is the largest integer which verifies the following expression:
The following lower bound will be used in the Branch and Bound:
Node extension procedure.
A Branch and Bound (B&B) algorithm is based on the design of an enumeration tree. In our algorithm, each node of the enumeration tree represents a set of feasible solutions. Let [A, B] be a node of this tree. The descendants of this node are obtained by dividing (partitioning) the corresponding space [A, B] into two smaller subspaces [A, B1] and [A1, B] as follows:
- we choose i such that i = arg max (b i -a i )
- then, the descendent [A, B1] (respectively [A1, B]) is the subspace given by the vectors A and B1 (resp. A1 and B) for whom the i-th component satisfies (resp. ).
After applying this node extension procedure for the node [A, B] we obtain two son-nodes [A, B1] and [A1, B], each with smaller space of feasible solutions.
Lower Cut and Upper Cut procedures.
For each node before applying a node extension procedure some cuts are executed. The aim is to reduce the space of feasible solutions which is associated with the node to be divided.
For our algorithm, the principle is simple, as mentioned above a node corresponds to a search space [A, B]. The cut procedure reduces the solution space [A, B] replacing A (respectively B) by a larger (respectively smaller) vector. This is equivalent to cutting a part of the search space [A, B]. We introduce two procedures: one for cutting small values (Lower Cut procedure) and second for cutting large values (Upper Cut procedure) of the corresponding decision variables. The reduction scheme is the same for these two procedures and they return "true" when the subset [A, B] is entirely dominated (i.e. by applying the cuts we completely eliminated the node [A, B]).
Upper bound calculation procedure.
This procedure to calculate an Upper Bound is a variant of depth first search that consists in choosing the node [A, B] to be partitioned (divided) that has the best solution at one of its two extremities (A or B).
6. Conclusion and further research
We studied an MRP parameterization problem for assembly systems under component lead time uncertainties. This problem of inventory control and production planning under uncertainties is crucial for industry. Most publications are devoted to customer demand uncertainties. In contrast, lead time uncertainties seem not be sufficiently studied, in particular, for the control of component inventories for assembly systems with random component procurement times (lead times). Nevertheless, many of industrial applications exist where the component lead times are random.
For the case of assembly systems with random lead times and a random demand, if the demand and component lead times are independent random variables, the following decomposition can be made. The finished product stock and the component stocks for assembly can be considered as independent. So, our approach is still valid for MRP parameterization: for the finished product a safety stock is calculated using the standard approaches, and the component planned lead times are deducted from the model proposed in this chapter.
Of course, it would be better to develop a model which takes into account the dependence between the stock of the finished product and component stocks in the case of random demand and lead times. This will be one path for our future research, perhaps using the conjecture of (Kim et al., 2006). This conjecture, suggested for a single-item model, affirms that the behaviour of an inventory/production system where both demand and lead times are random can be evaluated by modelling for three particular cases with: (i) deterministic demand and lead time, (ii) random demand and deterministic lead time, and (iii) random lead time and deterministic demand.
Further research should be focused on the development of a more effective Branch- and- Bound procedures for the general case of these single-level assembly systems. Another path for future work would deal with multilevel assembly systems, i.e. with multi-level bill of material. Logically, difficulty will increase because of dependence among levels in addition to the dependence among inventories.