  We consider the classical scheduling problem on parallel identical machines
to minimize the makespan, and achieve the following results under the
Exponential Time Hypothesis (ETH)
  1. The scheduling problem on a constant number $m$ of identical machines,
which is denoted as $Pm||C_{max}$, is known to admit a fully polynomial time
approximation scheme (FPTAS) of running time $O(n) + (1/\epsilon)^{O(m)}$
(indeed, the algorithm works for an even more general problem where machines
are unrelated). We prove this algorithm is essentially the best possible in the
sense that a $(1/\epsilon)^{O(m^{1-\delta})}+n^{O(1)}$ time FPTAS for any
$\delta>0$ implies that ETH fails.
  2. The scheduling problem on an arbitrary number of identical machines, which
is denoted as $P||C_{max}$, is known to admit a polynomial time approximation
scheme (PTAS) of running time $2^{O(1/\epsilon^2\log^3(1/\epsilon))}+n^{O(1)}$.
We prove this algorithm is nearly optimal in the sense that a
$2^{O((1/\epsilon)^{1-\delta})}+n^{O(1)}$ time PTAS for any $\delta>0$ implies
that ETH fails, leaving a small room for improvement.
  To obtain these results we will provide two new reductions from 3SAT, one for
$Pm||C_{max}$ and another for $P||C_{max}$. Indeed, the new reductions explore
the structure of scheduling problems and can also lead to other interesting
results. For example, using the framework of our reduction for $P||C_{max}$,
Chen et al. (arXiv:1306.3727) is able to prove the APX-hardness of the
scheduling problem in which the matrix of job processing times
$P=(p_{ij})_{m\times n}$ is of rank 3, solving the open problem mentioned by
Bhaskara et al. (SODA 2013).
