Article ID: | iaor20071751 |
Country: | United Kingdom |
Volume: | 44 |
Issue: | 22 |
Start Page Number: | 4713 |
End Page Number: | 4735 |
Publication Date: | Jan 2006 |
Journal: | International Journal of Production Research |
Authors: | Allahverdi Ali, Al-Anzi Fawaz S. |
Keywords: | heuristics, heuristics: ant systems, heuristics: tabu search |
In this paper we address the two-stage assembly flowshop scheduling problem with respect to the makespan criterion where setup times are considered as separate from processing times. We formulate the problem and obtain a dominance relation. Moreover, we propose two evolutionary heuristics: a Particle Swarm Optimization (PSO) and a tabu search. We also propose a simple and yet efficient algorithm with negligible computational time. We have conducted extensive computational experiments to compare the two heuristics and the algorithm along with a random solution. The computational analysis indicates that both heuristics and the algorithm perform significantly well. The computational analysis also indicates that PSO is the best and that the difference between the average errors of PSO and the algorithm becomes small as the number of jobs increases, while the computational time of PSO becomes much larger. Moreover, the difference between the two errors becomes even smaller as the number of machines (at the first stage) and the ratio of setup times to processing times becomes smaller. Therefore, PSO is recommended for a number of jobs up to 50, whereas the algorithm is suggested for larger numbers of jobs and larger numbers of machines at the first stage.