A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
We consider the following single-machine scheduling problem, which is often denoted $1||\sum f_{j}$: we are given $n$ jobs to be scheduled on a single machine, where each job $j$ has an integral processing time $p_j$, and there is a nondecreasing, nonnegative cost function $f_j(C_{j})$ that specifies the cost of finishing …