A multi-level genetic algorithm for a multi-stage space allocation problem. (English) Zbl 1190.90083

Summary: A new case of space allocation problem is considered. The study is based on a real-world multi-stage hostel space allocation for university students. A multi-level application of genetic algorithm metaheuristic with promising results is presented. Based on the case study, we examined the sensitivity analysis of various genetic algorithm operators in order to establish the baseline for practical deployment. The feasibility rate of the solutions obtained were also determined and presented.


90B80 Discrete location and assignment
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
68T05 Learning and adaptive systems in artificial intelligence


Knapsack; MULKNAP
Full Text: DOI


[1] R. Bai, An investigation of novel approaches for optimising retail shelf space allocation, Ph.D. Dissertation, School of Computer Science and Information Technology, University of Nottingham, UK, 2005
[2] J.D. Landa-Silva, Metaheuristics and multi-objective approaches for space allocation. Ph.D. Dissertation. School of Computer Science and Information Technology, University of Nottingham, UK, 2003
[3] E.K. Burke, P. Cowling, J.D. Landa-Silva, B. McCollum, Three methods to automate the space allocation process in UK universities, in: Proceedings of the 3rd International Conference on the Practice and Theory of Automated Timetabling, PATAT2000, Konstanz, Germany, 2000, pp. 374-393 · Zbl 0987.68974
[4] Adewumi, A.O.; Ayeni, J.O.A; Abass, O.; Fasina, E.P., Some comments on task allocation problem in distributed computing systems, J. comput. sci. appl., 9, 1, 136-145, (2003)
[5] A.O. Adewumi, N. Ihemedu, J.O.A. Ayeni, An evolutionary-based approach to university course time-tabling problem, Poster Session, First Annual Research Conference and Fair, University of Lagos, 9(11) (2005), October
[6] Andresen, M.; Brasel, H.; Morig, M.; Tusch, J.; Werner, F.; Willenius, P., Simulated annealing and genetic algorithms for minimizing Mean flow time in an open shop, Math. comput. modelling, 48, 1279-1293, (2008) · Zbl 1187.90127
[7] Burke, E.K.; Varley, D.B., Automating space allocation in higher education, (), 66-73
[8] Burke, E.K.; Varley, D.B., Space allocation: an analysis of higher education requirements, (), 20-33
[9] E.K. Burke, P. Cowling, J.D. Landa-Silva, On the performance of population-based metaheuristics for the space allocation problem: An extended abstract, in: Proceedings of the 4th Metaheuristics International Conference, MIC 2001, Porto Portugal, 2001, pp. 579-583
[10] Ritzman, L.; Bradford, J.; Jacobs, R., A multiple objective approach to space planning for Academic facilities, J. mgmt. sci., 25, 9, 895-906, (1980)
[11] Benjamin, C.; Ehie, I.; Omurtag, Y., Planning facilities at the university of missoury-rolla, J. interface, 22, 4, 95-105, (1992)
[12] Giannikos, J.; El-Darzi, E.; Lees, P., An integer goal programming model to allocate offices to staff in an Academic institution, J. oper. res. soc., 46, 6, 713-720, (1995) · Zbl 0832.90070
[13] Pisinger, D., An exact algorithm for large multiple knapsack problems, European J. oper. res., 144, 528-541, (1999) · Zbl 0948.90110
[14] Federgruen, A.; Ryzin, G.V., Probabilistic analysis of a generalized bin packing problem and applications, Oper. res., 45, 4, 596-609, (1997) · Zbl 0887.90138
[15] Federal university of technology minna. student affairs department information, available on www.futminna.org/currentstudents/student_affairs.htm. Accessed in October, 2008
[16] Goldberg, D.E., Genetic algorithms in search, optimisation and machine learning, (1989), Addison Wesley
[17] Glover, F., Future paths for integer programming and links to artificial intelligence, Comput. oper. res., 13, 5, 533-549, (1986) · Zbl 0615.90083
[18] Lucasius, C.B.; Kateman, I.G., Understanding and using genetic algorithms — representation, configuration and hybridization (A tutorial), Chemo. intel. lab. syst., 25, 99-145, (1994)
[19] Ramadan, Z.; Jacobs, D.; Grigorov, M.; Kochhar, S., Metabolic profiling using principal component analysis, discriminant partial least squares, and genetic algorithms, Talanta, 68, 1683-1691, (2006)
[20] Sivanandam, S.N.; Deepa, S.N., Introduction to genetic algorithms, (2008), Springer New York · Zbl 1129.90001
[21] D. Corne, H.L. Fang, C. Mellish, Solving the modular exam scheduling problem with genetic algorithms, in: The proceedings of the 6th international conference of industrial and engineering applications of ai and expert system, 1993, pp. 370-373
[22] E. Annevelink, R.A.C.M. Broekmeulen, The Genetic Algorithm applied to Space Allocation Planning in Pot-Plant Nurseries, in: XII International Symposium on Horticultural Economics Acta Hort. (ISHS) 340 (1995) pp. 141-148
[23] J.S. Dean, Staff scheduling by a genetic algorithm with a two-dimensional chromosome, in: E.K. Burke, M. Gendreau, (Eds.), Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling — PATAT, 2008, Montreal, Canada, August 18-22, 2008, p. 15
[24] Kubiak, W.; Sriskandarajah, C.; Zaras, K., A note on the complexity of open shop scheduling problems, Infor, 29, 284-294, (1991) · Zbl 0778.90027
[25] Liu, C.Y.; Bulfin, R.L., Scheduling ordered open shops, Comput. oper. res., 14, 257-264, (1987) · Zbl 0625.90045
[26] M. Obitko, Genetic algorithm — recommendation. Hochschule für Technik und Wirtschaft Dresden (FH) (University of Applied Sciences), Available on http://cs.felk.cvut.cz/ xobitko/ga/recom.html. Accessed in October, 2008
[27] J.E. Baker, Reducing bias and inefficiency in the selection algorithm, in: Proceedings of the Second International Conference on Genetic Algorithms and their Application (Hillsdale), 1987, pp. 14-21
[28] Wikipedia. Genetic Algorithm. Accessed via http://en.wikipedia.org/wiki/Genetic_algorithm in October 2008
[29] W. Kosiński, S. Kotowski, Limit properties of evolutionary algorithms, in: W. Kosiński. Advances in Evolutionary Algorithms, I-Tech Education and Publishing, Vienna, Austria, November 2008, p. 468, ISBN 978-953-7619-11-4
[30] Ross, P.; Hart, E.; Corne, D., Some observations about GA based timetabling. the practice and theory of automated timetabling II, (), 115-129
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.