This paper proposes approaches for combining the Iterated Greedy (IG) technique, as a presently state-of-the-art method, with a recently proposed adapted version of the Bacterial Evolutionary Algorithm (BEA) in order to efficiently solve the Permutation Flow Shop Problem. The obtained techniques are evaluated via simulation runs carried out on the well-known Taillard's benchmark problem set. Based on the experimental results the hybrid methods are compared to each other and to the original techniques (i.e. to the original IG and BEA algorithms). © 2012 IEEE.