Railway scheduling problems and their decomposition [Elektronische Ressource] / Christian Strotmann

Railway scheduling problems and theirdecompositionDissertationim Fachbereich Mathematik/Informatik der¨Universitat Osnabru¨ckChristian StrotmannOsnabru¨ck, Juli 2007AbstractRailway scheduling problems are quite popular scheduling and optimization prob-lems which are treated in a large variety of papers and projects. Many special andeven quite general situations have been investigated theoretically and also a varietyof applied approaches tested on real-world instances has been developed.This thesis mainly deals with the problem of scheduling trains in railway net-works with respect to given routings, fixed minimal travelling times, and other con-straints like time-windows. It combines the theory of some well-known schedulingmodels with its applications in railway scheduling. The railway scheduling prob-lems considered in this work are closely related to job-shop scheduling problemswith blocking and some additional constraints. Therefore part of this research isrelated to these shop scheduling problems. Theoretical scheduling models are ex-tended, complexity results are derived and solution methods are proposed. Mostresults are applied to the considered railway scheduling problems. In addition to ap-proaches which treat railway problems as a whole also decomposition methods forthese problems and corresponding solution methods are presented. These solutionmethods are tested and compared with simple greedy procedures.