A Genetic algorithm to minimize the makespan in the k-stage hybrid flow shop scheduling problem

摘要

In this paper, we consider the k-stage hybrid flow shop scheduling problem where the parallel machines are identical. Our study aims to provide a good approximate solution to this specific problem with the makespan (C_(max)) minimization as the objective function. Considering the success of the Genetic Algorithms (GA) developed for scheduling problems, we apply this metaheuristic to deal with this problem. We develop a GA with a new crossover operator. Indeed, it is a combination of two other crossover operator proposed in the literature. The design of our GA is different compared to the classical structure of the genetic algorithm especially in the encoding of solutions. For the calibration of our metaheuristic parameters, we conduct several experimental designs. Our algorithm is tested on a well known benchmark in the literature. The numerical results show that the proposed genetic algorithm is an efficient approach for solving the k-stage hybrid flow shop problem. Furthermore, this computational study shows that our GA, with the proposed crossover operator gives better results than the two other crossover operators.