A genetic algorithm and particle swarm optimization for no-wait flow shop problem with separable setup times and makespan criterion |
| |
Authors: | Hamed Samarghandi Tarek Y ElMekkawy |
| |
Affiliation: | 1. Department of Mechanical and Manufacturing Engineering, University of Manitoba, 75A Chancellors Circle, Winnipeg, MB, Canada, R3T5V6
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|