This paper focuses on the configuration of a parallel multi-purpose machines workshop. An admissible configuration must be chosen in order to ensure that a load-balanced production plan meeting the demand exists. Moreover, the demand is strongly subject to uncertainties. That is the reason why the configuration must exhibit robustness properties: the load-balancing performance must be guaranteed with regard to a given range of uncertainties. A branch-and-bound approach has been developed and implemented to determine a cost-constrained configuration that maximizes a robustness level. Computational results are reported for both academic and industrial-scale instances. More than 80% of the academic instances are solved to optimality by the proposed method. Moreover, this method appears to be a good heuristic for industrial-scale instances.