Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem

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 pro...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2015-01, Vol.53, p.107-117
Main Authors: Sels, Veronique, Coelho, José, Manuel Dias, António, Vanhoucke, Mario
Format: Article
Language:English
Subjects:
Algorithms
Branch & bound algorithms
Genetic algorithms
Heuristic
Heuristic methods
Job shops
Machine scheduling
Mathematical models
Operations research
Parallel processing
Production scheduling
SAT
Scheduling
Studies
Tabu search
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2014.08.002