The drift towards new challenges in Grid computing including scientific workflow management implies the need for new, robust, multicriteria scheduling algorithms that can be applied by the user in an intuitive way. Currently existing bi-criteria scheduling approaches for scientific workflows are usually restricted to certain criterion pairs and require the user to define his preferences either as weights assigned each criterion or as fixed constraints defined for one criterion. The first approach has the drawback that combining multiple criteria into a single objective function is not always intuitive to the end-user, while the second requiresa prioriknowledge about the result of the first criteria scheduling result. We propose a new bi-criteria scheduling specification method defining for the secondary criterion a sliding constraint as a function of the primary criterion. We model the problem as an extension of the multiple-choice knapsack problem and propose a general bi-criteria scheduling heuristic called dynamic constraint algorithm (DCA) based on dynamic programming. We show through simulation that in most of the experimental cases DCA outperforms two existing algorithms designed for the same problem at the expense of an increased execution time, which is still relatively low for workflows of medium size. Finally, we confirm our simulation results for a real-world hydrological application executed in the Austrian Grid environment.

The drift towards new challenges in grid computing, including the utility grid paradigm and service level agreements based on quality-of-service guarantees, implies the need for new, robust, multi-criteria scheduling algorithms that can be applied by the user in an intuitive way. Multiple scheduling criteria addressed by the related grid research include execution time, the cost of running a task on a machine, reliability, and different data quality metrics. The existing bi-criteria scheduling approaches are usually dedicated for certain criterion pairs only that require the user to define one's preferences either as weights assigned to the criteria or as fixed constraints defined for one of the criteria. These requirements are often not feasible for the user and not suited to the specificity of the multi- criteria scheduling problem. We propose a novel requirement specification method based on a sliding constraint, and we model the problem as an extension of the multiple-choice knapsack problem. We propose a general bi-criteria scheduling heuristic called dynamic constraint algorithm (DCA) based on dynamic programming, dedicated to the problem model defined by us. In the experimental study, we show that in most of the problem variants, DCA outperforms two existing algorithms designed for the same problem. It also shows relatively low scheduling times for workflows of medium size.

Grid economy models have long been considered as a promising alternative for the classical Grid resource management, due to their dynamic and decentralized nature, and because the financial valuation of resources and services is inherent in any such model. In particular, auction models are widely used in the existing Grid research, as they are easy to implement and are shown to successfully manage resource allocation on the Grid market. The focus on the current work is on workflow scheduling in the Grid resource allocation model based on Continuous Double Auctions (CDA). We analyze different scheduling strategies that can be applied by the user to execute workflows in such an environment, and try to identify the general behavioral patterns that can lead to a fast and cheap workflow execution. In the experimental study, we show that under certain circumstances some benefit can be gained by applying an ldquoaggressiverdquo scheduling strategy.

In this paper we present an extension to devise and implement advance reservation as part of the scheduling and resource management services of the ASKALON Grid application development and runtime environment. The scheduling service has been enhanced to offer a list of resources that can execute a specific task and to negotiatewith the resource manager about resources capable of processing tasks in the shortest possible time. We introduce progressive reservation approach which tries to allocate resources based on a fair-share principle. Experiments are shown that demonstrate the effectiveness of our approach, and that reflect different QoS parameters including performance, predictability, resource usage and resource fairness.

We propose a novel approach for bi-criteria scheduling of scientific workflows on the grid, using dynamic programming to balance the trade-off between the two contradicting criteria. We determine the primary and the secondary criterion, and establish a flexible limit for the primary criterion. We identify different classes of criteria and adjust the solution for different variants of the problem