Evolving Dispatching Rules for solving the Flexible Job-Shop Problem

Abstract

We solve the flexible job shop problem (FJSP) by using dispatching rules discovered through genetic programming (GP). While simple priority rules (SPR) have been widely applied in practice, their efficacy remains poor due to lack of a global view. Composite dispatching rules (CDR) have been shown to be more effective as they are constructed through human experience. In this paper, we employ suitable parameter and operator spaces for evolving CDRs using GP, with an aim towards greater scalability and flexibility. Experimental results show that CDRs generated by our GP framework outperforms the SPRs and CDRs selected from literature in 74% to 85% of FJSP problem instances.