In this paper, we propose a new exact method, called the parallel partitioning method (PPM), able to solve efficiently bi-objective problems. This method is based on the splitting of the search space into several areas leading to elementary exact searches. We compare this method with the well-known two-phase method (TPM). Experiments are carried out on a bi-objective permutation flowshop problem (BOFSP). During experiments the proposed PPM is compared with two versions of TPM: the basic TPM and an improved TPM dedicated to scheduling problems. Experiments show the efficiency of the new proposed method.