## 3 Background
### Genetic Programming and Generating DRs  
GP is a metaheuristic method based on the concept of natural evolution [12]. It starts with a set, called the population, of randomly generated solutions, usually referred to as individuals. These individuals are evaluated using the fitness function, which calculates the fitness of each individual, i.e., a numerical measure of how well the individual solves a particular problem by optimising a certain criterion. GP then iteratively applies a series of genetic operators to these individuals in search of better solutions until a certain termination criterion is met. The operators that GP applies are selection, crossover, and mutation. With the selection operator, GP selects better individuals for the crossover operator and worse individuals to be eliminated from the population. The selected individuals are then used by the crossover operator, which combines their properties and creates a new individual that is potentially better than the individuals from which it was created. In addition, the newly created individual can be mutated with a certain probability to introduce random changes. The purpose of the mutation operator is to help the algorithm bypass local optima and restore lost genetic material in the population. This newly created individual then replaces one of the underperforming individuals in the population. With such a strategy, GP iteratively attempts to obtain better solutions through crossover and mutation and place them into the population, eliminating poor-quality individuals. The variant of the selection algorithm used in this study is described in Algorithm 2 [48], and the flow diagram of the algorithm is shown in Figure 1.  
```
1:Randomly create the population \(P\) and evaluate all individuals in it
2:while termination criterion is not met do
3: Randomly select 3 individuals from the population that form a tournament
4: Select the two better individuals
5: Crossover the selected individuals and create a new individual
6: Mutate the newly created individual with a certain probability
7: Evaluate the newly created individual
8: Replace the worst individual from the tournament with the newly created individual
9:endwhile
```  
**Algorithm 2** The GP algorithm  
Figure 1: Flowchart of the GP algorithm. As already mentioned, solutions in GP are coded as expression trees consisting of function and terminal nodes. The function nodes are the inner nodes in the tree and represent various mathematical, logical, or other types of operations. The terminal nodes, on the other hand, appear as leaf nodes in the tree and represent different features of the problem. Therefore, the definition of terminal nodes is one of the most important decisions that must be made when applying GP to any problem. Through the evolutionary process, GP searches for the most appropriate expression to solve a given problem. GP has been successfully used as a hyperheuristic method [14; 49] to automatically generate heuristics for various types of combinatorial optimisation problems, such as scheduling problems [50; 51], the travelling salesman problem [52; 53], vehicle and arc routing problems [54; 55; 56], the container relocation problem [57], and the cutting stock problem [15; 58]. When used to generate DRs for scheduling problems, GP has the task of finding a suitable PF that can be used by the DR to evaluate scheduling decisions. Each individual represents a potential PF, which is then used by the SGS, as defined in Algorithm 1, to evaluate its effectiveness for a given set of problem instances. To be able to meaningfully rank the various decisions in the scheduling problem, e.g., which job to schedule next, GP must have access to all relevant features of the problem via its terminal nodes. Therefore, the set of terminal nodes must contain relevant problem characteristics, such as the processing times of jobs, their due dates, weights, and so on.