Beta 1


Title Job-shop-skedulering og togskedulering
Author Schmidt, Christian
Supervisor Clausen, Jens (Institut for Informatik og Matematisk Modellering, Danmarks Tekniske Universitet, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2002
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.
Imprint Institut for Informatik og Matematisk Modellering, Danmarks Tekniske Universitet, DTU : DK-2800 Kgs. Lyngby, Denmark
Pages 134
Keywords job shop scheduling; single track railway scheduling; total weighted tardiness; makespan; branch and bound; dominance criteria; shifting bottleneck
Fulltext
Original PDF imm875.pdf (0.50 MB)
Admin Creation date: 2006-06-22    Update date: 2012-12-19    Source: dtu    ID: 58343    Original MXD