A genetic algorithm and particle swarm optimization for no-wait flow shop problem with separable setup times and makespan criterion

作者：Samarghandi Hamed^*; ElMekkawy Tarek Y

来源：International Journal of Advanced Manufacturing Technology, 2012, 61(9-12): 1101-1114.

DOI：10.1007/s00170-011-3766-8

• Flow shop scheduling
• No-wait
• Separable setup
• Makespan
• Genetic algorithm
• Particle swarm optimization
• Factoradics

This paper considers the problem of no-wait flow shop scheduling, in which a number of jobs are available for processing on a number of machines in a flow shop context with the added constraint that there should be no waiting time between consecutive operations of a job. Each operation has a separable setup time, meaning that the setup time of an operation is independent on the previous operations; and the machine can be prepared for a specific operation and remain idle before the operation actually starts. The considered objective function in this paper is the makespan. The problem is proven to be NP-hard. In this paper, two frameworks based on genetic algorithm and particle swarm optimization are developed to deal with the problem. For the case of no-wait flow shop problem without setup times, the developed algorithms are applied to a large number of benchmark problems from the literature. Computational results confirm that the proposed algorithms outperform other methods by improving many of the best-known solutions for the test problems. For the problems with setup time, the algorithms are compared against the famous 2-Opt algorithm. Such comparison reveals the efficiency of the proposed method in solving the problem when separable setup times are considered.

• 出版日期2012-8