Local search driven periodic scheduling for workflows with random task runtime in clouds

When data processing applications from various fields are deployed in cloud computing, workflow scheduling is vital in satisfying users' requirements and improving cloud platforms' performance. Up to the present, some works have put forward heuristic methods to handle dynamic and uncertain factors when scheduling workflows in cloud platforms. Although these heuristics can generate feasible schedules quickly, their performance can be further improved. It is noteworthy that not all the workflow tasks can be executed immediately due to their data dependencies. Then, their waiting time can be utilized to further optimize schedules generated by heuristic methods. Motivated by the above fact, this paper proposes a Local Search driven Periodic Scheduling, LSPS, for workflows having deadlines and random task runtime. Specifically, in each scheduling period, the LSPS only schedule the tasks to start running, thus shortening the length of local waiting queues on resources to alleviate the negative effects of dynamics and uncertainty. Moreover, we design a problem-specific local search strategy for LSPS to fully use the scheduling period to improve the quality of schedules iteratively. At last, in the context of real cloud platforms, four groups of compared experiments are carried out to measure the effectiveness of the proposed LSPS concerning monetary cost and resource efficiency.

Automated summary

This paper emphasizes the importance of workflow scheduling in cloud computing and proposes a Local Search driven Periodic Scheduling (LSPS) method to optimize schedules. By utilizing task waiting time and designing a problem-specific local search strategy, LSPS shows advantages in alleviating the negative effects of dynamics and uncertainty and improving the quality of schedules.