In the process industry, plant production is completely halted every so many years for large-scale maintenance comprising inspection, repair and overhaul. It is paramount that this shutdown maintenance is completed according to the planning, which requires timely availability of replacement parts. In this setting, we present a spare parts optimization model and algorithm that includes the cost-time trade-off and precedence constraints between maintenance activities. The objective is to balance between spare parts ordering cost and the expected project delay cost due to waiting for spare parts. Using two-stage stochastic programming, spare parts ordering policies are determined in the first stage and a detailed project schedule is developed in the second stage. We propose a sample average approximation with importance sampling and pruning of dominated activities to solve the problem, and demonstrate that this method solves large instances quickly. We also consider heuristics, e.g. the standard project management approach based on the widely used critical path method and two heuristics that draw from spare part inventory control literature. These heuristics give poor solutions.