Multi-exchange algorithms for the minimum makespan machine

We address the problem of scheduling independent jobs to identical parallel machines in order to minimize the completion time (makespan). This is a hard problem, for which both constructive and improvement heuristics have been proposed. We describe new local search algorithms, whose neighborhood structure is based on multiple exchanges of jobs among machines. Inspired by the work of Thompson and Orlin (1989) on cyclic transfer neighborhood structures, in these algorithms multiple exchanges are modelled in terms of ``disjoint cycles'' on suitably defined improvement graphs, and improvement moves are obtained by heuristically constructing special disjoint cycles in such auxiliary graphs. The algorithms have been tested on benchmark instances, characterized by uniformly distributed processing times, and on a new class of ``highly non-uniform'' instances, generated by the authors, which seem to be, in some cases, more difficult than the ``uniform'' ones. The algorithms have shown a potential both for generating highly accurate solutions when the running time is not an issue, and for rapidly obtaining good solutions when the running time has to be kept small.