Using semantic analysis to assist schedule optimization
Ladda ner
Typ
Examensarbete för masterexamen
Master Thesis
Master Thesis
Program
Computer science – algorithms, languages and logic (MPALG), MSc
Publicerad
2018
Författare
RIPPE, JACOB
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Data- och informationsvetenskap , Computer and Information Science