Competitive analysis of HPC co-scheduling strategies optimizing for makespan, fairness and efficiency

Inefficient use of allocated computational resources is a common challenge in high-performance computing (HPC) applications. While modifying application source code to improve resource efficiency may not always be feasible, co-scheduling – concurrent execution of multiple applications on shared resources to mitigate resource contention – offers a potential solution. In this paper, we formalize the co-scheduling problem and analyze three approximate strategies: fastest combination speed (FCS), proportional efficiency (PE) and proportional fairness (PF). For these strategies we derive analytical worst-case performance bounds and use numerical simulation to show their average-case performance and trade-offs. In particular, we demonstrates that FCS achieves the lowest possible competitive ratio among all non-preemptive strategies, guaranteeing worst-case performance within 50% of the optimal solution. Numerical simulations demonstrate that PF ensures fairness and consistently outperforms FCS in the average case, despite having lower worst-case theoretical performance. The PE strategy, while minimizing the number of parallel tasks, is shown to have an unbounded competitive ratio. Modifying these strategies to prioritize tasks on the critical path for problems with precedence constraints improves performance for graphs that allow a higher degree of parallelism. These findings provide a theoretical foundation for incorporating co-scheduling strategies into HPC workflow managers.