Minimizing makespan in a blocking flowshop using genetic algorithms

We consider the problem of minimizing the makespan of n jobs in an In-machi ne flowshop operating without buffers. Since there is no intermediate stora ge, a job here cannot leave a machine until the machine downstream is free. When that is the case, the job is said to be blocked. This "blocking flows hop" problem is known to be strongly NP-hard for the shop having more than two machines. In this paper, we develop a genetic algorithmic approach to s olve large size restricted slowdown flowshop problems of which blocking flo wshop problems are a special case. Abadi (Flowshop scheduling problems with no-wait and blocking environments: A mathematical programming approach. Ph .D Thesis, Department of Industrial Engineering, University of Toronto, Can ada, 1995) has established a connection between the blocking flowshop probl em and a no-wait flowshop in which jobs do not wait between operations. He uses the idea of deliberately slowing down the processing of certain operat ions. We utilize this concept to evaluate the makespan (fitness) of the sol utions generated by genetic algorithms. Computational results indicate that a genetic algorithm with optimized parameters for controlling the evolutio n of solutions consistently performs significantly better than the heuristi c for blocking flowshops developed in a recent Ph.D. thesis by Abadi. The c omparison is made for the problems with sizes up to 20 machines and 250 job s. (C) 2001 Published by Elsevier Science B.V. All rights reserved.