A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search

The parallel machine scheduling problem with unrelated machines is studied where the objective is to minimize the maximum makespan. In this paper, new local search algorithms are proposed where the neighborhood search of a solution uses the ''efficiency'' of the machines for each job. It is shown that this method yields better solutions and shorter running times than the more general local search heuristics.