This paper proposes approaches for combining Iterated Greedy techniques, as state-of-the-art methods, with bacterial evolutionary algorithms based on a hybrid technique involving the Multi-Threaded Iterated Greedy heuristic and a memetic algorithm in order to efficiently solve the Permutation Flow Shop Problem on parallel computing architectures. In the present work three novel approaches are proposed by combining a variant of the Bacterial Memetic Algorithm and the recently proposed Bacterial Iterated Greedy technique with the mentioned hybrid multi-threaded approach. The techniques thus obtained are evaluated via simulation runs carried out on a series of data from the well-known Taillard's benchmark problem set. Based on the experimental results the multi-threaded hybrid methods are compared to each other and to the original techniques (i.e. to the techniques without bacterial algorithms). © 2012 IEEE.