A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times

This article deals with the problem of scheduling n jobs on m identical parallel processors with the objective of minimizing the total execution time (makespan). A new three-phase heuristic is proposed for solving this problem. An initial phase constructs a starting solution which is improved, in a...

Full description

Saved in:
Bibliographic Details
Published in:International journal of production economics 1996-06, Vol.43 (2), p.79-89
Main Authors: França, Paulo M., Gendreau, Michel, Laporte, Gilbert, Müller, Felipe M.
Format: Article
Language:English
Subjects:
Economic models
Heuristic
Heuristics
Job shops
Local search
Multiprocessor scheduling
Parallel processing
Searches
Sequential scheduling
Studies
Tabu search
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:This article deals with the problem of scheduling n jobs on m identical parallel processors with the objective of minimizing the total execution time (makespan). A new three-phase heuristic is proposed for solving this problem. An initial phase constructs a starting solution which is improved, in a second phase, by means of a tabu search method. A final phase follows attempting a further improvement in the current solution. Numerical tests in a series of randomly generated problems indicate that the proposed method outperforms a previous heuristic. Comparisons with an exact procedure attest that our method produces good-quality solutions in reasonable running times.
ISSN:0925-5273
1873-7579
DOI:10.1016/0925-5273(96)00031-X