## 4 The Concept of GORBA for Fast Rescheduling
### Evolutionary Optimization
#### 4.2.2 Two Gene Models  
For GORBA, two different gene models were investigated in detail. For both, each grid job is represented by one gene and the sequence of genes within the chromosome determines the scheduling sequence. A grid job gene consists of at least a unique grid job identifier (_id_ in Figure 1). The first gene model _GM1_ is based on genes that determine each resource of a grid job by a corresponding gene parameter. This means that every grid job gene has as many parameters as resources have to be allocated or co-allocated. Figure 1 shows an example of such a gene marked by a light blue background. A schedule is constructed from a chromosome by performing the following steps for each gene in the order of their appearance:  
Figure 2: Diffusion model based on overlapping neighborhoods, called demes. The demes of the two individuals “M” and “N” show minimal overlapping, while “X” and “Y” overlap maximally.  
1. If the grid job has no predecessors, its earliest start time equals the earliest start time of its application job. Otherwise, the latest end time of its predecessors is used as earliest start time.
2. Calculate the duration of the grid job on the given resources.
3. Search for a free time interval of the calculated duration beginning at the earliest start time from step 1 on all selected resources and allocate them.  
This gene model covers the complete search space, as every scheduling sequence and every resource assignment is possible. Both are controlled by evolution.  
The second gene model _GM2_ is aimed at a faster improvement in the beginning of the search by a reasonable reduction of the search space. It replaces the evolutionary selection of resources per grid job by the evolutionary selection of one of the three RAS heuristics, which is applied to all grid jobs. This is done by the removal of the parameters of the grid job genes and an additional RAS gene. Figure 1 shows this RAS gene, which is interpreted first independently of its position within the chromosome. The crossover operators are modified to pass on the RAS gene of the better parent. For chromosome interpretation, the first step of GM1 is used again:  
1. If the grid job has no predecessors, its earliest start time equals the earliest start time of its application job. Otherwise, the latest end time of its predecessors is used as earliest start time.
2. According to the RAS selected by the RAS gene, a list of alternatives is produced for every primary resource.
3. Beginning with the first resources of the lists, the duration of the job is calculated and it is searched for a free time slot for the primary resource and its depending ones, beginning at the earliest start time of step 1. If no suitable slot is found, the resources at the next position of the lists are tried.
4. The resources found are allocated to the grid job with the calculated time frame.  
This scheduling mechanism ensures that the precedence rules are adhered to for chromosomes, which contain no gene representing a direct predecessor of a grid job \(O_{ij}\), which is located after the gene of that grid job. Alternatively, a repair is performed as described in the next section. An example of the relationship between chromosomes and workflows is shown in Figure 1. The rationale of this reduction of the search space is as follows: Due to the limited time frame, evolutionary search is stopped (long) before convergence anyway, provided that the amount of grid jobs is large enough, _i.e._, 100 grid jobs or more. This means that any attempt to approach the global optimum is in vain and that it is therefore meaningful to increase fitness improvement in an early stage of the search at the costs of lower achievable quality in the long run. Figure 3 illustrates this idea. In fact, results from early experiments confirm this assumption [36].