Genetic Algorithm with Repair Method for Deadline-Constrained IoT Workflow Scheduling in Fog-Cloud Computing

Effectively scheduling the execution of deadline-constrained IoT workflows in Fog-Cloud computing is an im-portant practical problem. The execution of IoT workflows must be carefully controlled, especially in applications like IoT health, where missed deadlines can be life-threatening. Existing approaches, including heuristic and meta-heuristic algorithms, have limited capabilities of handling deadline constraints while ensuring efficient execution of workflows. In this paper, we develop a Genetic Algorithm (GA) with a novel repair method to properly allocate workflow tasks to IoT devices and Fog/Cloud servers in order to meet deadlines while minimizing the resource costs. To effectively handle deadline constraints, our repair method first identifies infeasible solutions evolved by GA that can be potentially repaired. It then carries out root cause analysis to determine the primary reasons for deadline violation, and finally reallocate critical tasks to resolve violated deadlines. In this way, the risks of violating deadline constraints can be substantially reduced. On a wide range of problem instances commonly studied in literature, our experiments show that the new algorithm can clearly outperform multiple recently developed methods since it enjoys better chance of finding solutions that satisfy deadline constraints and can notably reduce the resource cost simultaneously.