A multiple neighborhood search for dynamic memory allocation in embedded systems

Memory allocation has a significant impact on power consumption in embedded systems. We address the dynamic memory allocation problem, in which memory requirements may change at each time interval. This problem has previously been addressed using integer linear programming and iterative approaches which build a solution interval by interval taking into account the requirements of partial time intervals. A GRASP that builds a solution for all time intervals has been proposed as a global approach. Due to the complexity of this problem, the GRASP algorithm solution quality decreases for larger instances. In order to overcome this drawback, we propose a multiple neighborhood search hybridized with a Tabu Search and enhanced by complex ejection chains. The proposed approach outperforms all previously developed methods devised for the dynamic memory allocation problem.