Genetic Programming for Production Scheduling. An Evolutionary Learning Approach

Foreword
Preface
Acknowledgements
Contents
Acronyms
List of Figures
List of Tables
Part I Introduction
1 Introduction
	1.1 Production Scheduling
	1.2 Machine Learning
		1.2.1 Training Set and Test Set
		1.2.2 Types of Machine Learning Tasks
		1.2.3 Machine Learning Paradigms
	1.3 Evolutionary Learning and Genetic Programming
		1.3.1 Evolutionary Computation
		1.3.2 Genetic Programming
	1.4 Framework of Genetic Programming for Production Scheduling
	1.5 Interpretable Machine Learning
	1.6 Terminology
	1.7 Organisation of the Book
2 Preliminaries
	2.1 Job Shop Scheduling
	2.2 Exact, Heuristic, and Hyper-heuristic Approaches
	2.3 Hyper-heuristics in Evolutionary Learning
	2.4 Scheduling Heuristics for Job Shop Scheduling
	2.5 Genetic Programming for Production Scheduling Heuristics
		2.5.1 Advantages of Genetic Programming for Production Scheduling
		2.5.2 Overall Process of Genetic Programming for Job Shop Scheduling
		2.5.3 Extracting High-Level Heuristic from Low-Level Heuristics
	2.6 Evaluations of Genetic Programming Hyper-heuristics
	2.7 Chapter Summary
Part II Genetic Programming for Static Production Scheduling Problems
3 Learning Schedule Construction Heuristics
	3.1 Challenges and Motivations
	3.2 Algorithm Design and Details
		3.2.1 Meta-algorithm for Schedule Construction
		3.2.2 Representations of Scheduling Construction Heuristics
		3.2.3 Fitness Evaluation
		3.2.4 Proposed Genetic Programming Algorithm
	3.3 Empirical Study
		3.3.1 Parameter Settings
		3.3.2 Datasets
		3.3.3 Performance of Learned Heuristics
		3.3.4 Further Analyses
	3.4 Chapter Summary
4 Learning Schedule Improvement Heuristics
	4.1 Challenges and Motivations
	4.2 Algorithm Design and Details
		4.2.1 Meta-algorithm for Iterative Dispatching Rules
		4.2.2 Representation of IDRs
		4.2.3 Enhancing IDRs with Variable Neighbourhood Search
	4.3 Empirical Study
		4.3.1 Comparing IDR Variants and Schedule Construction Heuristics
		4.3.2 Influence of kmax on IDR-VNS
	4.4 Chapter Summary
5 Learning to Augment Operations Research Algorithms
	5.1 Challenges and Motivations
	5.2 Constraint Programming Model for Job Shop Scheduling Problems
	5.3 Algorithm Design and Details
		5.3.1 Representation
		5.3.2 Evaluation Mechanism and Fitness Function
		5.3.3 Genetic Operations
		5.3.4 Pre-selection of Promising Programs
	5.4 Empirical Study
		5.4.1 Datasets
		5.4.2 Parameter Settings
		5.4.3 Performance Metrics
		5.4.4 Results
		5.4.5 Further Analyses
		5.4.6 Examples of Evolved Variable Selectors
	5.5 Chapter Summary
Part III Genetic Programming for Dynamic Production Scheduling Problems
6 Representations with Multi-tree and Cooperative Coevolution
	6.1 Challenges and Motivations
	6.2 Algorithm Design and Details
		6.2.1 Genetic Programming with Cooperative Coevolution
		6.2.2 Genetic Programming with Multi-tree Representation
	6.3 Experiment Design
		6.3.1 Simulation Model
		6.3.2 Comparison Design
		6.3.3 Parameter Settings
		6.3.4 Experiment Configuration
	6.4 Results and Discussions
		6.4.1 Quality of the Learned Scheduling Heuristics
		6.4.2 Size of Learned Scheduling Heuristics
		6.4.3 Training Time
	6.5 Chapter Summary
