Approximability of average completion time scheduling on unrelated machines

We show that minimizing the average job completion time on unrelated machines isAPX -hard if preemption of jobs is allowed. This provides one of the last missing pieces in the complexity classification of machine scheduling with (weighted) sum of completion times objective. The proof is based on a mixed integer linear program. This means that verification… (More)