Low-Low Average Algorithm for Scheduling Request-Demanding Cloud Workflows with Overhead

This paper addresses the scheduling algorithms for request-demand cloud workflows. Request-demand cloud workflows are workflows with a huge number of workflow requests (hence request demand) enabled on a cloud computing environment (hence cloud workflows). Unlike complex scientific workflows on which most existing workflow scheduling algorithms focus, the main characteristic of request-demand workflows is a huge number of potentially relatively simple concurrent requests. Atypical example of these workflows is the bank cheque processing scenario, in which there are millions of concurrent cheque-processing transactions per day, while each of them is a rather simple workflow with only a few steps.
This distinguishing characteristic of request-demand workflows makes most existing workflow scheduling algorithms unsuitable for scheduling request-demand workflows. Moreover, if the cost needs to be considered, how to compromise the cost with execution time (make span) also becomes an important issue. As a result, this paper proposes different scheduling algorithms for request-demand workflows in different circumstances.