Sequencing of an M machine flow shop with setup, processing and removal times separated

In this research, a flow shop scheduling problem in which setup, processing and removal times are separated, with the objective of minimizing makespan, is considered. A tabu search based heuristic is presented for solving the addressed problem. The proposed heuristic begins with the construction of artificial processing times for each operation; then a modified NEH algorithm is used to generate an initial solution, followed by a designed tabu search procedure applied for further improvement of the solution. The proposed heuristic, as well as the existing one, is evaluated in a large number of randomly generated problems. The results of the experimental investigations of the proposed heuristic algorithm and the existing heuristic in meeting the objective of makespan are also reported. It is found that the solution quality of the proposed tabu search heuristic is better than that of the existing heuristic, but for large size problems more computational efforts are needed; however, the CPU time is still acceptable.