Originally posted by: felycite28

Hello everyone ,
I want to get your ideas about a topic which makes me confused. After applying a local search to escape from local minima we apply perturbation. In scheuling problems the most common way to do it is to choose two  random machines or jobs and swap them. After this swap, the found solution might not be feasible so it will do another swap. My question is it might be endless loop,  should I break this loop after a certain trial, (then the perturbation will be useless) . What do you think ? or is there anyone who applied this method, how you applied it? Thank you

I think it is expected that after a random perturbation you get an infeasible solution. If that happens, I see two options:

1. Go back to the current local minimum and try another random perturbation. Repeat this until you hit some limit or find another feasible solution.
2. Apply some sort of repair algorithm to repair the infeasibility. If that does not succeed within reasonable time then either stop or do 1.

So in some cases you just will have to give up because you cannot find another feasible solution within reasonable time. At that point local search has to stop with the current best solution.

If restoring feasibility is hard for your problem then maybe you can try tabu search to escape the local minimum? Tabu search does not make big jumps in the search space like random perturbation but it maintains feasibility.