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.

Mathematical and Computer Modelling
Erasmus School of Economics

Piersma, N., & van Dijk, W. (1996). A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search. Mathematical and Computer Modelling, 24(9), 11–19. doi:10.1016/0895-7177(96)00150-1