Sampling Heuristics for Multi-objective Dynamic Job Shop Scheduling Using Island Based Parallel Genetic Programming

Dynamic job shop scheduling is a complex problem in production systems. Automated design of dispatching rules for these systems, particularly using the genetic programming based hyper-heuristics (GPHH) has been a promising approach in recent years. However, GPHH is a computationally intensive and time consuming approach. Parallel evolutionary algorithms are one of the key approaches to tackle this drawback. Furthermore when scheduling is performed under uncertain manufacturing environments while considering multiple conflicting objectives, evolving good rules requires large and diverse training instances. Under limited time and computational budget training on all instances is not possible. Therefore, we need an efficient way to decide which training samples are more suitable for training. We propose a method to sample those problem instances which have the potential to promote the evolution of good rules. In particular, a sampling heuristic which successively rejects clusters of problem instances in favour of those problem instances which show potential in improving the Pareto front for a dynamic multi-objective scheduling problem is developed. We exploit the efficient island model-based approaches to simultaneously consider multiple training instances for GPHH.