Abstract: The focus of this study is on resource constrained project scheduling with stochastic task durations. In the extensive research performed in project scheduling, little research has been done with projects that have stochastic activity durations. In this study, we explore combining two priority rule based heuristics (Longest Activity First (LAF) and Greatest Resource Demand (GRD) using weights assigned to each heuristic. The heuristics are then used to schedule the project activities. Genetic Algorithms (GA) are used to find the optimal weights on the heuristics. The GA search was compared to both random and interval searches. Two performance measures were used: average percent deviation from the best mean project duration found by the enumerative search and average percent deviation from the best variance found by the enumerative search. An experimental analysis was conducted to evaluate the performance of the three approaches. A full factorial design with 10 replications was used in this evaluation. It was found that the interval search performs better than the random search, which in turn performs better than the GA.