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.