Abstract
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-∈ .
Original language | English |
---|---|
Pages (from-to) | 348-350 |
Number of pages | 3 |
Journal | Operations Research Letters |
Volume | 42 |
Issue number | 5 |
DOIs | |
State | Published - Jul 2014 |
Keywords
- APX-hardness
- Complexity
- Scheduling