A new variable neighborhood search approach for solving dynamic memory allocation problem
DOI:
https://doi.org/10.2298/YJOR161015018IKeywords:
dynamic memory allocation problem, combinatorial optimization, metaheuristics, variable neighborhood searchAbstract
This paper is devoted to the Dynamic Memory Allocation Problem (DMAP) in embedded systems. The existing Integer Linear Programing (ILP) formulation for DMAP is improved, and given that there are several metaheuristic approaches for solving the DMAP, a new metaheuristic approach is proposed and compared with the former ones. Computational results show that our new heuristic approach outperforms the best algorithm found in the literature regarding quality and running times.References
Atienza, D., Mamagkakis, S., Poletti, F., Mendias, J. M., Catthoor, F., Benini, L., Soudris, D., “Efficient system-level prototyping of power-aware dynamic memory managers for embedded systems”, INTEGRATION, the VLSI journal, 39 (2) (2006) 113–130.
Hanafi, S., Lazić, J., Mladenović, N., Wilbaut, C., Crévits, I., “New variable neighbourhood search based 0-1 MIP heuristics”, Yugoslav Journal of Operations Research, 25 (3) (2015) 343-360.
Hansen, P., Mladenović, N., “An introduction to variable neighborhood search”, Meta-heuristics, Springer, Boston, MA, 1999, 433-458.
Hansen, P., Mladenović, N., Pérez, J.A.M., “Variable neighbourhood search: methods and applications”, Annals of Operations Research, 175 (1) (2010) 367-407.
Hansen, P., Mladenović, N., “Variable neighborhood search: Principles and applications”, European Journal of Operational Research, 130 (3) (2001) 449–467.
Hansen, P., Mladenović, N., Developments of variable neighborhood search, Essays and surveys in metaheuristics, Springer, 2002, 415–439.
Hansen, P., Mladenović, N., Variable neighbourhood search, Handbook of Metaheuristics, Springer, Boston, MA, 2003, 145-184.
Ivanović, M., Dugošija, D., Savić, A., Urošević, D., “A new integer linear formulation for a memory allocation problem”, in proc. Balcor 2013, XI Balcan Conference on Operational Research, 2013, 284-288.
Mladenović, N., Hansen, P., “Variable neighborhood search”, Computers & Operations Research, 24 (11) (1997) 1097–1100.
Mladenović, N., “A variable neighborhood algorithm - a new metaheuristic for combinatorial optimization”, Optimization Weeks, 112 (1995) 112-112.
Sevaux, M., Rossi, A., Soto, M., Duarte, A., Martí, R., “Grasp with ejection chains for the dynamic memory allocation in embedded systems”, Soft Computing, 18 (8) (2014) 1515–1527.
Soto, M., Rossi, A., Sevaux, M., “A mathematical model and a metaheuristic approach for a memory allocation problem”, Journal of Heuristics, 18 (1) (2012) 149–167.
Soto, M., Rossi, A., Sevaux, M., “Two iterative metaheuristic approaches to dynamic memory allocation for embedded systems”, European Conference on Evolutionary Computation in Combinatorial Optimization, Springer, Berlin, Heidelberg, 2011, 250–261.
Soto, M., Sevaux, M., Rossi, A., Laurent, J., Memory Allocation Problems in Embedded Systems: Optimization Methods, John Wiley & Sons, Inc, Hoboken, NJ, 2013.
Sánchez-Oro, J., Sevaux, M., Rosi, A., Martí, R., Duarte, A., “Solving dynamic memory allocation problems in embedded systems with parallel variable neighborhood search strategies”, Electronic Notes in Discrete Mathematics, 47 (2015) 85–92.
Sánchez-Oro, J., Sevaux, M., Rosi, A., Martí, R., Duarte, A., “Improving the performance of embedded systems with variable neighborhood search”, Applied Soft Computing, Elsevier, 53 (2017) 217-226.
Wuytack, S., Catthoor, F., Nachtergaele, L., De Man, H., “Power exploration for data dominated video applications”, in: Proceedings of the 1996 international symposium on Low power electronics and design, IEEE Press, 1996, 359–364.
Downloads
Published
Issue
Section
License
Copyright (c) 2018 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
