During the construction phase of large-scale structures, efficient scheduling of installation activities can have a major impact on the cost and duration of the overall construction process. However, due to the inherent uncertainty of construction process and dynamic pricing of the resources, and the fact that schedule is sensitive to perturbation of these uncertain data, there exists a major concern on how to formulate and solve the scheduling optimization problem that will return robust solutions. To answer this question, we first propose two robust formulations with Mean + 6Sigma and Worst-case, respectively, based on a nominal project scheduling optimization problem.  Next, we extend the conventional scatter search algorithm with a graph-based algorithm to efficiently reduce the computational complexity for solving the resource availability cost problem (RACP), and proposed different algorithms for each formulation. To evaluate the Mean + 6Sigma and Worst-case formulations in terms of optimality, robustness, and computational complexity, a case-study on 3 high-rise steel structures with varying part count has been conducted.  Key contributions include a novel and tractable application of the Mean + 6Sigma and Worst-case robust optimization methods based on construction part attributes, a fast and robust graph-based scatter search algorithm, and a simplified framework for choosing formulations based on the objective of robustness for scheduling problem.