Tight Low-Complexity Approximation for the Q _m ‖ C _max

We consider the well-known uniform machine scheduling problem [Formula: see text], in which we are given a set of n jobs with processing times [Formula: see text] and a set of m parallel machines, each with a corresponding speed factor [Formula: see text] for [Formula: see text]. The goal is to find an assignment of the jobs to the machines that minimizes the makespan. We propose a general methodology to derive approximation results for different algorithms that share the following high-level structure: a specific procedure is first applied to a list of long jobs, followed by a standard list scheduling approach. This methodology is based on theoretical results we derive for [Formula: see text] that allow us to analyze instances with a limited number of jobs. We evaluate the worst case performance of several algorithms using mathematical programming formulations and derive both existing and new approximation ratios for the problem with up to seven machines. In this context, our approach offers a more flexible tool than traditional analytical proof systems for studying the [Formula: see text] problem and potentially other related problems.

History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms.

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1129 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1129 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .