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
- General introduction of job shop scheduling
- Static vs dynamic job shop scheduling
- Flexible vs non-flexible job shop scheduling
- The similarities and differences between different types of job shop scheduling
(2) Introduction of machine learning and genetic programming
- Representation of genetic programming
- Evaluation of genetic programming
- Parent selection in genetic programming
- Genetic operators (i.e., crossover, mutation, and reproduction) of genetic programming
(3) Introduction of genetic programming for job shop scheduling
- Scheduling heuristics for different types of job shop scheduling
- Genetic programming to learn scheduling heuristics
- Set up genetic programming as a hyper-heuristic approach for job shopscheduling (e.g., representations, terminal set and function set)
(4) Surrogate-Assisted genetic programming for job shop scheduling
- Surrogate basic concepts
- Phenotype VS Genotype of genetic programming individuals
- K-nearest neighbour based surrogate for genetic programming
- Simplified model based surrogate for genetic programming
- Collaborative multi-fidelity based surrogates for genetic programming
(5) Genetic programming with feature selection for job shop scheduling
- Feature selection basic concepts
- Feature frequency-based feature selection
- Contribution-based feature selection
(6) Multitask genetic programming for job shop scheduling
- Multitask basic concepts
- Multitask genetic programming based generative hyper-heuristics
- Surrogate-Assisted evolutionary multitask genetic programming
- Adaptive multitask genetic programming
(7) Future directions
- Limitations of existing studies in this field
- Potential solutions to handle the limitations
Learning outcomesThis 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’s 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.
Expected length of the tutorial (2h or 4h): 2h
The level of the tutorial (introductory or advanced): advanced/specialised
Presenters:
Fangfang Zhang is a Postdoctoral Research Fellow in the School of Engineering and Computer Science, Victoria University of Wellington, New Zealand. She has nearly 30 journal and conference papers. Her current research interests include evolutionary computation, hyper-heuristics learning/optimisation, job shop scheduling, and multitask optimization. Fangfang is a member of the IEEE Computational Intelligence Society and Association for Computing Machinery, and has been severing as a reviewer for top international evolutionary computation journals such as the IEEE Transactions on Evolutionary Computation, the IEEE Transactions on Cybernetics, Applied Soft Computing, Computers and Operations Research, Journal of Scheduling and Complex & Intelligent Systems, and conferences including the Genetic and Evolutionary Computation Conference (GECCO) and the IEEE Congress on Evolutionary Computation (CEC). She is also a committee member of the IEEE New Zealand Central Section.
Mengjie Zhang is a Professor of Computer Science, the Head of the Evolutionary Computation Research Group, and the Associate Dean (Research and Innovation) with the Faculty of Engineering, Victoria University of Wellington, New Zealand. His current research interests include artificial intelligence and machine learning, particularly genetic programming, image analysis, feature selection and reduction, job shop scheduling, and transfer learning. He has published over 700 research papers in refereed international journals and conferences.Prof. Zhang is a Fellow of the Royal Society of New Zealand, a Fellow of IEEE and an IEEE Distinguished Lecturer. He was the Chair of the IEEE CIS Intelligent Systems and Applications Technical Committee, the IEEE CIS Emergent Technologies Technical Committee, and the Evolutionary Computation Technical Committee, and a member of the IEEE CIS Award Committee. He is a Vice-Chair of the Task Force on Evolutionary Computer Vision and Image Processing, and the Founding Chair of the IEEE Computational Intelligence Chapter in New Zealand. He is a Fellow of Royal Society of New Zealand, a Fellow of IEEE, and an IEEE Distinguished Lecturer.
Yi Mei is a Senior Lecturer with the School of Engineering and Computer Science, Victoria University of Wellington, New Zealand. He has more than 100 fully referred publications, including the top journals in Evolutionary Computation and Operations Research, such as IEEE Transactions on Evolutionary Computation, IEEE Transactions on Cybernetics, Evolutionary Computation, European Journal of Operational Research, and ACM Transactions on Mathematical Software. His research interests include evolutionary scheduling and combinatorial optimization, machine learning, genetic programming, and hyper-heuristics.Dr. Mei was a Vice-Chair of the IEEE CIS Emergent Technologies Technical Committee and a member of the Intelligent Systems Applications Technical Committee. He is an Editorial Board Member/Associate Editor of three international journals, and a Guest Editor of a special issue of the Genetic Programming and Evolvable Machines journal. He serves as a reviewer of over 30 international journals.
Su Nguyen is a Senior Research Fellow and an Algorithm Lead with the Centre for Data Analytics and Cognition, La Trobe University, Melbourne, Australia. His expertise includes evolutionary computation, simulation optimization, automated algorithm design, interfaces of artificial intelligence/operations research, and their applications in logistics, energy, and transportation. He has more than 70 publications in top evolutionary computation/operations research peer-reviewed journals and conferences. His current research focuses on novel people-centric artificial intelligence to solve dynamic and uncertain planning tasks by combining the creativity of evolutionary computation and power of advanced machine- learning algorithms.
Dr. Nguyen was the Chair of IEEE Task Force on Evolutionary Scheduling and Combinatorial Optimisation from 2014 to 2018 and is a member of the IEEE CIS Data Mining and Big Data Technical Committee. He delivered technical tutorials about evolutionary computation and artificial intelligence based visualization at Parallel Problem Solving from Nature Conference in 2018 and IEEE World Congress on Computational Intelligence in 2020. He served as an Editorial Member of Complex and Intelligence Systems and the Guest Editor of the special issue on Automated Design and Adaption of Heuristics for Scheduling and Combinatorial Optimization in Genetic Programming and Evolvable Machines journal.