## 5 Experiments
### Benchmarks  
Benchmarks for the assessment of scheduling procedures can either be derived from real applications or generated synthetically. Practical relevance seems to be an argument in favor of the first approach, but benchmarks extracted from real data tend to inherit those application scenarios which were dominant during data collection or which were typical of a given user domain [13,54]. Additionally, characteristic properties are difficult to control and consequently, we use synthetic benchmarks. Examples are given in [55,56], who use homogeneous resources and only one application job. As we consider a more general application with heterogeneous resources and many workflows, we started early to develop our own benchmark set as described in [57]. The complexity of a benchmark certainly depends on its size, _i.e._, the number of grid and application jobs as well as the number of resources. Besides these more general figures, the degree of mutual dependencies of the grid jobs \(D\) and the degree of freedom in the selection of resources \(R\) are used to characterize a benchmark more precisely. \(D\) is defined as follows. Figure 5: Pseudo code of the Adaptive Multimeme Algorithm AMMA. The adaptive memetic part is marked by a dark grey background. For details of the EA part see Figure 4.  
\[D=\frac{\sum_{i=1}^{n}{pred_{i}}}{pred_{\max}}\qquad pred_{\max}=\frac{n(n-1)}{2} \tag{8}\]  
where \(n\) is the number of all grid jobs of all application jobs and \(pred_{i}\) is the number of all direct or indirect predecessors of grid job \(i\). The degree of resource alternatives \(R\) is given by Equation (9). \[R=\frac{\sum_{i=1}^{n}{m_{i}}}{n\cdot m} \tag{9}\]  
where \(m\) is the number of all usable resources and \(m_{i}\) is the number of all alternatively usable resources of grid job \(i\). A small value of \(R\) corresponds to a small mean possibility of selection of resources per grid job. By using small (s) and large (l) values for \(R\) and \(D\), four benchmark classes are defined, which are labeled _sRsD_, _sRID_, _lRsD_, and _IRID_. They range from a low degree of resource alternatives and parallelization (_sRID_) to many resource alternatives and a high level of parallelization (_lRsD_). For these four classes, benchmarks are constructed for given values of \(n\) and \(m\). The complexity of the planning problem also depends on user requirements for the application jobs like cost budgets and latest completion times. An approach to measuring these properties will be presented in the next paragraph. For the first experiments, we used the attribute \"free of budget violations and processed in time\" to distinguish between a successful and an unsuccessful schedule. This differentiation was applied as an additional measure besides the fitness introduced in Section 3 to compare the schedulers. For this purpose, these two constraints of a benchmark were adjusted in such a way that the heuristics for the first planning phase just could not solve them although it was possible. All scheduling algorithms and their settings are assessed in the experiments by the achieved _success rate_ as described before and the resulting _fitness_. For the second benchmark set used for the new experiments reported in Section 5.2.3, further measurands were introduced for the time and cost constraints in order to ensure their homogeneity when varying the loads. The _time_ and _cost reserve_ of an application job are calculated based on the usage of average fast and expensive resources, the critical path of the workflow, and on the average off-time of resources, as described in detail in [58]. They are given as percentages of the corresponding time frame and budget. Of course, these figures are based on an \"empty grid\", _i.e._, there are no delays due to other jobs or there is no need to use e.g., more expensive resources in order to meet the due date.