A Graphical Approach for Solving Single Machine Scheduling Problems Approximately
Résumé
For five single machine total tardiness problems a fully polynomial-time approximation scheme (FPTAS) based on a graphical algorithm is presented. The FPTAS has the best running time among the known approximation schemes for these problems.