Using semantic analysis to assist schedule optimization

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/256248
Download file(s):
File Description SizeFormat 
256248.pdfFulltext591.41 kBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: Using semantic analysis to assist schedule optimization
Authors: RIPPE, JACOB
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.
Keywords: Data- och informationsvetenskap;Computer and Information Science
Issue Date: 2018
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
URI: https://hdl.handle.net/20.500.12380/256248
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.