Scheduling tasks on unrelated machines: Large neighborhood improvement procedures

Two approximation algorithms are presented for minimizing the makespan of i ndependant tasks assigned on unrelated machines. The first one is based upo n a partial and heuristical exploration of a search tree, which is used not only to build a solution but also to improve it thanks to a post-optimizat ion procedure. The second implements a new large neighborhood improvement p rocedure to an already existing algorithm. Computational experiments show t hat their efficiency is equivalent to the best local search heuristics.