Academic
Publications
Bi-criteria Scheduling of Scientific Workflows for the Grid

Bi-criteria Scheduling of Scientific Workflows for the Grid,10.1109/CCGRID.2008.21,Marek Wieczorek,Stefan Podlipnig,Radu Prodan,Thomas Fahringer

Bi-criteria Scheduling of Scientific Workflows for the Grid   (Citations: 16)
BibTex | RIS | RefWorks Download
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.
Conference: Cluster Computing and the Grid - CCGRID , pp. 9-16, 2008
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Considering that users are unable to express the exact value for a given criterion or their preferences, the work presented in [9] modeled workflow scheduling as an extension of the Multiple-Choice Knapsack Problem (MCKP) and proposed an algorithm called Dynamic Constraint Algorithm (DCA) used to solve this problem based on the dynamic programming...
    • ...The above research either focused on transforming the structure of DAGs which are used to describe workflows [4][5], or adopted dynamic programming [6] and intelligent algorithms [7-9] to schedule tasks based on static performance of resources which could not guarantee deadline constraints due to dynamic workload changes of target resources...

    Xi Liet al. A Deadline Satisfaction Enhanced Workflow Scheduling Algorithm

    • ...Several bi-criteria scheduling problems with different objectives from the one in this paper have been studied, for independent jobs [10] and for computational workflows [11] on parallel machines...

    Timothy G. Armstronget al. Scheduling Many-Task Workloads on Supercomputers: Dealing with Trailin...

    • ...[11] Proposes a new bi-criterion workflow scheduling algorithm that performs optimization based on a flexible sliding constrain, and they apply a dynamic programming method to the entire workflow to enable an extensive exploration of the search space within the optimization process...
    • ...In order to evaluate our NVCA, we present a set of experiments comparing with DCA [11] by a simulation program that can be used to emulate the execution of randomly generator application task on a simulated grid environment...

    Guoqi Yanget al. A Comprehensive Task Scheduling Algorithm in Grid

    • ...The article [6] presents a study of scheduling workow applications on Grids based on a bi-criteria scheduling model...
    • ...The number of criteria should however be limited since the larger is the amount of criteria, the larger is the complexity of the algorithm [6]...
    • ...With these steps is possible in the worst case, to nd a local optimum and choose the service that better suits a given task [6]...

    H. Klohet al. A scheduling model for workflows on grids and clouds

    • ...Many list heuristics [1][2][3][5][6] have been proposed in non genetic algorithms...

    Bin Quet al. A new genetic algorithm based scheduling for volunteer computing

Sort by: