The use of abstractions to solve large scheduling problems

Holmberg, Per (2000) The use of abstractions to solve large scheduling problems. [SICS Report]



This thesis investigates how abstractions can be used to improve performance in a railroad scheduling system that uses constraint programming. The idea behind abstractions is to solve a large problem in smaller parts and extract information from these parts. That information can then be used when solving the entire problem. Two different types of abstractions are introduced: Relations and Net abstractions. The use of relations builds orders between trips or parts of trips. These orders can be used to reduce the search necessary to find a solution to the scheduling problem. When using net abstraction, the problem is solved in an abstract search space, where it is easier to solve. The solution computed in the abstract search space is then used to reduce search when solving the problem in the original space. It is shown that these two types of abstraction can improve performance in problems with various settings. Relations can successfully be used in problems that have few solutions and are hard to solve. Net abstraction on the other hand works best for problems with many valid solutions.

Item Type:SICS Report
Uncontrolled Keywords:Train planning, Hierarchical planning,Vehicle routing and scheduling, Constraint programming, Formal abstraction
ID Code:2290
Deposited By:Vicki Carleson
Deposited On:30 Jul 2009
Last Modified:18 Nov 2009 16:04

Repository Staff Only: item control page