Minimizing makespan in a blocking flowshop using genetic algorithms
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
We consider the problem of minimizing the makespan of n jobs in an m-machine flowshop operating without buffers. Since there is no intermediate storage, 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 flowshop' 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 solve large size restricted slowdown flowshop problems of which blocking flowshop problems are a special case. Abadi has established a connection between the blocking flowshop problem 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 operations. We utilize this concept to evaluate the makespan (fitness) of the solutions generated by genetic algorithms. Computational results indicate that a genetic algorithm with optimized parameters for controlling the evolution of solutions consistently performs significantly better than the heuristic for blocking flowshops developed in a recent Ph.D. thesis by Abadi. The comparison is made for the problems with sizes up to 20 machines and 250 jobs.
