This paper examines supply planning for two level assembly systems under lead time uncertainties. It is supposed that the demand for the finished product and its due date are known. It is assumed also that the component lead time at each level is a random discrete variable. The expected cost is composed of the finished product tardiness cost and the component holding costs. The objective is to find the release dates for the components at level 2 in order to minimize the total expected cost. A genetic algorithm is suggested. The proposed algorithm is evaluated with a variety of supply chain settings in order to verify its robustness across different supply chain scenarios. Moreover, the effect of a local search on the performance of the Genetic Algorithm in terms convergence and computation time is investigated.