Job-shop-skedulering og togskedulering

In June 2002 I achieved my Master of Science degree in Engineering.

I wrote my Master's Thesis at the Operations Research Section at the department of Informatics and Mathematical Modelling.

Abstract

This thesis investigates the job-shop scheduling problem with emphasis on a particular application, namely railway scheduling. Two different objective functions are examined: makespan and total weighted tardiness.

Different solution strategies are applied, including Branch & Bound with two different branching strategies and the Shifting Bottleneck heuristic. Most methods are mentioned in different variants for the two objective functions.

Performance is measured with different test instances from in the literature.

A bounding function for total weighted tardiness is developed and investigated. Also two different bounding functions for makespan are examined. A local search heuristic is used to find tighter bounds, and this improves the performance marginally.

For Branch & Bound a new dominance criterion is suggested for pruning the search tree. With generel job-shop instanses this does not lead to increased performance, but for train scheduling instanses the results look promising.

Keywords

job shop scheduling; single track railway scheduling; total weighted tardiness; makespan; branch and bound; dominance criteria; shifting bottleneck