Solving very large instances of the scheduling of independent tasks problem on the GPU

In this paper, we present two new parallel algorithms to solve large instances of the scheduling of independent tasks problem. First, we describe a parallel version of the Min–min heuristic. Second, we present GraphCell, an advanced parallel cellular genetic algorithm (CGA) for the GPU. Two new generic recombination operators that take advantage of the massive parallelism of the GPU are proposed for GraphCell. A speedup study shows the high performance of the parallel Min–min algorithm in the GPU versus several CPU versions of the algorithm (both sequential and parallel using multiple threads). GraphCell improves state-of-the-art solutions, especially for larger problems, and it provides an alternative to our GPU Min–min heuristic when more accurate solutions are needed, at the expense of an increased runtime.

► Solving very large instances of the scheduling of independent tasks.
► New CPU and GPU multi-threaded parallel designs of Min–min.
► New GPU multi-threaded parallel design of a cellular genetic algorithm.
► New multi-purpose recombination operator for cellular genetic algorithms on GPU.
► Accurate and fast results.