In this paper we present a Genetic Algorithm based heuristic for solving the Product Line Design Problem using the Buyers' Welfare criterion. The new approach is compared with a recently developed Beam Search method on randomly generated problems. Our method seems to be substantially better in terms of CPU time. Also, the solutions found by our method are better than those found by the Beam Search method in comparable times.