In this paper, we discuss a new approach for solving an unbalanced assignment problem. A Lexi-search algorithm is used to assign all the jobs to machines optimally. The results of new approach are compared with existing approaches, and this approach outperforms other methods. Finally, numerical example (Table 1) has been given to show the efficiency of the proposed methodology.