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 with no migrations. 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 . The reduction works both for the preemptive and the non-preemptive setting. 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.