Optimal Task Scheduling Algorithm for Simulation Engines

Aiming at the efficiency optimization problem of multi-thread task scheduling in simulation engine environments, this paper proposes an optimal task scheduling algorithm based on load balancing. By establishing a task-thread system model, the problem of decomposing <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$K$</tex> independent computational subtasks into <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> threads is constructed as a combinatorial optimization model with the objective of minimizing task completion time. Through problem transformation, the discrete task allocation is converted into a continuous computational load optimization problem, deriving the conclusion that the optimal load of each thread should be proportional to its computational capability and providing a theoretical optimality proof. Based on this conclusion, a two-stage greedy algorithm is designed: the first stage allocates task groups to threads in ascending order of computational capability to approximate the theoretical optimal value; the second stage realizes time optimization compensation by reversely allocating remaining tasks. Simulation experiments under normal distribution of task volumes and computational capabilities show that the proposed algorithm reduces computation time by 16.9% and 20.3% compared with random scheduling and round-robin scheduling in different task scale scenarios, respectively. The experimental results verify the algorithm's effectiveness in load balancing and time optimization, providing theoretical support and practical methods for task scheduling in simulation engines.