Current networks-on-chip (NoCs) may include many Intellectual Properties (IPs). As those IPs do not necessarily operate at the same clock frequency, a significant number of Phase Locked Loops (PLLs) are required. Since a PLL is very power consuming (e.g., a PLL delivering a 6 GHz frequency consumes 11 mW), one needs to reduce the number of PLLs. To the best of our knowledge, only one work in literature tackled this problem. Since the interested problem is not polynomial in time, we developed heuristic-based methods and found that our work outperforms that which is described in the literature both in terms of number 30% and power consumption 25% of PLLs with less CPU time.