Change search
ReferencesLink to record
Permanent link

Direct link
Train Re-scheduling: A Massively Parallel Approach Using CUDA
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science and Engineering.
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Context. Train re-scheduling during disturbances is a time-consuming task. Modified schedules need to be found, so that trains can meet in suitable locations and delays minimized. Domino effects are difficult to manage. Commercial optimization software has been shown to find optimal solutions, but modied schedules need to be found quickly. Therefore, greedy depth-first algorithms have been designed to find solutions within a limited time-frame. Modern GPUs have a high computational capacity, and have become easier to use for computations unrelated to computer graphics with the development of technologies such as CUDA and OpenCL.

Objectives. We explore the feasibility of running a re-scheduling algorithm developed specifically for this problem on a GPU using the CUDA toolkit. The main objective is to find a way of exploiting the computational capacity of modern GPUs to find better re-scheduling solutions within a limited time-frame.

Methods. We develop and adapt a sequential algorithm for use on a GPU and run multiple experiments using 16 disturbance scenarios on the single-tracked iron ore line in northern Sweden.

Results. Our implementation succeeds in finding re-scheduling solutions without conflicts for all 16 scenarios. The algorithm visits on average 7 times more nodes per time unit than the sequential CPU algorithm when branching at depth 50, and 4 times more when branching at depth 200.

Conclusions. The computational performance of our parallel algorithm is promising but the approach is not complete. Our experiments only show that multiple solution branches can be explored fast in parallel, but not how to construct a high level algorithm that systematically searches for better schedules within a certain time limit. Further research is needed for that. We also find that multiple threads explore redundant solutions in our approach.

Place, publisher, year, edition, pages
2015. , 42 p.
Keyword [en]
scheduling algorithms, massively parallel algorithms, combinatorial optimization
National Category
Computer Science
URN: urn:nbn:se:bth-10965OAI: diva2:868498
Subject / course
DV2566 Master's Thesis (120 credits) in Computer Science
Educational program
DVACS Master of Science Programme in Computer Science
2015-09-21, Karlskrona, 15:00 (English)
Available from: 2015-11-11 Created: 2015-11-10 Last updated: 2015-11-11Bibliographically approved

Open Access in DiVA

fulltext(562 kB)29 downloads
File information
File name FULLTEXT01.pdfFile size 562 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Petersson, Anton
By organisation
Department of Computer Science and Engineering
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 29 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 131 hits
ReferencesLink to record
Permanent link

Direct link