At this time, Wireless Sensor Networks (WSNs) are widely used in many fields. This kind of network has some attractive features that have promoted their use, such as the absence of wires and the use of low-cost devices. However, WSNs also have important shortcomings that affect some features like energy cost and quality of service. In this paper, we optimize traditional static WSNs (a set of sensors and a sink node) by means of adding routers to simultaneously optimize a couple of important factors: energy consumption and average coverage. This multiobjective optimization problem was solved in a previous work using two genetic algorithms (NSGA-II and SPEA2) which had an important limitation: the computing time was very high and then, to address complex instances was difficult. In this paper, both algorithms are parallelized using OpenMP in order to reduce the computing time, and a more realistic data set is included. The results obtained are analyzed in depth from both multiobjective and parallel viewpoints. A Quite good efficiency is obtained with a wide range of processing cores, observing that NSGA-II provides the best results in small and medium instances, but in the largest ones the behavior of both algorithms is similar.