×
Ivanović, Marija; Savić, Aleksandar; Urošević, Dragan; Dugošija, Djordje

A new variable neighborhood search approach for solving dynamic memory allocation problem. (English) Zbl 1460.90211

Yugosl. J. Oper. Res. 28, No. 3, 291-314 (2018).
Summary: 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.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
05C90 Applications of graph theory
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Keywords:

dynamic memory allocation problem; combinatorial optimization; meta-heuristics; variable neighborhood search
Cite Review PDF
Full Text: DOI

References:

[1] 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.
[2] Hanafi, S., Lazi´c, J., Mladenovi´c, N., Wilbaut, C., Cr´evits, I., “New variable neighbourhood search based 0-1 MIP heuristics”,Yugoslav Journal of Operations Research, 25 (3) (2015) 343-360. · Zbl 1474.90301
[3] Hansen, P., Mladenovi´c, N., “An introduction to variable neighborhood search”,Meta-heuristics, Springer, Boston, MA, 1999, 433-458. · Zbl 0985.90095
[4] Hansen, P., Mladenovi´c, N., P´erez, J.A.M,. “Variable neighbourhood search: methods and applications”,Annals of Operations Research, 175 (1) (2010) 367-407. · Zbl 1185.90211
[5] Hansen, P., Mladenovi´c, N., “Variable neighborhood search: Principles and applications”,European journal of operational research, 130 (3) (2001) 449-467. · Zbl 0981.90063
[6] Hansen, P., Mladenovi´c, N.,Developments of variable neighborhood search, Essays and surveys in metaheuristics, Springer, 2002, 415-439. · Zbl 1017.90130
[7] Hansen, P., Mladenovi´c, N.,Variable neighbourhood search, Handbook of Metaheuristics, Springer, Boston, MA, 2003, 145-184. · Zbl 1102.90371
[8] Ivanovi´c, M., Dugoˇsija, D., Savi´c, A., Uroˇsevi´c, D., “A new integer linear formulation for a memory allocation problem”, in proc.Balcor 2013, XI Balcan Conference on Operational Research, 2013, 284 288.
[9] Mladenovi´c, N., Hansen, P., “Variable neighborhood search”,Computers & Operations Research, 24 (11) (1997) 1097-1100. · Zbl 0889.90119
[10] Mladenovi´c, N., “A variable neighborhood algorithm - a new metaheuristic for combinatorial optimization”,Optimization Weeks, 112 (1995) 112-112.
[11] 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.
[12] 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. · Zbl 1358.90162
[13] 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.
[14] Soto, M., Sevaux, M., Rossi, A., Laurent, J.,Memory Allocation Problems in Embedded Systems: Optimization Methods, John Wiley & Sons, Inc, Hoboken, NJ, 2013. · Zbl 1317.90067
[15] S´anchez-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. · Zbl 1362.68260
[16] S´anchez-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.
[17] 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.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.