71 | | * single point crossover |
72 | | * 3 types of mutation: |
| 73 | |
| 74 | '''Genetic operators''' |
| 75 | |
| 76 | a. ''Single Point Crossover'' |
| 77 | |
| 78 | The crossover operator for a chromosome representation used follows the following steps: |
| 79 | a. a cut position is randomly selected ( in the above example the cut point is chosen between genes four and five) and for each chromosome results a head and a tail segment; |
| 80 | b. the first offspring is obtained by joining the head segment of the first parent with the combination of the tail segments both parents; more specific, for each gene the task is taken from the first parent and the assigned task is taken from the parent; |
| 81 | c. the second offspring is obtain the same way, using the head segment of the first parent and the combination of tail segments of both parents, but this time, the tasks are taken from the second parent while the assigned processors are taken from the first parent |
| 82 | |
| 83 | b ''Simple Gene Mutation'' |
| 84 | |
| 85 | First is selected a chromosome and a randomly selected gene is changed by assigning the task described by the gene to a new processor with the earliest start time. |
| 86 | |
| 87 | c. ''Swap Gene Mutation'' |
| 88 | |
| 89 | It is selected a processor that is assigned to run at least two jobs with topological level. Then are randomly selected two tasks with the same topological level assigned to the current processor and the tasks are interchanged if the first task to execute has less children then the second one |
| 90 | |
| 91 | d. ''Topological Hyper-Mutation'' |
| 92 | |
| 93 | Whenever a chromosome is affected by this type of mutation, a node from the free node list is randomly selected. Its current topological level is increased and its position in the chromosome is modified in order to reveal the new topological order. Then, all direct predecessors of the selected node are investigated to decide whether they became free floating nodes. If they do, they are inserted in free floating node list corresponding to the current chromosome. If the modified node is no longer a free floating node list (its topological level is equal to the minimum topological level of its successors minus 1), it is removed from the list. |