Paper Info
Title
Genetic Programming Based Hyper-heuristics for Dynamic Job Shop Scheduling: Cooperative Coevolutionary Approaches.
Abstract
Job shop scheduling (JSS) problems are optimisation problems that have been studied extensively due to their computational complexity and application in manufacturing systems. This paper focuses on a dynamic JSS problem to minimise the total weighted tardiness. In dynamic JSS, attributes of a job are only revealed after it arrives at the shop floor. Dispatching rule heuristics are prominent approaches to dynamic JSS problems, and Genetic Programming based Hyper-heuristic (GP-HH) approaches have been proposed to automatically generate effective dispatching rules for dynamic JSS problems. Research on static JSS problems shows that high quality ensembles of dispatching rules can be evolved by a GP-HH that uses cooperative coevolution. Therefore, we compare two coevolutionary GP approaches to evolve ensembles of dispatching rules for dynamic JSS problems. First, we adapt the Multilevel Genetic Programming (MLGP) approach, which has never been applied to JSS problems. Second, we extend an existing approach for a static JSS problem, called Ensemble Genetic Programming for Job Shop Scheduling (EGP-JSS), by adding “less-myopic” terminals that take job and machine attributes outside of the scope of the attributes commonly used in the literature. The results show that MLGP for JSS evolves ensembles that are significantly better than single “less-myopic” rules evolved using GP with only little difference in computation time. In addition, the rules evolved using EGP-JSS perform better than the MLGP-JSS rules, but MLGP-JSS evolves rules significantly faster than EGP-JSS.
Year
Venue
Field
2016
EuroGP
Mathematical optimization,Tardiness,Job shop scheduling,Computer science,Cooperative coevolution,Flow shop scheduling,Genetic programming,Heuristics,Artificial intelligence,Machine learning,Computation,Computational complexity theory
DocType
Citations 
PageRank 
Conference
6
0.46
References 
Authors
13
6
Name
Order
Citations
PageRank
John Park1233.46
Mei Yi294153.85
Su Nguyen334823.67
Gang Chen 00024142.44
Mark Johnston5623.81
Mengjie Zhang619510.65