Novel Method to Improve ACO Performance on the GPU Using CUDA for Nurse Roster Scheduling Problem

Abstract: This paper shows the accomplishment of parallel Ant Colony Optimization algorithm on the Graphics Processing Unit (GPU) to solve nurse roster scheduling problem (NRSP).We put on the Schedule formation and pheromone update phases of Ant colony Optimization using a data parallel method. We applied roulette wheel selection method for schedule formation and pheromone update. The parallel accomplishment of roulette wheel selection method considerably cuts the execution time of Schedule formation. Our new parallel accomplishment executes up to 8-12x faster than sequential execution at the same time as preserving the quality of the Schedules formation.

Keywords: CUDA, GPU, NRSP, NVDIA, ACO.