Synthesis of Planning and Scheduling Software
Douglas R. Smith, Eduardo A. Parra, Stephen J. Westfold, Polo Alto · 1996
This report describes our research on transportation planning and scheduling supported by the ARPA/Rome Lab Planning Initiative (ARPI). The main goal of this project was to develop generic tools to support the construction of flexible, highperformance planning and scheduling software. Our technical approach is based on program transformation technology which allows machine-supported development of software from requirement specifications. The development process produces code that is correct by construction and which can be highly efficient. We have used KIDS (Kestrel Interactive Development System) to derive extremely fast and accurate transportation schedulers from formal specifications. As test data we use strategic transportation plans which are generated by U.S. government planners. A typical problem, with 10,000 movement requirements, takes the derived scheduler 1 -- 3 minutes to solve, compared with 2.5 hours for a deployed feasibility estimator (JFAST) and 36 hours for deployed...