Integrated scheduling algorithm of reversed device network based on operation genealogy table

Abstract

In response to the issue where previous complex product device network scheduling algorithms did not separately consider the migration time of the device, resulting in errors in the actual scheduling results, this paper proposes a reverse device network integrated scheduling algorithm based on the operation genealogy table within the framework of a genetic algorithm. Firstly, the processing operation tree of the product is mapped into an operation genealogy table, and an encoding method based on multi-child probability selection is proposed. Then, crossover methods based on descendant nodes, parent nodes, and positions are respectively introduced to ensure the legality of the generated offspring individuals. Additionally, two mutation methods, namely the single point mutation method based on movable range and the recoding mutation method based on a single node, are proposed to enhance population diversity. Lastly, a pre-decoding method driven by migration time and a forward-to-reverse scheduling scheme conversion strategy based on completion time reversal is resented. This paper conducts two sets of comparative experiments based on rules and based on metaheuristics, comparative experimental results demonstrate that the proposed algorithm outperforms other comparative algorithms in terms of solution quality.