## 4 The Concept of GORBA for Fast Rescheduling
### Memetic Optimization  
Hybridizations of an Evolutionary Algorithm with one or more heuristics or local searchers are known to perform significantly better than each algorithm alone [37]. Two forms of hybridization are used frequently: The seeding of the start population with heuristic results as already applied and the incorporation of heuristic improvement in the process of offspring creation. The latter type is also called Memetic Algorithm (MA), a term coined by [PERSON] [39]. Figure 3 shows the pseudo code of a standard EA (light grey) with its memetic extension marked by a dark grey background. In Figure 4 the heuristic or local searcher, called _meme_, improves either all or the best offspring of a mating. Based on suited heuristics or local searchers (LS), MAs have been applied successfully to such different domains as continuous, mixed-integer, or combinatorial optimization or combinations thereof [37, 40, 41, 42]. An up-to-date survey on Memetic Computing can be found in [43]. The advantage of a performance increased by factors of ten and more is compensated by the disadvantage that the choice of suited memes is crucial to success and that additional strategy parameters are introduced. These strategy parameters control the intensity of local search, the frequency of meme application, and the selection of offspring to be treated by a meme, see [44, 45]. In Figure 4, most of these parameters are hard coded like the search intensity of the meme by an iteration limit or by a termination threshold. The frequency of meme application is simply set to each pairing while the offspring selection can be steered by the parameter _all_improvement_ to some extent. Both disadvantages mentioned above can be overcome by an adaptive parameter control and meme selection as described for example in [24, 40, 41]. Of course, good candidates for a set of memes must still be chosen manually and the adaptation figures out, which are better in which stage of the evolutionary process. Another question which must be answered when an EA is expanded to an MA is whether the solution found by the meme should be coded back to the chromosome (Lamarckian evolution) or not (Baldwin evolution). The observed disadvantage of Lamarckian evolution is the danger of premature convergence of the population [46, 47]. As we use the diffusion model described above, which already promotes genotypic diversity by niching, we found Lamarckian evolution to perform better than its Baldwinian counterpart [40, 48]. Thus, Figure 4 contains the code for the chromosome update of an accepted and improved offspring. For scheduling, it is not so easy to define suitable local searchers as for other combinatorial problems. For example, for the well-known Travelling Salesman Problem, it is easy to decide whether a small change of the tour is beneficial or not without recalculating the complete tour. In contrast to that, a small change like the selection of a different resource or the swap of the sequence of two grid jobs cannot be judged without setting up the complete allocation matrix. Thus, the usage of local searchers is more costly for a scheduling application in general and for the GORBA problem in particular than for many other combinatorial tasks. The experiments will show whether the price of evaluations paid to assess the results of local search justifies their benefit of improving solutions found so far by the evolution. We suggest and compare four different local searchers: Three are aimed at finding a better grid job sequence by shifting the grid jobs of too late application jobs to the left (_i.e._, start them earlier) in two different ways or by shifting the grid jobs of application jobs with a large time reserve to the right (_i.e._, start them later). All shifts are done such that no precedence violations occur. These three LS are inspired by the _gap reduction_ approach used e.g., in [49] and the consideration of the critical path, see e.g., [50].