The problem of scheduling jobs with release dates on a single machine so as to minimize total completion time has long been know to be strongly NP-complete. Recently, a polynomial-time approximation scheme (PTAS) was found for this problem. We implemented this algorithm to compare its performance with several other known algorithms for this problem. We also developed several good algorithms based on this PTAS that run faster by sacrificing the performance guarantee. Our results indicate that the ideas used by this PTAS lead to improved algorithms.
展开▼
