2026-08-17T04:25:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13355 2024-03-06T10:51:46Z ddc:004 open_access

Approximations for Throughput Maximization Hyatt-Denesik, Dylan Rahgoshay, Mirmahdi Salavatipour, Mohammad R. Scheduling Approximation Algorithms Throughput Maximization In this paper we study the classical problem of throughput maximization. In this problem we have a collection J of n jobs, each having a release time r_j, deadline d_j, and processing time p_j. They have to be scheduled non-preemptively on m identical parallel machines. The goal is to find a schedule which maximizes the number of jobs scheduled entirely in their [r_j,d_j] window. This problem has been studied extensively (even for the case of m = 1). Several special cases of the problem remain open. Bar-Noy et al. [STOC1999] presented an algorithm with ratio 1-1/(1+1/m)^m for m machines, which approaches 1-1/e as m increases. For m = 1, Chuzhoy-Ostrovsky-Rabani [FOCS2001] presented an algorithm with approximation with ratio 1-1/e-ε (for any ε > 0). Recently Im-Li-Moseley [IPCO2017] presented an algorithm with ratio 1-1/e+ε₀ for some absolute constant ε₀ > 0 for any fixed m. They also presented an algorithm with ratio 1-O(√(log m/m))-ε for general m which approaches 1 as m grows. The approximability of the problem for m = O(1) remains a major open question. Even for the case of m = 1 and c = O(1) distinct processing times the problem is open (Sgall [ESA2012]). In this paper we study the case of m = O(1) and show that if there are c distinct processing times, i.e. p_j’s come from a set of size c, then there is a randomized (1-ε)-approximation that runs in time O(n^{mc⁷ε^(-6)}log T), where T is the largest deadline. Therefore, for constant m and constant c this yields a PTAS. Our algorithm is based on proving structural properties for a near optimum solution that allows one to use a dynamic programming with pruning. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dylan Hyatt-Denesik and Mirmahdi Rahgoshay and Mohammad R. Salavatipour 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.11 urn:nbn:de:0030-drops-133555 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.11 eng https://creativecommons.org/licenses/by/3.0/legalcode