Complexity and heuristic algorithm for parallel machine scheduling problem with release times and a single server

We discuss parallel machine scheduling problem with a single server. Before processing, each job must be loaded on a machine, which takes certain setup time. All these setups have to be done by a single server, which can handle at most one job at a time. For the two-machine case, we prove that problem is NP-hard in the strong sense even if all processing times are equal to 1. A simple heuristic algorithm is shown to create schedule with the makespan that is at most twice the optimum value for the m-machine.