# 2-approxmation

by scheduling in order of Smith ratio,

for 1|r_{j};pmtn|Σ w_{j}C_{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.]

## Input

## Output