Application of gene expression programming on dynamic job shop scheduling problem

In this paper, we consider a dynamic job shop scheduling problem (DJSSP) with job release dates. In such a problem, jobs arrive over time and are unknown in advance and they can not be scheduled before their arrivals. We apply gene expression programming (GEP), a new search technique based on evolutionary principle, on the scheduling problem to automatically construct efficient scheduling rules (SRs), which can generate high-quality schedules for the problem. A novel encoding scheme is proposed which prevents the length of chromosomes from increasing dramatically with the increase of the size of scheduling problems. And a new decoding scheme is also proposed which transfers a GEP chromosome into a schedule for each problem instance. The proposed GEP-based method is valuated for its solution quality. According to computational experiment results, the method is proved to be able to construct effective SRs for DJSSP with job release dates.