Iterated local search, iterated greedy and applications

Iterated local search and iterated greedy are two stochastic local search methods. The first one iterates through perturbation phases and local searches, while the second one iterates through destruction/construction phases and optionally through local searches. The destruction/construction phase in iterated greedy can be consider as a perturbation in iterated local search that leads to many commonalities between these two methods. However, iterated greedy can function without the local search phase. In this article, we review the two methods and detail their main principles. After some experiments with these methods on the permutation flow-shop problem, we review recent applications where these two methods have been successfully employed. We then delve into the historical development of these approaches, which reveals that many methods with different names have been proposed, but they ultimately align with one of these two approaches.