A note on scheduling with low rank processing times

Lin Chen, Deshi Ye, Guochuan Zhang

We consider the classical minimum makespan scheduling problem, where the processing time of job $j$ on machine $i$ is $p_{ij}$, and the matrix $P=(p_{ij}{)}_{m\times n}$ is of a low…