Automatic design of scheduling policies for dynamic flexible job shop scheduling via surrogate-assisted cooperative co-evolution genetic programming

Abstract

At present, a lot of references use discrete event simulation to evaluate the fitness of evolved rules, but which simulation configuration can achieve better evolutionary rules in a limited time has not been fully studied. This study proposes three types of hyper-heuristic methods for coevolution of the machine assignment rules (MAR) and job sequencing rules (JSR) to solve the DFJSP, including the cooperative coevolution genetic programming with two sub-populations (CCGP), the genetic programming with two sub-trees (TTGP) and the genetic expression programming with two sub-chromosomes (GEP). After careful parameter tuning, a surrogate simulation model is used to evaluate the fitness of evolved scheduling policies (SP). Computational simulations and comparisons demonstrate that the proposed surrogate-assisted CCGP method (CCGP-SM) shows competitive performance with other evolutionary approaches using the same computation time. Furthermore, the learning process of the proposed methods demonstrates that the surrogate-assisted GP methods help accelerating the evolutionary process and improving the quality of the evolved SPs without a significant increase in the length of SP. In addition, the evolved SPs generated by the CCGP-SM show superior performance as compared with existing rules in the literature. These results demonstrate the effectiveness and robustness of the proposed method.

Keywords:

• dynamic flexible job shop scheduling
• hyper-heuristic
• cooperative co-evolution
• genetic programming
• scheduling policies

Acknowledgements

The authors would like to thank Professor Lianyu Zheng for his guidance during the academic writing and Dr Pengcheng Fang for his assistance during the simulation experiment.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notations

DFJSP	=	dynamic flexible job shop scheduling problem
SP	=	scheduling policy
JSR	=	job sequencing rule
MAR	=	machine assignment rule
CCGP	=	cooperative co-evolution genetic programming with two sub-populations
TTGP	=	genetic programming with single population that a GP individual contains two sub-trees
GEP	=	genetic expression programming with two sub-chromosomes
CCGP-SM	=	surrogate-assisted cooperative co-evolution genetic programming with two sub-populations
TTGP-SM	=	surrogate-assisted genetic programming with two sub-trees

ORCID

Yong Zhou http://orcid.org/0000-0002-5129-9159

Additional information

Funding

This work was supported by Beijing Key Laboratory of Digital Design and Manufacturing; Beijing Municipal Education Commission (Build a Project).