GENACE: an efficient cultural algorithm for solving the flexible job-shop problem

Abstract

This work presents an efficient methodology called GENACE for solving the flexible job-shop scheduling problem (or FJSP) with recirculation. We show how CDRs are used to solve the FJSP with recirculation by themselves and to provide a bootstrapping mechanism to initialize GENACE. We then adopt a cultural evolutionary architecture to maintain knowledge of schemata and resource allocations learned over each generation. The belief spaces influence mutation and selection over a feasible chromosome representation. Experimental results show that GENACE obtains better upper bounds for 11 out of 13 benchmark problems, with improvement factors of 2 to 48 percent when compared to results by Kacem et al. (2002), Brandimarte (1993) and of using CDRs alone.