Job-shop-skedulering og togskedulering |
Christian Schmidt
|
| 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 |
| Type | Master's thesis [Academic thesis] |
| Year | 2002 |
| Publisher | Informatics and Mathematical Modelling, Technical University of Denmark, DTU |
| Address | Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby |
| Series | IMM-EKS-2002-34 |
| Electronic version(s) | [pdf] |
| BibTeX data | [bibtex] |
| IMM Group(s) | Operations Research |