Faster Exponential Algorithms for Multi-Machine Scheduling Problems

Abstract

Minimizing the weighted completion times ($P\mid \mid \Sigma w_j{C}_j$) and weighted number of tardy jobs ($P\mid \mid \Sigma w_j{U}_j$) on multiple identical machines are two classical NP-hard scheduling problems. As shown by Lenté et al. (2014), both problems can be solved in time $O^{\star }(3^n)$. In this paper, we improve these bounds to $O(2.755^n)$ and $O^{\star }(2^n)$, respectively. Our algorithm for $P\mid \mid \Sigma w_j{C}_j$ exploits the meet-in-the-middle paradigm and an efficient data structure answering linear programming queries. Additionally, when the number of machines is at most $6$, we show that the running time for $P\mid \mid \Sigma w_j{C}_j$ can further be improved. Both scheduling problems are generalizations of the classical Bin Packing problem, which can be solved in $O^{\star }(2^n)$ time. Improving this running time is an important open question. We show that, when assuming the Asymptotic Rank Conjecture (ARC), Bin Packing can be solved in time $O((2-\epsilon {)}^n)$ for some $\epsilon >0$. Our algorithm makes use of two main ingredients: the recent $O((2-\epsilon {)}^n)$-time algorithm of Nederlof et al. [SICOMP'23] for Bin Packing when the number of bins is a fixed constant, and the $O((2-\epsilon {)}^n)$-time algorithm of Björklund et al. [SODA'25] for special instances of the $3$-way Partitioning problem when assuming ARC.