In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree.Then the lower bound Ω(m＋hlog h) of the running time for the general sequential B&B algorithm and the lower bound Ω(m/p ＋ hlogp) for the general parallel best-first B&B algorithm in PRAMCREW are proposed, where p is the number of processors available. Moreover, the lower bound Ω(M/p＋H＋ (H/p) log (H/p)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B&B algorithm is put forward. The parallel algorithm is the fastest one az p ＝ max{he,r}, where ε ＝ 1/logh,and r is the largest branch number of the nodes in the state-space tree.