Date of Graduation
Statler College of Engineering and Mineral Resources
Industrial and Managements Systems Engineering
Kenneth R. Currie
The generalized quadratic assignment problem (GQAP) is the task of assigning a set of facilities to a set of locations such that the sum of the assignment and transportation costs is minimized. The facilities may have different space requirements, and the locations may have varying space capacities. Also, multiple facilities may be assigned to each location such that space capacity is not exceeded. In this research, an application of the GQAP is presented for assigning a set of machines to a set of locations on the plant floor. Two meta-heuristics are proposed for solving the GQAP: tabu search (TS) and simulated annealing (SA). In addition, two types of neighborhood structures are considered for each meta-heuristic. A set of 21 test problems, available in the literature, is used to evaluate the performances of the meta-heuristics using one or two neighborhood structures. Computational experiments show that the proposed SA heuristics performed better than the proposed TS heuristics. The SA heuristics obtained results better than those presented in the literature for three of the test problems. On the other hand, the TS heuristics did not perform well for the problems with high space capacity utilization.
Mostafa, Roseline, "Metaheuristics for the Generalized Quadratic Assignment Problem" (2020). Graduate Theses, Dissertations, and Problem Reports. 7717.
Available for download on Tuesday, July 27, 2021