Static scheduling of computational workflow represented by a directed acyclic graph (DAG) is an important problem in many areas of computer science. The main idea and novelty of the proposed algorithm is an adaptive heuristic or graph metric that uses a different heuristic rule at each scheduling step depending on local workflow. It is also important to note that multi-agent reinforcement learning is used to determine scheduling policy based on adaptive metrics. To prove the efficiency of the approach, a comparison with the state-of-the-art DAG scheduling algorithms is provided: DONF, CPOP, HCPT, HPS, and PETS. Based on the simulation results, the proposed algorithm shows an improvement of up to 30% on specific graph topologies and an average performance gain of 5.32%, compared to the best scheduling algorithm, DONF (suitable for large-scale scheduling), on a large number of random DAGs. Another important result is that using the proposed algorithm it was possible to cover 30.01% of the proximity interval from the best scheduling algorithm to the global optimal solution. This indicates that the idea of an adaptive metric for DAG scheduling is important and requires further research and development.
1 January 2022 in Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes
More and more experts agree that in the near future, most freight traffic will be carried out using automated systems, and of them drone delivery is considered to be the most promising. Drone delivery would benefit by independence from the limitations of transport infrastructure and road conditions and would ensure cargo delivery with rapid turnaround times, as well as a significant reduction of environmental impact. The technical capabilities of unmanned aerial vehicles improve year by year, so the task of coordinating drones and effectively planning routes is relevant and in great demand. The development of such technologies will help reduce transportation costs and improve customer service through faster delivery. This article discusses the applied routing problem for a fleet of drones with limited load capacity for the delivery of heterogeneous goods with the possibility of loading in multiple warehouses from an international optimization competition. The solution includes new approach based on a mixed dimensional parallel genetic algorithm (MDPGA) for finding rational routes for delivering goods to various customers and an assignment problem to reduce the dimension depending on the number of warehouses.