Bi-Criteria Scheduling of Scientific Grid Workflows

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 requires a priori knowledge 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. Note to Practitioners-The objective of application scheduling in heterogeneous environments such as computational Grids typically targets the minimization of execution time. This single criterion optimization can have serious limitations leading to inefficient resource utilization, use of unreliable resources, or high economic cost. In practice, a tradeoff between multiple contradicting requirements is usually required, which is often for the scientists hard and non-intuitive to specify in a single objective function. We propose in this paper a new and more user-friendly method for the specification of the bi-criteria scheduling problem that targets the optimization of two contradicting criteria: a primary criterion and a secondary criterion specified as a sliding constraint function of the primary criterion. We design an new bi-criteria scheduling algorithm based dynamic programming as on extension of the multiple-choice knapsack problem. Simulated and real-world experiments demonstrate that the proposed algorithm outperforms two related methods designed for the same problem, the tradeoff being a higher execution time complexity.