Approximation Algorithms for Maximum Weighted Throughput on Unrelated Machines

We study the classic weighted maximum throughput problem on unrelated machines. We give a (1 − 1/e − ε)-approximation algorithm for the preemptive case. To our knowledge this is the first ever approximation result for this problem. It is an immediate consequence of a polynomial-time reduction we design, that uses any ρ-approximation algorithm for the single-machine problem to obtain an approximation factor of (1 − 1/e)ρ − ε for the corresponding unrelated-machines problem, for any ε > 0. On a single machine we present a PTAS for the non-preemptive version of the problem for the special case of a constant number of distinct due dates or distinct release dates. By our reduction this yields an approximation factor of (1 − 1/e) − ε for the non-preemptive problem on unrelated machines when there is a constant number of distinct due dates or release dates on each machine.