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