This study presents a coalition-based parallel metaheuristic algorithm for solving Permutation Flow Shop Scheduling Problems (PFSP). The proposed approach incorporates five different single-solution based metaheuristic algorithms (SSBMA) (Simulated Annealing Algorithm, Random Search Algorithm, Great Deluge Algorithm, Threshold Accepting Algorithm and Greedy Search Algorithm) and a recently proposed swarm intelligence based metaheuristic algorithm that is known as Weighted Superposition Attraction Algorithm (WSA). While SSBMAs are responsible for exploring the search space, WSA serves as a controller that handles the coalition process. SSBMAs perform their search simultaneously by utilizing MATLAB’s parallel programming tool. When all SSBMAs complete their search, they share their findings with other SSBMAs through the superposition mechanism of WSA. As a result of sharing, SSBMAs move towards the superposition point found by the coalition of SSBMAS or they do their own local search if they are in a better position (has a better fitness) than the superposition. Before a new parallel search process, SSBMAs determine their new characteristics (new parameters). This search and coalition process last until a predetermined iteration number is reached. The proposed approach is tested on many PFSP benchmarks and results are compared against the state of the art algorithms from the literature. Moreover, the proposed algorithm is also tested against its constituents (SSBMAS and WSA) and its serial version. Non-parametric statistical tests are performed to compare the performance of the proposed approach statistically with the state of the art algorithms, its constituents and its serial version. The statistical results prove the effectiveness of the proposed approach.