Abstract For the problem of minimizing total completion time on single machine with
unit processing time, an approximation algorithm with a performance
ratio smaller than$\frac{9+\sqrt{3}}{6}\approx1.7817$ is given. The
paper showed that there dose not exist any fully polynomial time
approximation schedule unless $P=NP$, even if the total size of the
jobs is smaller than 2.
Received: 18 March 2017
Published: 01 December 2018
