Compact enumeration for scheduling one machine
share
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 ν!, ν>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 ν 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(κ!κ k n log n), where κ is the number of the long critical jobs (κ<<ν) and the corresponding approximation factor is 1+1/k, where κ<k. We show that the probability that a considerable number of permutations (far less than κ!) are enumerated is close to 0. Hence, with a high probability, the running time of PTAS is fully polynomial.
READ FULL TEXT