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. | Yugoslav Journal of Operations Research 28 (2018), Number 3, 291–314 DOI: A NEW VARIABLE NEIGHBORHOOD SEARCH APPROACH FOR SOLVING DYNAMIC MEMORY ALLOCATION PROBLEM ´ Marija IVANOVIC Faculty of Mathematics, University of Belgrade, Serbia marijai@ ´ Aleksandar SAVIC Faculty of Mathematics, University of Belgrade, Serbia asavic@ ˇ ´ Dragan UROSEVI C Mathematical Institute, SANU, Belgrade, Serbia draganu@ ˇ Djordje DUGOSIJA Faculty of Mathematics, University of Belgrade, Serbia dugosija@ Received: October 2016 / Accepted: May 2018 Abstract: 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. Keywords: Dynamic Memory Allocation Problem, Combinatorial Optimization, Metaheuristics, Variable Neighborhood Search. MSC: 90C59, 05C90, 68T20. 292 ´c, ´c, ´c, / A New VNS approach 1. INTRODUCTION Dedicated computational systems within a larger mechanical or electrical system, usually with real time constraints, or the embedded systems, represent an integral part of a large number of devices, ranging from portable devices up to large industrial, medical, and military structures. Minimizing energy consumption while increasing reliability and performance present a major challenge for engineers. Therefore, designers want to find a balance between the architecture cost and its power consumption [1]. Power consumption of a given application can be reduced by using data access parallelization, which leads us to the definition of the Dynamic .
