## 2 Related Work  
When we developed the concept of GORBA, a comparable problem could not be found in the published literature, see e.g., [6, 7]. A literature review included in a paper by [PERSON] _et al._ published in 2006 [8] came to a similar result. They found only a few publications that dealt with more than one criterion in scheduling and, if so, they were mostly based on single-machine problems. But after that, more papers dealing with multi-objective optimization were published, especially in the field of grid job computing. In a review article published two years later [9] it is reported that most of them are based on two criteria like e.g., the work of [PERSON] _et al._[10] and that in most cases just one criterion is really optimized while the other serves as a constraint like in [11] or [12]. The latter can handle about 30 jobs within one hour only, which is probably due to the complex chromosomes they used. A true multi-objective optimization based on a modified weighted sum aiming at a compromise between resource owners and users was performed by [PERSON] _et al._[13]. They used contradicting criteria like costs and several time-related objectives, but their solution did not handle workflows. Two years later, they extended their procedure to hierarchical two-level scheduling and reported about experiments with workloads of about 500 independent jobs [14]. A multi-layer approach is also favored by [PERSON] _et al_. [15] and they also work with individual jobs, for which the makespan is minimized. [PERSON] _et al._[16] extended their recent work in 2010 to parallel tasks and the integration of the standard multi-objective genetic algorithm NSGA-II [17]. For that they used advanced reservations of multiple computing nodes. They experimented with 1500 jobs, which were grouped into 60 sets and assigned optimization preferences. [PERSON] _et al._[18] schedule workflows instead of single jobs to constrained resources as we do and discuss the analogy with the resource-constrained project scheduling problem (RCPSP), see also [7]. They stress and discuss the similarity of the problem with other application fields and introduce an algorithm for finding feasible solutions. The approach of [PERSON] _et al._ published in 2008 [19] comes closest to ours, with the following common features: Usage of a Memetic Algorithm, a structured population, the concept of fast and permanent replanning, multi-criteria optimization, and experiments based on workloads and heterogeneous resource pools of up to half the size of ours. The main differences concern the question of what is scheduled, the extent of using heuristics, the number of criteria considered and their contrariness, the MA concept, and the kind of structured population. Our work is based on scheduling multiple workflows of grid jobs, while [PERSON] _et al._ consider independent single jobs only. We use more heuristics for seeding the initial population and for resource allocation, as we have found that heuristic resource selection outperforms its evolutionary counterpart, if the runtime for planning is strictly limited [20]. In [19] two criteria, _makespan_ and _average flow time_, are used, which can be regarded as less conflicting than _time_, _costs_, and _utilization rate_, which will be explained in more detail in Section 3. In contrast to [19], we use adaptive MAs, as explained in Section 4.4, to steer local search parameters as well as the frequency of local search usage. In [19] this is controlled manually, which is more costly. Furthermore, one of our MAs is an adaptive Multimeme Algorithm, where all local procedures work together and compete for application as will be described later. The last difference concerns population structures and the concept of cellular MAs based on the diffusion model, for which two authors of [19] claim that they are \"a new class of algorithms\" [21]. Since the early 90's, our EA has been using a ring-shaped diffusion model, which is described in more detail in Section 4.2.1 [22, 23, 24].