## 1 Introduction  
A _computational grid_ consists of a mass of heterogeneous resources such as computing nodes, storage devices, application software and their licenses, operating systems, and communication links. All these resources usually differ in size, performance, and costs, and their availability may be restricted to certain hours of the day or days of the week, _etc._ Furthermore, the prices may differ at different times reflecting that e.g., computer time is cheaper at night or on the weekend. Summarizing, the grid can be characterized as a huge virtualized computing center, the resources of which are requested by grid jobs originated by grid users; cf. [1]. Typically, the task a user wants to be solved by the grid consists of several single _grid jobs_ organized as a workflow, which has the form of a directed acyclic graph. Thus, we will distinguish between elementary _grid jobs_ requesting one or more resources (e.g., the license for a specific software tool, an appropriate operating system, and a suitable hardware to run on) and _application jobs_ representing the workflow of the grid jobs belonging together. The resulting scheduling problem is of greater complexity than the well-known job-shop scheduling problem due to the following reasons:  
* Scheduling of workflows of parallel branches instead of just a linear sequence of operations (grid jobs);
* Co-allocation of resources for each grid job instead of only one machine (resource) per operation;
* Restricted availability of resources;
* Heterogeneous resource alternatives due to different cost performance ratios as well as different performances or capacities instead of alternatives of uniform resources;
* Multi-objective target function with conflicting criteria like _costs_, _execution times_, and _rate of utilization_. This is necessary to fulfill the different needs of resource providers and users. As the classical job-shop scheduling problem is both, NP-complete and a special case of the outlined task, the grid job scheduling problem is NP-complete as well. Therefore and because of the limited time available for planning, only approximate solutions can be expected. In Section 3, we will give a formal definition of the problem. A widely used solution to grid job management is the application of queuing systems. As they yield only sub-optimal solutions for nontrivial workloads, we proposed advanced planning and reservation at an early stage, firstly as a concept in 2005 [2] and a year later first results were reported [3]. Planning requires, among other things, knowledge about the expected execution times and information about the performance of the computing nodes. The latter must be standardized to be comparable and is therefore a requirement of the grid information system used. Execution times can be derived either from former executions of the same task with different data, from experience, or must be estimated. In contrast to many other scheduling problems, a grid job schedule is usually executed to a more or less small extent only. Grid computing is a highly dynamic process, as changes in jobs and resources occur permanently. The following events belong to these _replanning inducements_:  
* Arrival of new application jobs;
* Cancellation of waiting or already begun application jobs;
* Crash of grid jobs resulting in the termination of the remaining workflow;
* New resources;* Breakdown of resources;
* Changes of the availability or the cost model of resources. Thus, a permanent replanning process is required. The time for planning should be much shorter than the average of the job execution time. As grid jobs are more likely to last hours rather than seconds, we consider a small time frame of a few minutes to be defensible. Thus, we consider three minutes to be an acceptable amount of time for coming up with a revised plan. Jobs already running or started within this time will not be rescheduled, provided that their resources are still in operation.