## 3 Formal Problem Definition  
For completeness, we will give here a formal definition of the problem, which was already published in [20]. The notation used is common to scheduling literature [6, 7] to facilitate comparisons with other scheduling problems. Given are a set \(M=\{M_{1},\ \ldots,\ M_{m}\}\) of resources, a set \(J=\{J_{1},\ \ldots,\ J_{r}\}\) of \(r\) application jobs, and a set \(O\) of grid jobs. The \(n\) grid jobs of application job \(J_{i}\) are denoted \(O_{iI}\),..., \(O_{in}\). The following functions are given:  
* A precedence function \(p\):\(O\)\(\times\)\(O\)\(\rightarrow\)\(\{\)_TRUE_, _FALSE_\(\}\) for the grid jobs;
* An assignment function \(\mu\):\(O\)\(\rightarrow\)\(P(P(M))\) from grid jobs to resource sets. \(P(M)\) is the power set of \(M\), _i.e._, the set of all possible combinations of resources. Thus, \(O_{ij}\) can be performed by a feasible element from \(P(M)\). Then \(\mu_{ij}\)\(\in\)\(P(P(M))\) is the set of all possible combinations of resources from \(M\), which together are able to perform the grid job \(O_{ij}\);
* A function \(t\):\(O\)\(\times\)\(P(M)\)\(\rightarrow\)\(\Re\), which gives for every grid job \(O_{ij}\) the time needed for the processing on a resource set \(R_{ij}\)\(\in\)\(\mu_{ij}\);
* A cost function, \(c\):\(\Re\)\(\times\)\(P(M)\)\(\rightarrow\)\(\Re\), which gives for every time \(z\)\(\in\)\(\Re\)  the costs per time unit of the given resource set. Optimization is done by choosing suitable start times \(s(O_{ij})\)\(\in\)\(\Re\)  and resource allocations \(R_{ij}\)\(\in\)\(\mu_{ij}\). A solution is valid, if the following two restrictions are met:  
1. All grid jobs are planned and resources are allocated exclusively: \[\forall O_{ij}:\exists s(O_{ij})\in\Re,R_{ij}\in\mu_{ij}:\forall M _{k}\in R_{ij}:\] \[M_{k}\;\;\text{is in }[\,s(O_{ij});s(O_{ij})+t(O_{ij},R_{ij})\,]\; \text{exclusively allocated by }\;O_{ij}\,.\] (1)
2. Precedence relations are adhered to: \[\forall i,j\
eq k:p(O_{ij},O_{ik})\Rightarrow s(O_{ik})\geq s(O_{ij})+t(O_{ ij},R_{ij})\] (2) A violation of the two following soft constraints is treated by penalty functions as described below. 1. All application jobs \(J_{i}\) have a cost limit \(c_{i}\), which must be observed: \[\forall J_{i}:c_{i}\geq\sum_{j=1}^{n}\,\int\limits_{s(O_{ij})+(O_{ij},R_{ij}) }^{s(O_{ij})+t(O_{ij},R_{ij})}\,dz\] (3)
2. All application jobs \(J_{i}\) have due dates \(d_{i}\), which must be adhered to: \[\forall J_{i}:d_{i}\geq s(O_{in})+t(O_{in},R_{in})\;\;\text{where }O_{in}\;\text{is the last grid job of }J_{i}\] (4)  
There are four penalty functions, each of which yields a value of one (no violation) dropping to zero, which stands for maximum overrun. For each constraint, the number of violating application jobs \(nv\) and the amount of violation is assessed as _pfn_ and _pfa_ as shown in Equation (5):  
\[\textit{pfn}=\frac{r-nv}{r}\;\;\;\;\;\;\;\;\;\;\;\;\textit{pfn}=e^{2\,\text{ ln}(\textit{fj})_{\text{$\times$}}(a-t)}\;\;\;\;\;\;a=\frac{I}{nv}\sum_{i=I}^{nv} \frac{val_{i}}{m_{i}} \tag{5}\]  
where \(r\) is the total number of application jobs, \(val_{i}\) is the required time or costs of the violating application job \(i\) and \(m_{i}\) is its maximum allowed time or costs respectively. The constants of the exponential function yield a value of one third for \(a=1.5\) which corresponds to an average overrun of 50% of the allowed value \(m_{i}\). These penalty values are multiplied by the weighted sum of the following five criteria, thus resulting in the final objective value or _fitness_ as it is called in the context of Evolutionary Algorithms. The first two criteria reflect more the interests of the users, while the criteria 3 and 4 meet more the demands of the resource providers. The fifth criterion is an auxiliary criterion, which helps to reduce the makespan of application jobs. The weights of the five criteria are given in brackets:  
1. _costs_ of the application jobs (35%) are measured with respect to the budget of each application job given by the user and averaged. 2.