Tight Low-Complexity Approximation for the Q_m‖C_max Problem via Mathematical Programming Modeling

We consider the well-known uniform machine scheduling problem $Qm\Vert C_{\mathit{\text{max}}}$, in which we are given a set of n jobs with processing times $p_1,\dots ,p_n$ and a set of m parallel machines, each with a corresponding speed factor $q_i$ for $i=1,\dots ,m$. 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 $Qm\Vert C_{\mathit{\text{max}}}$ 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 $Qm\Vert C_{\mathit{\text{max}}}$ 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/.