An Effective Hybrid Genetic Algorithm for Hybrid Flow Shops with Sequence Dependent Setup Times and Processor Blocking

Abstract

Hybrid flow-shop or flexible flow shop problems have remained subject of intensive research over several years. Hybrid flow-shop problems overcome one of the limitations of the classical flow-shop model by allowing parallel processors at each stage of task processing. In many papers the assumptions are generally made that there is unlimited storage available between stages and the setup times are neglected or considered independent from sequences of jobs. In this paper we study the hybrid flow shop problems with sequence dependent setup times and processor blocking. We present an effective hybrid genetic algorithm with some state-of-the-art procedures for these NP-hard problems to minimize total completion time or makespan. We established a benchmark to draw an analogy between the performance of our algorithm and RKGA. The obtaining results clearly show the superiority performance of our algorithm.