7 Efficiency Improvement with Multi-fidelity Surrogates
	7.1 Challenges and Motivations
	7.2 Algorithm Design and Details
		7.2.1 Framework of the Algorithm
		7.2.2 Knowledge Transfer
		7.2.3 Algorithm Summary
	7.3 Experiment Design
		7.3.1 Comparison Design
		7.3.2 Specialised Parameter Settings of Genetic Programming
	7.4 Results and Discussions
		7.4.1 Training Time
		7.4.2 Quality of Learned Scheduling Heuristics
		7.4.3 Effectiveness of Knowledge Transfer Mechanism
	7.5 Further Analyses
		7.5.1 Number Analysis of Multi-fidelity Surrogate Models
		7.5.2 Sensitivity Analysis of Knowledge Sharing Ratio
	7.6 Chapter Summary
8 Search Space Reduction with Feature Selection
	8.1 Challenges and Motivations
	8.2 Algorithm Design and Details
		8.2.1 Two-stage Genetic Programming with Feature Selection
		8.2.2 Individual Adaptation Strategies and Genetic Programming Feature Selection
		8.2.3 Algorithm Summary
	8.3 Experiment Design
		8.3.1 Comparison Design
		8.3.2 Specialised Parameter Settings of Genetic Programming
	8.4 Results and Discussions
		8.4.1 Quality of Learned Scheduling Heuristics
		8.4.2 Rule Size
		8.4.3 Number of Unique Features
		8.4.4 Training Time
	8.5 Further Analyses
		8.5.1 Selected Features
		8.5.2 Insights of Learned Scheduling Heuristics
	8.6 Chapter Summary
9 Search Mechanism with Specialised Genetic Operators
	9.1 Challenges and Motivations
	9.2 Algorithm Design and Details
		9.2.1 Framework of the Algorithm
		9.2.2 Subtree Importance Measure Based on Feature Importance
		9.2.3 Subtree Importance Measure Based on the Behaviour Correlation
		9.2.4 Crossover with Recombinative Guidance
		9.2.5 Algorithm Summary
	9.3 Experiment Design
		9.3.1 Comparison Design
		9.3.2 Specialised Parameter Settings of Genetic Programming
	9.4 Results and Discussions
		9.4.1 Quality of the Learned Scheduling Heuristics
		9.4.2 Depth Ratios of Selected Subtrees
		9.4.3 Correlations of Selected Subtrees
		9.4.4 Probability Difference
		9.4.5 Training Time
	9.5 Further Analysis
		9.5.1 Number of Invalid Crossover Operations
		9.5.2 Sizes of Learned Scheduling Heuristics
		9.5.3 Insight of Learned Scheduling Heuristics
		9.5.4 Occurrences of Features
	9.6 Chapter Summary
Part IV Genetic Programming for Multi-objective Production Scheduling Problems
10 Learning Heuristics for Multi-objective Dynamic Production Scheduling Problems
	10.1 Challenges and Motivations
	10.2 Algorithm Design and Details
		10.2.1 Representation
		10.2.2 Multi-objective Genetic Programming Algorithm
		10.2.3 Simulation Models for Dynamic Job Shop Scheduling Problems
		10.2.4 Benchmark Heuristics
		10.2.5 Statistical Analysis
	10.3 Empirical Study
		10.3.1 MOGP Performance with Single Objective
		10.3.2 MOGP Performance with Multiple Objectives
	10.4 Further Analyses
		10.4.1 Learned Pareto Front
		10.4.2 Robustness of Learned Heuristics
	10.5 Chapter Summary
11 Cooperative Coevolution for Multi-objective Production Scheduling Problems
	11.1 Challenges and Motivations
	11.2 Algorithm Design and Details
		11.2.1 Representations
		11.2.2 Cooperative Coevolution MOGP for Dynamic Job Shop Scheduling
		11.2.3 Genetic Operators
		11.2.4 Parameters
		11.2.5 Job Shop Simulation Model
		11.2.6 Performance Measures for MOGP Methods
	11.3 Empirical Study
		11.3.1 Pareto Front of Learned Scheduling Heuristics
		11.3.2 Comparison to Heuristics Combining Existing DRs and Dynamic DDARs
		11.3.3 Comparison to Heuristics Combining Existing DRs and Regression-Based DDARs
		11.3.4 Further Analysis
	11.4 Chapter Summary
