Implementation of Hungarian Procedure Using C++ (Case study of Dangote flour mills)

Abstract

The Hungarian method is a combinatorial optimization algorithm which solves the assignment problem in polynomial time. It is also known as Kuhn–Munkres algorithm or Munkres assignment. The implementation of Hungarian procedure requires a nonnegative n×n matrix, where the element in the i-th row and j-th column represents the cost of assigning the j-th job to the i-th worker. We have to find an assignment of the jobs to the workers that have minimum cost. This project takes input from user and then performs the job of scheduling based on the best available options provided. It was observed that the algorithm works even when the minimum values in two or more rows are in the same column, when two or more of the rows contain the same values in the same order. Or even when all the values are the same (although the result is not very interesting). Munkres Assignment Algorithm is not exponential run time or intractable. Optimality is guaranteed in Munkres Assignment Algorithm. It takes fraction of seconds to perform it computation in most cases.