Tight Low-Complexity Approximation for theQmβCmaxProblem via Mathematical Programming Modeling
Luca Savant Aira, Rosario Scatamacchia, Federico Della Croce di Dojola
INFORMS Journal on Computing Β· Mon
Abstract
We consider the well-known uniform machine scheduling problem π β’ π β πΆ π π π₯ Q β’ m β C max , in which we are given a set of n jobs with processing times π 1 , β¦ , π π p 1 , β¦ , p n and a set of m parallel machines, each with a corresponding speed factor π π q i for π = 1 , β¦ , π i = 1 , β¦ , 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 π β’ π β πΆ π π π₯ Q β’ m β C 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 π β’ π β πΆ π π π₯ Q β’ m β C 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/ .
Keywords
approximation algorithms, mathematical programming, uniform parallel machine scheduling
Enable JavaScript for citation tools and additional paper interactions.