You should rewrite subroutines in the metaheuristic with lower computational complexity, using better data structures and algorithms, considering your problem. Depends on the problem you are solving, different metaheuristics can perform better. You can search for better parameter values when setting up your approach, as well as refine the constructive heuristic or local search. If you are using a language as C or C++, then you can also compile your code with optimization flags. However, if you are using a language as Python, be careful on the choice of data structures. In that case, always use native Python built-in modules, as for example, Numpy to perform array operations. Avoid using lists, dicts and loops. It slows down you code. A good start point is to search literature related to you problem to see how it is solved. After that, using a proper tool, you can propose and implement yours.

Thank you Éverton Santi

Wether you have multiple local search operators, you can also try changing the order in which they are executed by adding for example a probability of choosing a certain move to diversify your solutions and maybe also improve your bounds by avoiding local minima.

Thank you, Diego Martino