high performance computing on graphics processing units: hgpu.org

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.