Supply planning for two-level assembly systems under lead time uncertainties is considered. It is supposed that the demand for the finished product and its due date are known. The assembly process at each level begins when all necessary components are in inventory. A holding cost at each level appears if some components needed to assemble the same semi-finished product arrive before beginning the assembly at this level. It is assumed also that the component lead time is a random discrete variable. The objective is to find the release dates for the components at level 2 in order to minimize the expected component holding costs and to maximize the customer service level for the finished product. For this new problem, we consider two multi-objective approaches, which are both based on genetic algorithms. They are evaluated with a variety of supply chain settings, and their respective performance is reported and commented. These two heuristics permitted to obtain interesting results within a reasonable computational time.