We consider the classical minimum makespan scheduling problem, where the processing time of job j on machine i is pij, and the matrix P=( pij)m×n is of a low rank. It is proved in Bhaskara et al. (2013) that rank 7 scheduling is NP-hard to approximate to a factor of 3/2-∈, and rank 4 scheduling is APX-hard (a factor of 1.03-∈). We improve this result by showing that rank 4 scheduling is already NP-hard to approximate within a factor of 3/2-∈ .
|Number of pages||3|
|Journal||Operations Research Letters|
|State||Published - Jul 2014|