Loading...
Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem
Sels, Veronique Coelho, José Dias, Antonio Manuel Vanhoucke, Mario
Sels, Veronique
Coelho, José
Dias, Antonio Manuel
Vanhoucke, Mario
Citations
Altmetric:
Publication Type
Journal article with impact factor
Editor
Supervisor
Publication Year
2015
Journal
Computers and Operations Research
Book
Publication Volume
53
Publication Issue
Jan
Publication Begin page
107
Publication End page
117
Publication Number of pages
Collections
Abstract
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 three heuristic approaches, i.e., a genetic algorithm, a tabu search algorithm and a 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 a standard dataset 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 able to compete with the best known results from the literature.
Research Projects
Organizational Units
Journal Issue
Keywords
Machine Scheduling, SAT