The local-global conjecture for scheduling with non-linear cost

Nikhil Bansal, Christoph Dürr, Nguyen Kim Thang +1

We consider the classical scheduling problem on a single machine, on which we need to schedule sequentially $n$ given jobs. Every job $j$ has a processing time $p_j$ and a priority…