A Hybrid Combinatorial Optimization Approach to the Job Scheduling Problem in Supercomputing Environments

The NP-hard job scheduling problem is a fundamental challenge for the efficiency of high-performance computing environments, where the high dimensionality of data makes traditional exact approaches impractical. This work proposes a hybrid approach that integrates the Adaptive Large Neighbourhood Search metaheuristic with clustering techniques and an exact optimization model for the local resolution of subproblems. The method incorporates a learning mechanism based on the Multi-Armed Bandit framework for dynamic operator adaptation, as well as a probabilistic solution acceptance criterion based on Simulated Annealing. The decomposition strategy enables the optimization of critical subsets while keeping the remaining tasks fixed. Validated using real workload logs from three distinct systems, the method focuses on minimizing the average bounded slowdown. Computational results indicate that the proposed approach is scalable and competitive, outperforming classical heuristics and evolutionary methods, and achieving up to 8.25% lower values than the Reinforcement Learning-based benchmark.