||Job-shop-skedulering og togskedulering
||Clausen, Jens (Institut for Informatik og Matematisk Modellering, Danmarks Tekniske Universitet, DTU, DK-2800 Kgs. Lyngby, Denmark)
||Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
||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.
||Institut for Informatik og Matematisk Modellering, Danmarks Tekniske Universitet, DTU : DK-2800 Kgs. Lyngby, Denmark
||job shop scheduling; single track railway scheduling; total weighted tardiness; makespan; branch and bound; dominance criteria; shifting bottleneck
Creation date: 2006-06-22
Update date: 2012-12-19