Schedule heterogeneous tasks on heterogeneous machines

Question

We have n jobs and m machines. Each job i has a release time r[i]. Processing job i on machine j takes p[i][j] time. For one job k, |{p[i][j] | i == k}| <= c, where c << m. We define the delay of job i as f[i] - r[i], where f[i] is the time when job i is finished. The system is not preemptive, i.e., when one job is started on some machine, it cannot be interrupted before it finishes. The goal is to provide a scheduling algorithm that minimizes the delay sum of all jobs. Any idea?

Answer 1

Here's a reduction from the 3-partition problem.

Let S = {x₁, …, x_3m} be the instance of 3-partition such that, for every i, B/4 < x_i < B/2, where B = ∑x_i/m is the target sum.

Let there be m identical machines. At time 0, release 3m jobs of lengths x₁, …, x_3m. At each time B, B + 1, …, B + 4mB - 1, release m jobs of length 1, for a total of 4m²B jobs.

The instance of 3-partition has a solution if and only if the makespan of the initial jobs is less than or equal to B. If there is a solution, then the contribution of the initial jobs to the objective is at most 3mB. The contribution of the other jobs is 4m²B.

If the makespan is longer than B, then a chain of 4mB jobs is delayed at least one unit, contributing 4mB to the objective. Thus the objective is at most 3mB + 4m²B if the 3-partition problem is solvable and at least 4mB + 4m²B if the 3-partition problem is not solvable.