In this paper we present three path relinking approaches for solving a bi-objective permutation flowshop problem. The path relinking phase is initialized by optimizing the two objectives using Ant Colony System. The initiating and guiding solutions of path relinking are randomly selected and some of the solutions along the path are intensified using local search. The three approaches differ in their strategy of defining the heuristic bounds for the local search, i.e., each approach allows its solutions to undergo local search under different conditions. These conditions are based on local nadir points. Several test instances are used to investigate the performances of the different approaches. Computational results show that the decision which allows solutions to undergo local search has an influence in the performance of path relinking. We also demonstrate that path relinking generates competitive results compared to the best known solutions of the test instances.