A modi ed genetic algorithm for a special case of the generalized assignmentproblem

Abstract

Many central examinations are performed nationwide in Turkey. These examinations are held simultaneouslythroughout Turkey. Examinees attempt to arrive at the examination centers at the same time and they encounterproblems such as traffic congestion, especially in metropolises. The state of mind that this situation puts them intonegatively affects the achievement and future goals of the test takers. Our solution to minimize the negative effects ofthis issue is to assign the test takers to closest examination centers taking into account the capacities of examinationhalls nearby. This solution is a special case of the generalized assignment problem (GAP). Since the scale of the problemis quite large, we have focused on heuristic methods. In this study, a modi ed genetic algorithm (GA) is used forthe solution of the problem since the classical GA often generates infeasible solutions when it is applied to GAPs. Anew method, named nucleotide exchange, is designed in place of the crossover method. The designed method is runbetween the genes of a single parent chromosome. In addition to the randomness, the consciousness factor is takeninto consideration in the mutation process. With this new GA method, results are obtained successfully and quickly inlarge-sized data sets.