Truncated branch-and-bound guided meta-heuristics for the unrelated parallel machine scheduling problem

In this paper, we consider the problem of scheduling a number of jobs on a number of unrelated parallel machines in order to minimize the makespan. We develop two heuristic approaches, i.e. a genetic algorithm and a tabu search algorithm and the hybridization of these heuristics with a truncated branch-and-bound procedure. This hybridization is made in order to accelerate the search process to near-optimal solutions. The branch-and-bound procedure will check whether the solutions obtained by the meta-heuristics can be scheduled within a tight upper bound. We compare the performances of these heuristics on standard data sets available in the literature. Moreover, the influence of the different heuristic parameters is examined as well. The computational experiments reveal that the hybrid heuristics are (almost) able to compete with the best known results from the literature.