Genetic Programming for Dynamic Workflow Scheduling in Fog Computing
Meng Xu, Yi Mei, Shiqiang Zhu, Beibei Zhang, Tian Xiang, Fangfang Zhang, Mengjie Zhang
Abstract
<bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D</b> ynamic <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">W</b> orkflow <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</b> cheduling in <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F</b> og <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</b> omputing (DWSFC) is an important optimisation problem with many real-world applications. The current workflow scheduling problems only consider cloud servers but ignore the roles of mobile devices and edge servers. Some applications need to consider the mobile devices, edge, and cloud servers simultaneously, making them work together to generate an effective schedule. In this article, a new problem model for DWSFC is considered and a new simulator is designed for the new DWSFC problem model. The designed simulator takes the mobile devices, edge, and cloud servers as a whole system, where they all can execute tasks. In the designed simulator, two kinds of decision points are considered, which are the routing decision points and the sequencing decision points. To solve this problem, a new <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</b> ulti- <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</b> ree <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</b> enetic <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</b> rogramming (MTGP) method is developed to automatically evolve scheduling heuristics that can make effective real-time decisions on these decision points. The proposed MTGP method with a multi-tree representation can handle the routing decision points and sequencing decision points simultaneously. The experimental results show that the proposed MTGP can achieve significantly better test performance (reduce the makespan by up to 50%) on all the tested scenarios than existing state-of-the-art methods.