Branch-and-Bound (B&B) is a problem-solving technique which is widely used for various problems encountered in operations research and combinatorial mathematics. In this paper, the lower bound of running time Ω(m/p+hlogp)(the base of all logarithms in this paper is 2) is presented for general parallel best-first B&B algorithms on shared memory systems, where p is the number of processors available, h is the number of expanded nodes, and m is the total number of active nodes in state-space tree. In addition, a new general parallel best-first B&B algorithm on PRAM-EREW is proposed by devising the shared memory into p cubeheaps. Theoretical analysis shows that it is the fastest algorithm for h<p^2p, and it is asymptotically optimal in this type of general parallel B&B algorithms. Computational experiments are conducted to solve 0-r knapsack problem.