The most popular parallelization approach of the branch and bound algorithm consists in building and exploring in parallel the search tree representing the problem being tackled. The deployment of such parallel model on a grid rises the crucial issue of dynamic load balancing. The major question is how to efficiently distribute the nodes of an irregular search tree among a large set of heterogeneous and volatile processors. In this paper, we propose a new dynamic load balancing approach for the parallel branch and bound algorithm on the computational grid. The approach is based on a particular numbering of the tree nodes allowing a very simple description of the work units distributed during the exploration. Such description optimizes the communications involved by the huge amount of load balancing operations. The approach has been applied to one instance of the bi-objective flow-shop scheduling problem. The application has been experimented on a computational pool of more than 1000 processors belonging to seven Nation-wide clusters. The optimal solution has been generated within almost 6 days with a parallel efficiency of 98%.