Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints*,**

We investigate two parallel dedicated machine scheduling with conflict constraints. The problem of minimizing the makespan has been shown to be NP-hard in the strong sense under the assumption that the processing sequence of jobs on one machine is given and fixed a priori. The problem without any fixed sequence was previously recognized as weakly NP-hard. In this paper, we first present a 95-approximation algorithm for the problem with a fixed sequence. Then we show that the tight approximation ratios of the algorithm are 74 and 35 for two subproblems which remain strongly NP-hard. We also root send an improved algorithm with approximation ratio 3 - 2 approximate to 1.586 for one subproblem. Finally, we prove that the problem without any fixed sequence is actually strongly NP-hard, and design a 35-approximation algorithm. (c) 2022 Elsevier B.V. All rights reserved.