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

Sels, Veronique; Coelho, José; Dias, António Manuel; Vanhoucke, Mario

http://hdl.handle.net/10400.2/3446

Use this identifier to reference this record.

Name:	Description:	Size:	Format:
UPMS_140519.pdf		390.42 KB	Adobe PDF	Download

Send Feedback

Authors

Abstract(s)

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 inﬂuence 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.

Keywords

Machine scheduling SAT

URI

http://hdl.handle.net/10400.2/3446

Citation

Coelho, José [et al.] - Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problema. "Computers & Operations Research" [Em linha]. ISSN 0305-0548. Vol. 53 (2015), p. 1-30