Improved Hungarian Algorithm for Unbalanced Assignment Problems

Abstract

Hungarian algorithm gives optimum one to one assignment when there are equal number of machines and jobs. For unbalanced assignment problems, prior to solve it, dummy jobs/machines are to be added to convert the unbalanced problem in to a balanced problem. But the jobs which are assigned to dummy machines cannot be served in reality. So to avoid this problem duplication of required number of machines/jobs, that is multiple jobs (machines) are assigned to a single machine (job) is proposed. At most care is taken while selecting the duplicate machines/jobs to minimize the cost of final assignment. In addition to that the proposed algorithm ensures no overloading of particular machine/job. Some researchers have proposed this concept, but an improved Hungarian algorithm is introduced in this paper, which gives the optimum result with reduced computational complexity. In addition to this, the proposed algorithm is most generalized one which solves the assignment problem for all possible number of machines and jobs, which is not addressed by other researchers. Furthermore, it ensures no machine or job is overloaded.