An approximate decomposition algorithm for scheduling on parallel machines with heads and tails

We address the makespan minimization for parallel identical machines subject to heads and tails. This problem is NP-hard in the strong sense. We show that the worst-case performance of Jackson's algorithm is improved by using a preprocessing algorithm, and we propose an approximate decomposition algorithm which requires iteratively solving a sequence of two-machine problems. We present the results of an extensive computational study on large instances with up to 2000 jobs and 100 machines which show that the proposed heuristic is fast and yields in most cases schedules with relative deviation from a lower bound less than 0.2%.