Using semantic analysis to assist schedule optimization

Abstract

Airline Crew Planning is a complex task often divided into many steps to reduce complexity. One approach for finding good solutions is to generate a large set of solutions and determine which combination of solutions satisfy all constraints at the lowest cost. We have analyzed a software system for generating solutions that uses rules stated in a DSL to determine solution legality. The legality is checked during solution generation, and the legality of the solution in progress affect the generation strategy. The question this project sought to answer is whether it is possible to determine certain properties of the rules at compile-time. The approach has been to analyze the structure of the rules and assign semantic information in a method inspired by type inference rules. In an iterative fashion, theories about the system were formed, and tested by implementing checks inside the DSL compiler. After manual verification of the theories by looking at the output of the implementation, the theories were expanded upon or revised. The implementation has been able to automatically identify a few rules with the desired properties, and more may be identified with continued development. Inference rules were a general approach to deciding properties, and more interesting findings might be found using more advanced techniques. However, there is a limit to what can be decided by static analysis. Aside from analyzing existing rules, some semantic information may be of assistance when writing new rules, and might even be of assistance at runtime in future projects.