Hybrid metaheuristics have shown their capabilities to solve NP-hard problems. However, they exhibit significantly higher execution times in comparison to deterministic approaches. Parallel techniques are usually leveraged to overcome the execution time bottleneck for various metaheuristics. Recently, GPUs have emerged as general purpose parallel processors and have been harnessed to reduce the execution time of these algorithms. In this work, we propose a novel parallel memetic algorithm which is fully offloaded onto GPUs. In addition, we propose an adaptive sorting strategy in order to achieve maximum possible speedups for discrete optimization problems on GPUs. In order to show the efficacy of our algorithm, a task scheduling problem for heterogeneous environments is chosen as a case study. The output of this problem can have a tangible impact on overall performance of parallel heterogeneous platforms. The achieved results of our approach are promising and show up to 696x speedup in comparison to the sequential approach for various versions of this problem. Moreover, the effects of key parameters of memetic algorithms in terms of execution time and solution quality are investigated.