Job-shop-skedulering og togskedulering

Christian Schmidt

AbstractThis 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.
Keywordsjob shop scheduling; single track railway scheduling; total weighted tardiness; makespan; branch and bound; dominance criteria; shifting bottleneck
TypeMaster's thesis [Academic thesis]
Year2002
PublisherInformatics and Mathematical Modelling, Technical University of Denmark, DTU
AddressRichard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby
SeriesIMM-EKS-2002-34
Electronic version(s)[pdf]
BibTeX data [bibtex]
IMM Group(s)Operations Research