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

References

• Berndt S, Brinkop H, Jansen K, Mnich M, Stamm T (2023) New support size bounds for integer programming, applied to makespan minimization on uniformly related machines. Iwata S, Kakimura N, eds. 34th Internat. Sympos. Algorithms Comput. (ISAAC 2023), Leibniz International Proceedings in Informatics (LIPIcs), vol. 283 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 13:1–13:18.Google Scholar
• Burkard R, He Y (1998) A note on multifit scheduling for uniform machines. Computing 61(3):277–283.Crossref, Google Scholar
• De Bontridder K, Halldórsson B, Halldórsson M, Hurkens C, Lenstra J, Ravi R, Stougie L (2021) Local improvement algorithms for a path packing problem: A performance analysis based on linear programming. Oper. Res. Lett. 49(1):62–68.Crossref, Google Scholar
• Della Croce di Dojola F (2016) MP or not MP: That is the question. J. Scheduling 19(1):33–42.Crossref, Google Scholar
• Della Croce di Dojola F, Scatamacchia R (2020) The longest processing time rule for identical parallel machines revisited. J. Scheduling 23(2):163–176.Crossref, Google Scholar
• Dobson G (1984) Scheduling independent tasks on uniform processors. SIAM J. Comput. 13(4):705–716.Crossref, Google Scholar
• Fishkin A, Jansen K, Mastrolilli M (2008) Grouping techniques for scheduling problems: Simpler and faster. Algorithmica 51(2):183–199.Crossref, Google Scholar
• Friesen D (1987) Tighter bounds for LPT scheduling on uniform processors. SIAM J. Comput. 16(3):554–560.Crossref, Google Scholar
• Friesen D, Langston M (1983) Bounds for multifit scheduling on uniform processors. SIAM J. Comput. 12(1):60–70.Crossref, Google Scholar
• Gonzalez T, Ibarra O, Sahni S (1977) Bounds for LPT schedules on uniform processors. SIAM J. Comput. 6(1):155–166.Crossref, Google Scholar
• Graham R (1969) Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2):416–429.Crossref, Google Scholar
• Graham R, Lawler E, Lenstra J, Rinnooy Kan A (1979) Optimization and approximation in deterministic sequencing and scheduling: A survey. Hammer P, Johnson E, Korte B, eds. Discrete Optimization II, Annals of Discrete Mathematics, vol. 5 (North-Holland, Amsterdam), 287–326.Crossref, Google Scholar
• Horowitz E, Sahni S (1976) Exact and approximate algorithms for scheduling nonidentical processors. J. Assoc. Comput. Machinery 23(2):317–327.Crossref, Google Scholar
• Jansen K, Porkolab L (2001) Improved approximation schemes for scheduling unrelated parallel machines. Math. Oper. Res. 26(2):324–338.Link, Google Scholar
• Kononov A, Kononova P, Gordeev A (2020) Branch-and-bound approach for optima localization in scheduling multiprocessor jobs. Internat. Trans. Oper. Res. 27(1):381–393.Crossref, Google Scholar
• Koulamas C, Kyparisis G (2009) A modified LPT algorithm for the two uniform parallel machine makespan minimization problem. Eur. J. Oper. Res. 196(1):61–68.Crossref, Google Scholar
• Kovács A (2010) New approximation bounds for LPT scheduling. Algorithmica 57(2):413–433.Crossref, Google Scholar
• Mireault P, Orlin J, Vohra R (1997) A parametric worst case analysis of the LPT heuristic for two uniform machines. Oper. Res. 45(1):116–125.Link, Google Scholar
• Mitsunobu T, Suda R, Suppakitpaisarn V (2024) Worst-case analysis of LPT scheduling on a small number of non-identical processors. Inform. Processing Lett. 183:106424.Crossref, Google Scholar
• Savant Aira L, Scatamacchia R, Della Croce di Dojola F (2025) Tight low-complexity approximation for the Qm‖Cmax problem via mathematical programming modeling. https://doi.org/10.1287/ijoc.2025.1129.cd, https://github.com/INFORMSJoC/2025.1129.Google Scholar
• Sevastianov S, Tchernykh I (1998) Computer-aided way to prove theorems in scheduling. Bilardi G, Italiano GF, Pietracaprina A, Pucci G, eds. Algorithms—ESA ’98: 6th Annual Eur. Sympos., Proceedings, Lecture Notes in Computer Science, vol. 1461 (Springer, Berlin, Heidelberg), 502–513.Google Scholar