Assigning a large number of independent tasks to heterogeneous processors is a fundamental problem in modern computing, with applications in many domains such as cloud services, web crawling, and AI training. Exact and matheuristic approaches deliver high-quality assignments but incur superlinear or even exponential runtime costs, making them impractical, especially on large problem instances. Conversely, lightweight heuristics run efficiently at scale but often produce assignments with much lower quality. To address this issue, we present the first multilevel framework for the independent task assignment problem that maintains an end-to-end linear runtime bound of O ( K N ) , where K × N is the size of the expected-time-to-compute matrix, with K and N respectively representing the number of processors and tasks. We propose (i) novel high-quality coarsening metrics that numerically define task characteristics and similarity; (ii) an efficient and effective matching algorithm that incorporates these metrics while maintaining linear time complexity with respect to the input size; (iii) an initial solution scheme that generates base solutions using complementary heuristics, which are disjointly projected back through the uncoarsening levels; (iv) an effective and efficient uncoarsening algorithm that iteratively improves assignment quality with different refinement algorithms. Extensive experimental evaluations involving hundreds of millions of tasks demonstrate that our algorithm achieves significantly higher quality and runs faster than known high-quality heuristics, making it a practical choice for the problem instances at high scale.

MinMin, MaxMin, and Sufferage are constructive heuristics that are widely and successfully used in assigning independent tasks to processors in heterogeneous computing systems. All three heuristics are known to run in O(KN2) time in assigning N tasks to K processors. In this paper, we propose an algorithmic improvement that asymptotically decreases the running time complexity of MinMin to O(KN log N) without affecting its solution quality. Furthermore, we combine the newly proposed MinMin algorithm with MaxMin as well as Sufferage, obtaining two hybrid algorithms. The motivation behind the former hybrid algorithm is to address the drawback of MaxMin in solving problem instances with highly skewed cost distributions while also improving the running time performance of MaxMin. The latter hybrid algorithm improves the running time performance of Sufferage without degrading its solution quality. The proposed algorithms are easy to implement and we illustrate them through detailed pseudocodes. The experimental results over a large number of real-life data sets show that the proposed fast MinMin algorithm and the proposed hybrid algorithms perform significantly better than their traditional counterparts as well as more recent state-of-the-art assignment heuristics. For the large data sets used in the experiments, MinMin, MaxMin, and Sufferage, as well as recent state-of-the-art heuristics, require days, weeks, or even months to produce a solution, whereas all of the proposed algorithms produce solutions within only two or three minutes.