A note on scheduling with low rank processing times
2013
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 [1] that rank 7 scheduling is NP-hard to approximate to a factor of 3/2−ǫ, and rank 4 scheduling is APX-hard (NP-hard to approximate within 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 − ǫ, and meanwhile rank 3 scheduling is APX-hard.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
8
References
4
Citations
NaN
KQI