Solutions of Mono and Multi-objective Assignment Problems without Modification Matrix

Abstract

This paper presents a new solution technique for assignment problems. In the first phase, the proposed technique is used for the solution of mono-objective optimization problems, while in the second phase, the proposed technique is extended for the solution of multi-objective optimization problems. In the first phase, a distance matrix is defined and then reduced to the form which contains at least one zero in each row or one zero in each column. Moreover, the sum of each column's entries must be less than 2 to use the Hungarian algorithm. The proposed technique differentiates itself from the existing techniques in the literature in the sense that the case N ≠ n will not happen, and consequently, we do not define a modification matrix. Therefore, the proposed methodology reduces the solution procedure to a high extent. The proposed methodology is equally applicable to the solutions of multi-objective optimization problems as well. In such a case, we minimize each objective of the multi-objective problem by the proposed methodology and then use available multi-objective optimization algorithms for further solution for non-dominated solutions. The proposed approach is validated by numerical examples in both phases.