Evolutionary heuristics and an algorithm for the two-stage assembly scheduling problem to minimize makespan with setup times

Evolutionary heuristics and an algorithm for the two-stage assembly scheduling problem to minimize makespan with setup times

0.00 Avg rating0 Votes
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: ,
Keywords: heuristics, heuristics: ant systems, heuristics: tabu search
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.