زمان بندی جریان کاری، آخرین مهلت محدود شده در نرم افزار به عنوان یک ابر سرویس

The advent of Cloud computing as a new model of service provisioning in distributed systems, encourages researchers to investigate its benefits and drawbacks in executing scientific applications such as workflows. In this model, the users request for available services according to their desired Quality of Service, and they are charged on a pay-per-use basis. One of the most challenging problems in Clouds is workflow scheduling, i.e., the problem of satisfying the QoS of the user as well as minimizing the cost of workflow execution. In this paper, we propose a new QoS-based workflow scheduling algorithm based on a novel concept called Partial Critical Paths (PCP), which tries to minimize the cost of workflow execution while meeting a user-defined deadline. This algorithm recursively schedules the partial critical paths ending at previously scheduled tasks. The simulation results show that the performance of our algorithm is very promising.

Cloud computing [1] is the latest emerging trend in distributed computing that delivers hardware infrastructures and software applications as services. The users can consume these services based on a Service Level Agreement (SLA), which defines their required Quality of Service (QoS) parameters on a pay-per-use basis. Although there are many papers that address the problem of scheduling in traditional distributed systems, like Grids, there are only a few works on this problem in Clouds. The multi-objective nature of the scheduling problem in Clouds makes it difficult to solve, especially in the case of complex jobs like workflows. This has led most researchers to use time-consuming meta-heuristic approaches, instead of fast heuristic methods. In this paper, we propose a new heuristic algorithm for scheduling workflows in Clouds, and we evaluate its performance on some well-known scientific workflows. Recently, many researchers have considered the benefits of using Cloud computing for scientific applications [2], [3] and [4]. Using virtualization technologies, Clouds can offer the users a wide range of services from hardware to the application level. Currently, these services are categorized into three major classes: Infrastructure as a Service (IaaS), Platform as a Service (PaaS) and Software as a Service (SaaS). IaaS Clouds, like Amazon, provide virtualized hardware and storage on top of which the users can deploy their own applications and services. PaaS Clouds, like Microsoft Azure, provide an application development environment in which the users can implement and run applications on the Cloud. According to [5], there are two types of Cloud, which deliver software applications to the users. The first group offers an entire application as a service to the end users, which can be used without any changes or customization. Examples of these Clouds are Google office automation services like Google Document or Google Calendar. The second group provides rudimentary web services to the users (known as on-demand web services), which can be used to build more complex applications. Xignite and StrikeIron offer web services hosted on a Cloud on a pay per use basis. We have used the second group in our SaaS Cloud model. Workflows constitute a common model for describing a wide range of scientific applications in distributed systems. Usually, a workflow is described by a Directed Acyclic Graph (DAG) in which each computational task is represented by a node, and each data or control dependency between tasks is represented by a directed edge between the corresponding nodes. Due to the importance of workflow applications, many Grid projects, such as Pegasus [6], ASKALON [7] and GrADS [8], have designed workflow management systems to define, manage and execute workflows on the Grid. Having been successful on Grids, researchers are now investigating the running of large scientific workflows on Clouds [4]. Furthermore, the latest version of Grid workflow management systems, like Pegasus, VGrADS [9] and ASKALON [10], also support running scientific workflows on Clouds. Workflow scheduling is the problem of mapping each task to a suitable resource and of ordering the tasks on each resource to satisfy some performance criterion. As task scheduling is a well-known NP-complete problem [11], many heuristic methods have been proposed for homogeneous [12] and heterogeneous distributed systems like Grids [13] and [14]. These scheduling methods try to minimize the execution time (makespan) of the workflows and, as such, are suitable for community Grids. Most current workflow management systems, like the ones above mentioned, use such scheduling methods. However, in Clouds, there are many other potential QoS attributes besides execution time, like reliability, security, availability and so on. Besides, stricter QoS attributes mean higher prices for services. Therefore, the scheduler faces a QoS-cost tradeoff in selecting appropriate services, which belongs to the multi-objective optimization problems family. There are several existing approaches to the problem of multi-objective scheduling [15]. One method is to find pareto optimal solutions, and let the user select the best schedule according to his requirements. The problem is that the pareto sets are usually very large and hard to examine. Another common method is to assign a weight to each scheduling criterion, and optimize the weighted sum of these criteria. However, in most cases, the weight assignment is not a straightforward process for users. Due to the complexities of the development of a general multi-objective scheduling algorithm, many researchers try to propose bi-criteria scheduling algorithms. In most bi-criteria scheduling algorithms, the user specifies a limitation for one criterion (deadline or budget constraints), and the algorithm tries to optimize the other criterion under this constraint. This is a convenient way for the users to express their requirements, and a helpful method for the researchers to simplify the problem and propose fast and high performance solutions. In our previous paper, we proposed a QoS-based workflow scheduling algorithm on utility Grids, called the Partial Critical Paths (PCP) [16]. In this paper, we propose the SaaS Cloud Partial Critical Paths (SC-PCP) algorithm, which is an extension of the previous one for the SaaS Clouds. The objective function of the SC-PCP algorithm is to create a schedule that minimizes the total execution cost of a workflow, while satisfying a user-defined deadline for the total execution time. First, the SC-PCP algorithm tries to schedule the (overall) critical path of the workflow, such that it is completed before the user deadline, and execution cost is minimized. Then, it finds the partial critical path to each scheduled task on the critical path and executes the same procedure in a recursive manner. The remainder of the paper is organized as follows. Section 2 describes our system model including the application model the Cloud model and the objective function. The SC-PCP scheduling algorithm is explained in Section 3. A performance evaluation is presented in Section 4. Section 5 reviews related work and Section 6 concludes.

The Cloud computing model enables users to obtain their required services with desired QoS (such as deadline) by paying an appropriate price. In this paper, we propose a new algorithm named the SaaS Cloud Partial Critical Path (SC-PCP) for workflow scheduling in SaaS Clouds, which minimizes the total execution cost while meeting a user-defined deadline. We evaluate our algorithm by simulating it with synthetic workflows that are based on real scientific workflows with different structures and sizes. The results show that SC-PCP outperforms another highly cited algorithm called Deadline-MDP. Furthermore, the experiments show that the computation time of the algorithm is very low for the Decrease Cost and the Fair policies, but is much longer for the Optimized policy, although still acceptable for the mentioned workflows. In the future, we plan to extend our algorithm to support other Cloud computing models, such as IaaS and other pricing models.