Probabilistic-QoS-Aware Multi-Workflow Scheduling Upon the Edge Computing Resources

Background

It is widely acknowledged that to schedule multi-tasks workflow on distributed platforms, e.g., clouds or edge nodes, is an NP-hard problem. It is there for extremely time-consuming to yield optimal schedule through traversal-based algorithms. Fortunately, heuristic and meta-heuristic algorithms with polynomial complexity are able to produce approximate or near optimal solutions at the cost of acceptable optimality loss.

For instance, Zhang Y. et al. (2018) developed a Two-stage Cost Optimization algorithm to schedule workflows on edge clouds. The algorithm first leverages a BF algorithm for obtaining the initial scheduling strategy and then further optimizes the scheduling plans by the first stage. Their algorithm aims to minimize the system cost while meeting the delay requirements of workflows. Kim et al. (2017) studied the trade-off between execution cost and workflow delays in the mobile computing system and proposed an intelligent-control-based algorithm for achieving near-optimal trade-offs. The trace-driven simulation showed that the algorithm can achieve 71% saving of execution cost and 82% gain of as opposed to its peers. Pandey et al. (2010) proposed a particle swarm optimization (PSO) algorithm for load-balancing of cloud servers, while minimizing the execution cost, i.e., communication cost plus cloud resource cost of workflows.