DEVELOPMENT OF HYBRID META-HEURISTIC ALGORITHM FOR SOLVING NP-HARD COMBINATORIAL OFFICE SPACE ALLOCATION (OSA) PROBLEM IN A NIGERIA UNIVERSITY
No Thumbnail Available
Date
2018-05
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
UNIVERSITY OF ILORIN
Abstract
Office Space Allocation (OSA) is a major problem in higher institutions of learning. As a result of this problem, most of the demanding entities (staff) are wrongly allocated. The problem of OSA is considered to be Non-Polynomial (NP)-Hard combinatorial optimization problem which has been attended to by different researchers in the field of Artificial Intelligence (AI) and Operations Research (OR). Due to its combinatorial nature, several methods have been proposed, which include mathematical, heuristic and meta-heuristic methods. Considering the various methods available, meta-heuristic algorithms in their combinatorial forms need to be developed and tested for solving OSA in Nigeria Universities. Since the hybridization of the meta-heuristic algorithms considered in this research is not yet in existence, this study aimed at developing a hybrid meta-heuristic algorithms of Tabu search and Artificial Bee Colony in solving OSA problems using University of Ilorin as a case study. The objectives of the study were to; (i) formulate a mathematical objective function model for OSA problem and calculate penalty weight; (ii) adapt the algorithms to the problem of OSA; (iii) hybridize Artificial Bee Colony (ABC) algorithm with Tabu Search algorithm to solve OSA problem; and (iv) evaluate the algorithms using Halstead’s complexity measures.
The research adopted a five-phase method. These phases included collection of dataset from the Faculty of Communication and Information Sciences, University of Ilorin, as a sample for mathematical modelling for solving OSA problem in terms of the objective function and the constraints. The methodology phases were adaptation of Artificial Bee Colony, Genetic and Tabu search meta-heuristic algorithms for the OSA problem, hybridization of ABC and Tabu Search algorithms to enhance the performance of the allocation, and a comparative study of the hybrid algorithms using halstead’s complexity measures.
The findings of the study were that:
i. the ABCgave lower penalty weight of 1678.3 when compared with 3885, 4036.6 and 1838.3 of hybrid, Tabu and genetic algorithms respectively;
ii. when Tabu, ABC and genetic algorithms were adapted to the problem of OSA, the Tabu gave better result in term of time used. Tabu used 1231secs against 3114.8secs of ABC and 4256.3secs of genetic;
iii. the hybrid algorithm of Tabu and ABC gave better result when compared with the three algorithms in the second finding in term of time used to solve the OSA problem. The hybrid used 616.62secs against 1231s, 3114.8s and 4256.3s of Tabu, ABC and genetic respectively; and
iv. the halstead’s complexity measure such as program vocabulary, program length, program volume, program intelligence and program difficulty were used to compare the performance of all the algorithms and the hybrid algorithm gave the best result.
The hybridized meta-heuristic algorithm and mathematical model developed was effective in solving the OSA problem and the use of population based algorithm enhanced the performance in allocating all entities to their respective offices. The hybrid algorithm also outperformed other existing algorithms considering the time used and the penalty weight. The study recommended the use of more hybridized algorithms in solving the problem of OSA in Nigeria Universities.
Description
Keywords
Office Space Allocation (OSA), Non-Polynomial (NP)-Hard combinatorial optimization problem, Artificial Bee Colony (ABC) algorithm, Hybridization, Hybrid meta-heuristic algorithms, NIGERIAN UNIVERSITY