12 Learning Scheduling Heuristics for Multi-objective Dynamic Flexible Job Shop Scheduling
	12.1 Challenges and Motivations
	12.2 Algorithm Design and Details
		12.2.1 Genetic Programming Multi-objective with NSGA-II Strategy
		12.2.2 Genetic Programming Multi-objective with SPEA2 Strategy
	12.3 Experiment Design
		12.3.1 Comparison Design
		12.3.2 Specialised Parameter Settings of Genetic Programming
	12.4 Results and Discussions
		12.4.1 Quality of Learned Scheduling Heuristics
		12.4.2 Generalisation of Learned Scheduling Heuristics
		12.4.3 Consistency of Rule Behaviour
		12.4.4 Insight of the Distribution of Learned Scheduling Heuristics
	12.5 Chapter Summary
Part V Multitask Genetic Programming for Production Scheduling Problems
13 Multitask Learning in Hyper-Heuristic Domain with Dynamic Production Scheduling
	13.1 Traditional Evolutionary Multitask Learning Algorithms
	13.2 Challenges and Motivations
	13.3 Algorithm Design and Details
		13.3.1 Framework of the Algorithm
		13.3.2 Knowledge Sharing Among Tasks
		13.3.3 Algorithm Summary
	13.4 Experiment Design
		13.4.1 Multitask Dynamic Flexible Job Shop Scheduling Task Definition
		13.4.2 Comparison Design
		13.4.3 Specialised Parameter Settings of Genetic Programming
	13.5 Results and Discussions
		13.5.1 Adaptation of MFEA to Genetic Programming in Dynamic Scheduling
		13.5.2 Quality of Learned Scheduling Heuristics
		13.5.3 Insight of Learned High-Level Scheduling Heuristics
	13.6 Chapter Summary
14 Adaptive Multitask Genetic Programming for Dynamic Job Shop Scheduling
	14.1 Challenges and Motivations
	14.2 Algorithm Design and Details
		14.2.1 Framework of the Algorithm
		14.2.2 Task Relatedness Measure
		14.2.3 Assisted Task Selection Strategy
	14.3 Experiment Design
		14.3.1 Comparison Design
		14.3.2 Specialised Parameter Settings of Genetic Programming
	14.4 Results and Discussions
		14.4.1 Quality of Learned Scheduling Heuristics
		14.4.2 Relatedness Between Tasks
		14.4.3 Selected Assisted Tasks
		14.4.4 Training Time
	14.5 Further Analyses
		14.5.1 Insights of Learned Scheduling Heuristics
		14.5.2 Population Diversity Versus Knowledge Transfer
		14.5.3 Is It Good to Always Choose the Most Related Task?
	14.6 Chapter Summary
15 Surrogate-Assisted Multitask Genetic Programming for Learning Scheduling Heuristics
	15.1 Challenges and Motivations
	15.2 Algorithm Design
		15.2.1 Framework of the Algorithm
		15.2.2 Surrogate Model
		15.2.3 Knowledge Sharing with Surrogate
		15.2.4 Algorithm Summary
	15.3 Experiment Design
		15.3.1 Comparison Design
		15.3.2 Specialised Parameter Settings of Genetic Programming
	15.4 Results and Discussions
		15.4.1 Quality of Learned Scheduling Heuristics
		15.4.2 Effectiveness of Constructed Surrogate Models
		15.4.3 Effectiveness of Diversity Preservation
		15.4.4 Individual Allocation for Tasks
	15.5 Further Analyses
		15.5.1 Sizes of Learned Scheduling heuristics
		15.5.2 Insight of Learned Scheduling Heuristics
	15.6 Chapter Summary
Part VI Conclusions and Prospects
16 Conclusions and Prospects
	16.1 Main Conclusions
	16.2 Further Discussions and Future Prospects
Appendix  References
Index