This study deals with Material Requirement Planning (MRP) software parameterization under uncertainties. The actual lead time has random deviations; so it can be considered as a random variable. MRP approach with Periodic Order Quantity (POQ) policy is considered. The aim is to find the optimal MRP time phasing corresponding to each periodicity of the POQ policy. This is a crucial issue in supply planning with MRP approach because inappropriate planned lead times under lead time uncertainties invariably lead to large and costly inventories or insufficient customer service levels. The proposed model and algorithms minimize the sum of the setup and holding costs while satisfying a constraint on the service level. Our approach does not need to employ the commonly used normal probability distributions. Instead, its originality is in finding a closed form of the objective function, valid for any probability distribution of the actual lead times.