Cost-Based Scheduling of Scientific Workflow Application on Utility Grids

TLDR

Grid technologies have evolved into service‑oriented utility computing models where users pay per use and must consider execution cost under QoS constraints. The paper proposes a cost‑minimizing workflow scheduling algorithm that meets deadlines. The algorithm reschedules delayed tasks and models sequential branches as a Markov decision process solved by value iteration.

Abstract

Over the last few years, grid technologies have progressed towards a service-oriented paradigm that enables a new way of service provisioning based on utility computing models. Users consume these services based on their QoS (quality of service) requirements. In such "pay-per-use" grids, workflow execution cost must be considered during scheduling based on users' QoS constraints. In this paper, we propose a cost-based workflow scheduling algorithm that minimizes execution cost while meeting the deadline for delivering results. It can also adapt to the delays of service executions by rescheduling unexecuted tasks. We also attempt to optimally solve the task scheduling problem in branches with several sequential tasks by modeling the branch as a Markov decision process and using the value iteration method.