Generalized assignment problem (GAP) is a classic combinatorial optimization problem that has been proved to be NP-hard problem. For solving the GAP problem, combining the bat algorithm (BA) with the Lagrangian relaxation algorithm (LR), an efficient Lagrangian bat algorithm (LR-DBA) was proposed based on the characteristics of the GAP problem. The DBA takes BA as the basic framework and redefines the formulas of velocity, position and local updating. It was then combined with the LR algorithm to form the LR-DBA hybrid algorithm. A large number of examples show that compared with the DBA algorithm, the LR-DBA algorithm has obvious advantages in solving the GAP problem.