Cloud computing has been imperative for computing systems worldwide since its inception. The researchers strive to leverage the efficient utilization of cloud resources to execute workload quickly in addition to providing better quality of service. Among several challenges on the cloud, task scheduling is one of the fundamental NP-hard problems. Meta-heuristic algorithms are extensively employed to solve task scheduling as a discrete optimization problem and therefore several meta-heuristic algorithms have been developed. However, they have their own strengths and weaknesses. Local optima, poor convergence, high execution time, and scalability are the predominant issues among meta-heuristic algorithms. In this paper, a parallel enhanced whale optimization algorithm is proposed to schedule independent tasks in the cloud with heterogeneous resources. The proposed algorithm improves solution diversity and avoids local optima using a modified encircling maneuver and an adaptive bubble net attacking mechanism. The parallelization technique keeps the execution time low despite its internal complexity. The proposed algorithm minimizes the makespan while improving resource utilization and throughput. It demonstrates the effectiveness of the proposed PEWOA against the best performing enhanced whale optimization algorithm (WOAmM) and Multi-core Random Matrix Particle Swarm Optimization (MRMPSO). The algorithm consistently produces better results with varying number of tasks on GoCJ dataset, indicating better scalability. The experiments are conducted in CloudSim utilizing a variety of GoCJ and HCSP instances. Various statistical tests are also conducted to evaluate the significance of the results. © 2013 IEEE.