Solving Generalized Assignment Problem with Genetic Algorithm and Lower Bound Theory

Abstract: In this paper an attempt has been made to solve the “Assignment problem ” through genetic algorithm. In the assignment problem given N men and N jobs the task is to minimize overall cost of assignment considering the fact that a single job can be assigned to only one person. The problem is solved using genetic algorithm using an encoding scheme along with Partially Matched Crossover (PMX) function. The experimental setup has been carried out using values of N from 5 to 100. Though population size and generations are kept fixed but same can be varied in each iteration. The source codes for the above have been developed in matlab. For comparison results from lower bound theory and result from this experiment have analyzed. A comparison table for different values of N with results is presented that also contains deviation from results obtained through lower bound theory