Skip to main content

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

Buy Article:

$59.35 plus tax (Refund Policy)


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.

Keywords: Assembly flowshop; Makespan; PSO; Scheduling; Setup times; Tabu search

Document Type: Research Article


Affiliations: 1: Department of Industrial and Management Systems Engineering, Kuwait University, P.O. Box 5969, Safat, Kuwait 2: Department of Computer Engineering, Kuwait University, P.O. Box 5969, Safat, Kuwait

Publication date: November 15, 2006

More about this publication?

Access Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content
Cookie Policy
Cookie Policy
ingentaconnect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more