Solving the Assignment problem using Genetic Algorithm and Simulated Annealing

Paper, 4 p, IAENG International Journal of Applied Mathematics.
The paper attempts to solve the generalized Assignment problem through genetic algorithm and simulated annealing. The generalized assignment problem is basically the N men- N jobs problem where a single job can be assigned to only one person in such a way that the overall cost of assignment is minimized. While solving this problem through genetic algorithm (GA), a unique encoding scheme is used together with Partially Matched Crossover (PMX). The population size can also be varied in each iteration. In simulated annealing (SA) method, an exponential cooling schedule based on Newtonian cooling process is employed and experimentation is done on choosing the number of iterations (m) at each step. The source codes for the above have been developed in C language and compiled in GCC. Several test cases have been taken and the results obtained from both the methods have been tabulated and compared against the results obtained by coding in AMPL.