Synthesis of Planning and Scheduling Software

Advanced Planning Technology: Technological Achievements of the ARPA/Rome Laboratory Planning Initiative

Volume

Book One

Contents

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, high-performance 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 es-timator (JFAST) and 36 hours for deployed schedulers (FLOGEN, ADANS). The computed schedules use relatively few resources and satisfy all specified constraints. The speed of this scheduler is due to the synthesis of strong constraint checking and constraint propagation code.