While processor frequency stagnates for two decades, the number of available cores in servers or clusters is still growing, offering the opportunity for significant speed-up in combinatorial optimization. Parallelization of exact methods remains a difficult challenge. We revisit the concept of parallel branch-and-bound in the framework of weighted constraint satisfaction problems. We show how to adapt an anytime hybrid best-first search algorithm in a master/worker protocol. The resulting parallel algorithm achieves a good load-balancing without introducing new parameters to be tuned as in the embarrassingly parallel search (EPS) approach. It has also a small overhead due to its light communication messages. We performed an experimental evaluation on several benchmarks, comparing our parallel algorithm to its sequential version. We observed linear speed-up in some cases. Our approach compared favourably to the EPS approach and also a state-of-the-art parallel exact integer programming solver.