The U-shaped assembly line-balancing problem can be solved using optimization procedures or algorithms, including branch-and-bound procedures. This paper considers design elements that should be included in these solution methods for solving the U-shaped assembly line-balancing problem. New solution procedures are proposed and compared experimentally with several existing procedures using a variety of problem sets from the literature. The results show that the substantial improvement in the efficacy of the new solution procedures over existing methods is due primarily to the newly developed 'Paired Tasks' lower bound. Results also show the relative importance of various design elements comprising a branch-and-bound procedure.