An Effective Chromosome Representation for Evolving Flexible Job Shop Schedules

Abstract. As the Flexible Job Shop Scheduling Problem (or FJSP) is strongly NP-hard, using an evolutionary approach to find near-optimal solutions re-quires effective chromosome representations as well as carefully designed pa-rameters for crossover and mutation to achieve efficient search. This paper pro-poses a new chromosome representation and a design of related parameters to solve the FJSP efficiently. The results of applying the new chromosome repre-sentation for solving the 10 jobs x 10 machines FJSP are compared with three other chromosome representations. Empirical experiments show that the pro-posed chromosome representation obtains better results than the others in both quality and processing time required