Scheduling algorithms for instance-intensive cloud workflows

This thesis focuses on algorithms for scheduling instance-intensive cloud workflows in different cloud computing environments built on different system infrastructures. Instance-intensive cloud workflows are workflows with a huge number of workflow instances (hence instance intensive) running on a cloud computing environment (hence cloud workflows). First of all, the prosperity of e-business relies on the ability to process instanceintensive workflows. A typical example of instance-intensive workflows is the bank cheque processing scenario, where millions of cheque-processing transactions need to be processed concurrently each day, while each of them is a rather simple workflow with only a few steps. Meanwhile, with the promotion of the world's leading companies, cloud computing has become an area of increasing interest. Cloud computing has many unique advantages, such as low cost, scalability, reliability and fault-tolerance, which can effectively facilitate the execution of workflows. Moreover, cloud computing environments can be built on different system infrastructures. For instance, it can be built on physically collocated grids (grid-based), or geographically distributed services (service-based). In a commercial cloud computing infrastructure with a 'pay per use' context (business-based) the execution cost should be considered as well as the execution time. Each of these different infrastructures demands a different workflow scheduling algorithm. Therefore, in this research, we propose three corresponding algorithms for scheduling instance-intensive workflows on grid-based, service-based and businessbased cloud computing environments respectively, namely, TMS (Throughput Maximisation Strategy) for a grid-based cloud computing environment, MMA (Min- Min-Average) for a service-based cloud computing environment and CTC (Compromised-Time-Cost) for a business-based cloud computing environment. TMS consists of two algorithms in order to adapt to a grid-based cloud computing environment. The first algorithm is to maximise the overall throughput by pursuing overall load balance at the instance level, while the second algorithm strives to further maximise the throughput by increasing the utilisation rate of resources within each local autonomous group at the task level. Through these efforts, an increase in overall throughput can be achieved. MMA aims at increasing the overall throughput in a service-based cloud computing environment. It establishes a fundamental infrastructure that can provide nearest neighbours to decrease the communication time significantly. Moreover, due to the importance of both execution time and transmission time, it uses a different strategy to the original Min-Min algorithm in order to improve the utilisation rate of both the execution unit and transmission unit of the workflow execution engine in order to increase the overall throughput. Designed for business cloud workflows, the CTC algorithm is targeted to compromise the time and cost through the scheduling process. For different user requirements, this algorithm can be further divided into two sub-algorithms: the CTCMC (Compromised-Time-Cost algorithm Minimising execution Cost) algorithm, which minimises the execution cost within user designated deadline, and the CTC-MT (Compromised-Time-Cost algorithm Minimising execution Time) algorithm, which minimises the execution time within user designated budget. However, both algorithms allow the user to request an acceptable compromise between execution time and execution cost on the fly. The simulations performed on Swinburne Workflow Test Environment (SWTE) demonstrate that all our workflow scheduling algorithms have better performance than their counterparts which are scheduling algorithms currently implemented in most popular workflow management systems.