Scheduling two parallel semiautomatic machines to minimize machine interference

We consider the problem of scheduling two parallel semiautomatic machines sharing the same server for setting up jobs with the objective of minimizing the machine idle time resulting from the unavailability of the server. The problem is shown to be strongly NP-hard and a reduction procedure is developed to transform it into a smaller one with all consecutive job completions alternating between the two machines. In the latter problem, regeneration points are identified for simplifying the idle time computations, leading to the development of an efficient beam search heuristic. Computational results indicate that the beam search performs very favourably when compared with local search on a wide variety of problems.