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

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.

PDF

___

[1]Sahni S, Gonzalez T. p-Complete approximation problems. J ACM 1976; 23: 555-565.
[2]Pentico WP. Assignment problems: a golden anniversary survey. Eur J Oper Res 2007; 176: 774-793.
[3]Ross GT, Soland RM. A branch and bound algorithm for the generalized assignment problem. Math Program 1975;8: 91-103.
[4]Fisher ML, Jaikumar R. A generalized assignment heuristic for vehicle routing. Networks 1981; 11: 109-124.
[5]Mazzola JB, Neebe AW, Dunn CVR. Production planning of a exible manufacturing system in a materialrequirements planning environment. Int J Flex Manuf Sys 1989; 1: 115-142.
[6]Gross D, Pinkus CE. Optimal Allocation of Ships to Yards for Regular Overhauls. Technical Memorandum 63095.Washington, DC, USA: Institute of Management Science Engineering of George Washington University, 1972.
[7]Balachandran V. An integer generalized transportation model for optimal job assignment in computer networks.Oper Res 1972; 24: 742-759.
[8]Cromley RG, Hanink DM. Coupling land use allocation models with raster GIS. J Geogr Syst 1999; 1: 137-153.
[9]Cattrysse DG, Van Wassenhove LN. A survey of algorithms for the generalized assignment problem. Eur J OperRes 1992; 60: 260-272.
[10]Savelsbergh M. A branch-and-price algorithm for the generalized assignment problem. Oper Res 1997; 45: 831-841.
[11]Avella P, Boccia M, Vasilyev I. A computational study of exact knapsack separation for the generalized assignmentproblem. Comput Optim Appl 2010; 45: 543-555.
[12]Nauss RM. Solving the generalized assignment problem: an optimizing and heuristic approach. INFORMS J Comput2003; 15: 249-266.
[13]Chu PCH, Beasley JE. A genetic algorithm for the generalized assignment problem. Comput Oper Res 1997; 24:17-23.
[14]Osman IH. Heuristics for the generalized assignment problem: simulated annealing and tabu search approaches.OR Spectrum 1995; 17: 211-225.
[15]Daz JA, Fernandez E. A tabu search heuristic for the generalized assignment problem. Eur J Oper Res 2001; 132:22-38.
[16]Tasgetiren MF, Suganthan PN, Chua TJ, Al-Hajri A. Differential evolution algorithms for the generalized assignmentproblem. In: IEEE Congress on Evolutionary Computation; 18{21 May 2009; Trondheim, Norway. New York, NY,USA: IEEE. pp. 2606-2613.
[17]Ozbakir L, Baykasoglu A, Tapkan P. Bees algorithm for generalized assignment problem. Appl Math Comput 2010;215: 3782-3795.
[18]Yagiura M, Iwasaki S, Ibaraki T, Glover F. A very large-scale neighborhood search algorithm for the multi-resourcegeneralized assignment problem. Discrete Optim 2004; 1: 87-98.
[19]Liu YY, Wang S. A scalable parallel genetic algorithm for the generalized assignment problem. Parallel Comput2015; 46: 98-119.
[20]Wilson JM. A genetic algorithm for the generalised assignment problem. J Oper Res Soc 1997; 48: 804-809.
[21]Feltl H, Raidl GR. An improved hybrid genetic algorithm for the generalized assignment problem. In: Proceedingsof the 2004 ACM Symposium on Applied Computing; 14{17 March 2004; Nicosia, Cyprus. New York, NY, USA:ACM. pp. 990-995.
[22]Holland JH. Adaptation in Natural and Arti cial Systems. Ann Arbor, MI, USA: University of Michigan Press,1975.
[23]Goldberg DE. Genetic Algorithms in Search, Optimization and Machine Learning. Boston, MA, USA: Addison-Wesley Longman Publishing, 1988.
[24]Chatterjee S, Laudato M, Lynch LA. Genetic algorithms and their statistical applications: an introduction. ComputStat Data An 1996; 22: 633-651.
[25]Zolfaghari S, Liang M. A new genetic algorithm for the machine/part grouping problem involving processing timesand lot sizes. Comput Ind Eng 2003; 45: 713-731.
[26]Salomon R. The in uence of different coding schemes on the computational complexity of genetic algorithmsin function optimization. In: Fourth International Conference on Parallel Problem Solving from Nature; 22{26September 1996; Berlin, Germany. Cham, Switzerland: Springer. pp. 227-235.