The Permutation flow shop scheduling problem (PFSP) is a well-known combinatorial problem which is difficult for solving using the exact methods in case of large number of jobs and machines. It’s a variant of the flow shop scheduling problem (FSSP) and it has many applications in particular in the optimization of the production and supply chain management because it consists of optimizing the organization of manufacturing tasks on machines or production lines. The aim of this paper is comparing two new interesting metaheuristics applied for solving PFSP which have achieved good results. These metaheuristics are: The PGS-EDA algorithm, that’s an improved version of the ordinary evolutionary EDA algorithm (Estimation differential algorithm) using new methods in modeling and sampling step, and the HPSO algorithm that is a hybridization of the swarm algorithm PSO (Particle swarm optimization) and VNS (Variable neighborhood search) and SA (Simulated Annealing). So, this comparison is based on recomputing the ARPD of the two algorithms that will demonstrate the power of the HPSO in comparison to the PGS-EDA. This paper will be helpful for interested researchers in solving combinatorial problem in general and the PFSP particularly using different metaheuristics.