| The Line Planning Problem is a sub-problem within the more general Railroad Scheduling Problem. A line can be seen as a corridor with two main entry points for trains, one at each end of the line. On occasion there may be trains coming into the line from entry points along the line (i.e.: a yard from a factory). In the generic Line Planning Problem, there are two sets of trains, one at each end of the line, requesting authorization to cross the line. The goal is to generate one or several plans that will make it possible for the two sets of trains to traverse the line, optimizing some criteria, such as lateness or makespan.; This dissertation addresses two main issues: (1) Modelling the Line Planning Problem as a modified Job-Shop Scheduling Problem. (2) Demonstrating the benefits of using Multiple Representations in A-Teams.; This thesis addresses the Line Planning Problem by modelling it as a modified version of the well-known Job-Shop Scheduling Problem. In doing so, the goal is to benefit from the many existing algorithms developed for the Job-Shop Scheduling Problem, and combine them into an A-Team to solve the Line Planning Problem.; One of the major hurdles to achieve our goal was to find a good deadlock avoidance mechanism that would allow us to predict when certain train movements would cause deadlocks on the line. The avoidance of deadlocks is desirable because deadlocks do not occur in Job-Shops, but they may occur quite frequently on railroad lines. Once the problem with deadlocks was resolved, most Job-Shop Scheduling algorithms could be adapted almost immediately to solve Line Planning Problems.; Through this research, we developed a deadlock avoidance mechanism called Modular Switch Array Method, and integrated it into many Job-Shop Scheduling algorithms. Then, we combined the various algorithms, many of them using different representations, into a Multiple Representation A-Team to solve the Line Planning Problem. ftn *This work has been supported by Conselho Nacional de Pesquisa (CNPq) and by the Engineering Design Research Center (EDRC), a National Science Foundation ERC. |
