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

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 wj/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.]


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