  A strongly NP-hard scheduling problem in which non-simultaneously released
jobs with delivery times are to be scheduled on a single machine with the
objective to minimize the maximum job full completion time is considered. We
describe an exact implicit enumeration algorithm (IEA) and a polynomial-time
approximation scheme (PTAS) for the single-machine environment. Although the
worst-case complexity analysis of IEA yields a factor of $\nu!$, $\nu>n$, large
sets of the permutations of the critical jobs can be discarded by incorporating
a heuristic search strategy, in which the permutations of the so-called
critical jobs are considered in a special priority order. Not less importantly,
in practice, the number $\nu$ turns out to be several times smaller than the
total number of jobs $n$, and it becomes smaller when $n$ increases. The above
characteristics also apply to the proposed PTAS, which worst-case time
complexity can be expressed as $O(\kappa!\kappa k n \log n)$, where $\kappa$ is
the number of the long critical jobs ($\kappa<<\nu$) and the corresponding
approximation factor is $1+1/k$, where $\kappa<k$. We show that the probability
that a considerable number of permutations (far less than $\kappa!$) are
enumerated is close to 0. Hence, with a high probability, the running time of
PTAS is fully polynomial.
