Construct the initial solution S0 ;
S ← S0 ; /* S is the current solution */
S
∗ ← S0 ; /* S
∗ is the best solution so far */
bestValue ← ob jValue(S0) ; /* *bestValue* is the evaluation of S
∗ */
T ← /0 ; /* T is the Tabu list */
nonImprovingStep ← 0 ;
/* *nonImprovingStep* is the number of consecutive non improving iterations */
while bestValue > *lowerbound and we still have time* do N(S) ← all the neighboring solution of S ; S ← the solution in N(S) minimizing the objective ;
if ob jValue(S) < *bestValue* **then** /* The solution found is better than S
∗ */
S
∗ ← S ;
bestValue ← *ob jValue*(S) ;
nonImprovingStep ← 0 ;
else /* The iteration did not improve S
∗ */
nonImprovingStep+ + ;
end Record tabu for the current move in T (delete oldest entry if necessary) ;
if nonImprovingStep = *maxNonImprovingStep* **then**
/* Stuck in a non improving area: time for diversification */
nonImprovingStep ← 0 ;
/* Uniformly chooses the diversification to apply */
d ← *Uni f ormRandom*(1,3) ;
switch *The value of d* do case 1 /* Empties a partition */
Randomly choose a partition p ;
foreach *item i on the partition p* do Choose the partition p 0such that the assignment of i to p 0 minimizes the objective function and p 0 6= p ;
Assign i to the partition p 0; end case 2 /* Random Restarts */
foreach *item i* do Randomly choose a partition p ; Assign i to the partition p ;
end case 3 /* Applies m random moves */
m ← Uni f ormRandom(1,*numberO f Rings*) ;
Apply m moves ;
end end end end Algorithm 5: DMN2