Tutorials: Genetic Programming for Job Shop Scheduling

Job shop scheduling (JSS) is an important combinatorial optimisation problem, which covers a full range of topics and tasks including static JSS, dynamic JSS, flexible JSS, dynamic flexible JSS, from basic research to a huge number of real-world industrial applications. With recent technological advances in internet-of-things, artificial intelligence, and automation, modern production systems are digitalized and more flexible, and production environments can be monitored and diagnosed in real-time. Scheduling in such dynamic and complex environments is challenging since scheduling needs to be more efficient and reactive, and scheduling decisions have to incorporate dynamic information and uncertainty. Instead of manually designing scheduling heuristics and algorithms for each problem, we can use machine learning and hyper-heuristics to automatically learn effective scheduling heuristics from low-level heuristics, characteristics of scheduling problems, and dynamic information from production environments. Among the techniques studied and applied within the research field of JSS, genetic programming (GP), a powerful evolutionary machine learning technique, has been successfully used to learn scheduling heuristics for JSS, especially for dynamic JSS. This automated design approach can significantly reduce the time required to develop solution methods by domain experts and increase the chance of discovering novel and effective scheduling heuristics. Although GP has shown its advantage in learning scheduling heuristics for JSS, GP still has several limitations for handling JSS such as high computational cost and large search space. In addition, most of existing studies focus mainly on single JSS task optimisation, the multiple tasks solving ability of GP has not been explored. The tutorial will introduce the general JSS problem, including the similarities and differences of different types of job shop scheduling. The basic GP will be also introduced. How and why to use genetic programming to learn scheduling heuristics for JSS will be introduced. Different surrogate techniques used in GP for JSS will be introduced with examples. How feature selection techniques can be used in GP for JSS will be described. In addition, how to learn scheduling heuristics for multiple JSS tasks simultaneously will be discussed. In summary, we will show how such techniques can be used to help GP learn scheduling heuristics for JSS. All the techniques mentioned will be introduced with promising results.

This tutorial contains seven parts:
(1) Different types of job shop scheduling and their applications
(2) Introduction of machine learning and genetic programming
(3) Introduction of genetic programming for job shop scheduling
(4) Surrogate-Assisted genetic programming for job shop scheduling
(5) Genetic programming with feature selection for job shop scheduling
(6) Multitask genetic programming for job shop scheduling
(7) Future directions

Learning outcomes. This tutorial targets researchers who are not familiar with GP and/or production scheduling as well as experienced researchers who are interested in special research topics.(1) Researches with a background in machine learning, operations research, industrial engineering, can enjoy this tutorial and explore the interfaces between operations research / optimisation and machine learning.(2) Researchers can gain fundamental understandings of the subjects and incrementally explore different applications and algorithms of this tutorial.(3) Operations research / industrial engineering researchers who are familiar with combinatorial optimisation and production scheduling will find a good transition to refresh their knowledge and get used to machine learning and GP terminologies before exploring hybrid operations research-GP methods, and other applications in dynamic production environments.(4) Machine learning researchers can familiarise themselves with production scheduling applications from this tutorial and understand the basic settings for applying machine learning algorithms to scheduling problems.(5) Advanced applications of machine learning presented will be of great interests for many machine learning researchers. Operations research / industrial engineering / Machine Learning practitioners will find it useful to understand how machine learning can be applied to solve scheduling problems.