The rail industry spends billions of dollars each year on maintenance and renewal of its track infrastructure. The scheduling of these maintenance projects is extremely complex, with numerous hard and soft cost trade-offs and job scheduling constraints. Scheduling requires consideration of efficient maintenance production “gang” routing around the rail network while paying close attention to any train delay such maintenance projects might cause. Despite this importance and complexity, the subject has been largely ignored in the literature. We evaluate two formulations (time-space network mixed integer program and job scheduling) and three modeling formulation and solution methodologies (integer programming, constraint programming, and genetic algorithms) for scheduling rail gangs to annual renewal projects and discuss their relative merits in terms of parsimony of model formulation, solution time, and solution quality. The purpose of this paper is to identify the most fruitful avenues for further research on this novel application.