We consider the m-machine permutation flowshop with the objective of minimizing total completion time. We compare few recent heuristics that are independently developed and propose several new heuristics. Our computational analysis shows that a small proposed modification (pairwise exchange) improves the error performance of the best existing algorithms almost 50% with negligible CPU time. Moreover, some of our proposed heuristics outperform the modified existing heuristics in both error and CPU time. For example, for U(1,100) and number of jobs 500 and number of machines 20, our proposed heuristic IH3 yields an error of 0.287 at a CPU time of 144 seconds whereas the modified existing WY heuristic gives an error 0.325 at a CPU time of 2665 seconds.
