A genetic algorithm for an industrial multiprocessor flow shop scheduling problem with recirculation

We propose in this paper an effective heuristic algorithm to solve a scheduling problem that comes from industry. The workshop is an hybrid flow shop with recirculation and the problem is to perform jobs between a release date and a due date, in order to minimize the weighted number of tardy jobs. Firstly, an integer linear programming formulation of the problem is proposed, then a lower bound, a greedy algorithm and a genetic algorithm are described as approximate methods. To evaluate these heuristics, experiences on instances like industrial ones are computed, and show the efficiency of the genetic algorithm.