Truncated branch-and-bound guided meta-heuristics for the unrelated parallel machine scheduling problem
AbstractIn 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Ghent University, Faculty of Economics and Business Administration in its series Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium with number 11/753.
Length: 2 pages
Date of creation: Oct 2011
Date of revision:
This paper has been announced in the following NEP Reports:
You can help add them by filling out this form.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Nathalie Verhaeghe).
If references are entirely missing, you can add them using this form.