Often the problem of determining an optimal or approximate production schedule in a company can be reduced to the problem
of solving a scheduling problem on a bottleneck machine. However, even the majority of the resulting single-machine
scheduling problems are NP-hard from a computational point of view and, therefore, it is difficult to solve large instances of
such problems exactly. In this paper,we consider five such single-machine problems, where a dynamic programming algorithm
of pseudo-polynomial complexity exists. The running time of such an algorithm can often be improved by so-called graphical
algorithms which do not need to consider all states in a dynamic programming algorithm separately. Based on such graphical
algorithms, we present fully polynomial-time approximation schemes (FPTASes) for five single-machine total tardiness
problems. The new FPTASes have the best running time among the known approximation schemes for these problems. The
presented approach is rather general and can be applied to many other scheduling and combinatorial optimisation problems
as well.