Integrated Research in GRID Computing- P11:The deployment process for adaptive Grid applications does not finish when the application is started. Several activities have to be performed while the application is active, and actually the deployment system must rely on at least one permanent process or daemon. | Scheduling Workflows with Budget Constraints 191 in defining execution costs of the tasks of the DAG. However as indicated by studies on workflow scheduling 2 7 12 it appears that heuristics performing best in a static environment . HBMCT 8 have the highest potential to perform best in a more accurately modelled Grid environment. In order to solve the problem of scheduling optimally under a budget constraint we propose two basic families of heuristics which are evaluated in the paper. The idea in both approaches is to start from an assignment which has good performance under one of the two optimization criteria considered that is makespan and budget and swap tasks between machines trying to optimize as much as possible for the other criterion. The first approach starts with an assignment of tasks onto machines that is optimized for makespan using a standard algorithm for DAG scheduling onto heterogeneous resources such as HEFT 10 or HBMCT 8 . As long as the budget is exceeded the idea is to keep swapping tasks between machines by choosing first those tasks where the largest savings in terms of money will result in the smallest loss in terms of schedule length. We call this approach as LOSS. Conversely the second approach starts with the cheapest assignment of tasks onto resources that is the one that requires the least money . As long as there is budget available the idea is to keep swapping tasks between machines by choosing first those tasks where the largest benefits in terms of minimizing the makespan will be obtained for the smallest expense. We call this approach gain. Variations in how tasks are chosen result in different heuristics which we evaluate in the paper. The rest of the paper is organized as follows. Section 2 gives some background information about DAGs. In Section 3 we present the core algorithm proposed along with a description of the two approaches developed and some variants. In Section 4 we present experimental results that evaluate the .
