Solving the flow shop problem by parallel tabu search
- 26 June 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 17, 189-194
Abstract
We present a parallel tabu search algorithm for the permutation flow shop sequencing problem with the objective of minimizing the flowtime. We propose a neighbourhood using so-called blocks of jobs on a critical path and a backtrace jump method. By computer simulations it is shown that the performance of the proposed algorithm is comparable with the random heuristic technique discussed in literature. Another interesting property is the fact that the speedup of parallel implementation is equal or even greater than p, where p is the number of processors.Keywords
This publication has 19 references indexed in Scilit:
- New block properties for the permutation flow shop problem with application in tabu searchJournal of the Operational Research Society, 2001
- A fast tabu search algorithm for the permutation flow-shop problemEuropean Journal of Operational Research, 1996
- Modified simulated annealing algorithms for the flow shop sequencing problemEuropean Journal of Operational Research, 1995
- A genetic algorithm for flowshop sequencingComputers & Operations Research, 1995
- Improving the Efficiency of Tabu Search for Machine Sequencing ProblemsJournal of the Operational Research Society, 1993
- Some efficient heuristic methods for the flow shop sequencing problemEuropean Journal of Operational Research, 1990
- Simulated annealing for permutation flow-shop schedulingOmega, 1989
- A heuristic algorithm for the m-machine, n-job flow-shop sequencing problemOmega, 1983
- A New Algorithm of Solving the Flow — Shop Problem1982
- Optimal two‐ and three‐stage production schedules with setup times includedNaval Research Logistics Quarterly, 1954