11152

BbmTTP: Beat-based Parallel Simulated Annealing Algorithm on GPGPUs for the Mirrored Traveling Tournament Problem

Vijay Menon, Saurabh Jha
School of Computing Science and Engineering, VIT University, Chennai, India
VIT University, 2013

@article{menon2013bbmttp,

   title={BbmTTP: Beat-based Parallel Simulated Annealing Algorithm on GPGPUs for the Mirrored Traveling Tournament Problem},

   author={Menon, Vijay and Jha, Saurabh},

   year={2013}

}

Download Download (PDF)   View View   Source Source   Source codes Source codes

Package:

3607

views

The problem of scheduling sports leagues has received considerable attention in recent years, especially since mathematically optimized schedules often have a large impact both economically and environmentally. The Mirrored Traveling Tournament Problem (mTTP) is an optimization problem that represents certain types of sports scheduling where the main objective is to minimize the total distance traveled by all the participating teams. In this paper, we propose a GPU based parallel simulated annealing algorithm for mTTP and test the available instances using NVIDIA’s Compute Unified Device Architecture (CUDA). The approach taken here, especially keeping in mind the computationally intensive nature of mTTP, involves exploiting the thread level parallelism available in CUDA – where each thread starts with a random schedule from the discrete solution space and cooperate at regular intervals – called ‘Beats’ – to search for optimized solutions. Additionally, in this paper, we also introduce a new mTTP instance – IPL09 – which concerns with arriving at an optimized schedule for the Indian Premier League – one of India’s most popular sports league. Applying the proposed BbmTTP to IPL09 we were successful in generating a schedule which reduced the total distance traveled by 30.20%, or nearly 37,000 kilometres.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: