2-approxmation
by scheduling in order of Smith ratio,
for 1|r_j;pmtn|Σ w_jC_j

We are given n jobs. Each job has a release time before which it is not available, and a processing time p. We wish to find a feasible preemptive schedule for a single machine, which minimizes the weighted sum over the completion times.

Algorithm by Smith: At any time we schedule the job j with the greatest Smith ratio w_j/p'_j, where p'_j is the remaining processing time of job j.
This problem is NP-hard, but the algorithm provides a schedule which objective value is as most twice the optimum. [Goemans, Wein, Williamson personal communication to A. Schultz. Proof in A.S. Schulz, M. Skutella, The power of α-points in preemptive single machine scheduling, J. Sched. 5 (2002) 121-133.]

2-approxmation
by scheduling in order of Smith ratio,
for 1|r_j;pmtn|Σ w_jC_j

Input

Output

Release time/processing time/weight for every job
	output the schedule with one job per row (otherwise all jobs in a same row)
	zoom x2

2-approxmation by scheduling in order of Smith ratio, for 1|rj;pmtn|Σ wjCj

Input

Output

2-approxmation
by scheduling in order of Smith ratio,
for 1|r_j;pmtn|Σ w_jC_j