Genetic algorithm approach for the balanced assignment problem

Abstract

The Assignment Problem (AP) presents a crucial challenge in operations research, involving the allocation of resources to tasks to minimize costs or maximize profits. There are many approaches developed to address the AP, including the Modified Ant Colony Optimization Algorithm, Bottleneck Cost Method, New Revised Zero's to One's Method, Matrix One's Assignment Method, and Maximum Difference Cost Method. The Hungarian method produces very prominent results, and it is effective for small to medium-sized problems, yet becomes computationally intensive for large-scale APs. This study proposed a heuristic approach using a genetic algorithm (GA) designed even for large-scale APs. This modified GA incorporated tournament selection for parent selection, applies crossover operations targeting the minimum value in each row, and prevents redundant assignments through swap mutation. These techniques simplify the algorithm compared to the other methods. A numerical example was analysed to illustrate the practical application of the proposed method. This example demonstrated how the proposed method effectively handles the problem, providing clear insights into its accuracy. This approach, where solutions improve generation by generation, highlights the potential of GAs for tackling complex or large-scale assignment problems.