Compact enumeration for scheduling one machine

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.