Sub-Group Quadratic Assignment Problem: A Variant Of Quadratic Assignment Problem with Model Development and Comparison

Authors

  • Sharifah Shuthairah Syed-Abdullah , Syariza Abdul-Rahman , Aida Mauziah Benjamin , Ku-Ruhana Ku-Mahamud , Antoni Wibowo

Abstract

Numerous research onQuadratic Assignment Problem (QAP) and its variants have been proposed in the past to reflect
real-world problems. One of the real problems related to QAP is facilities are required to be assigned to certain
locations due to their purposes. A set of assignment has to be made accordingly based on their requirements and allow
complexities of the problem to be reduced. Hence, this study introducesa variant of QAP which is called as Sub-Group
QAP (SGQAP) with the objective to minimize the assignment cost by taking into consideration the flow and distance
between the facilities and locations. SGQAP represents real-world problem, especially in dealing with specific
requirements of some facilities to a specific set of locations. In this study, mathematical model of the problem is
developed and a dataset of SGQAP with various sizes of group is introduced and solved. The results of SGQAP are
compared with QAP and QAP with Fixed Assignment (QAPFA) in terms of objective function and running timein order
to show variation in the solution quality when different condition is applied. The computational results show that the
solution quality of SGQAP is better than QAPFA but not for QAP since the complexity was reduced by grouping
facilities into a set of assignment. This isdue to the need to fulfill some preferences in the assignment which contribute to
assignment cost. SGQAP is a new variant of QAP which is relatedto group assignment based on preferences, hence it
contributes as a new practical problem which gives more flexibility and effectiveness in the assignment while maximizing
the preferences.

Published

2020-03-31

Issue

Section

Articles