1. Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints.
- Author
-
Zhang, An, Zhang, Liang, Chen, Yong, Chen, Guangting, and Wang, Xing
- Subjects
- *
APPROXIMATION algorithms , *PARALLEL algorithms , *MACHINERY , *SCHEDULING , *PRODUCTION scheduling - Abstract
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 9 5 -approximation algorithm for the problem with a fixed sequence. Then we show that the tight approximation ratios of the algorithm are 7 4 and 5 3 for two subproblems which remain strongly NP-hard. We also send an improved algorithm with approximation ratio 3 − 2 ≈ 1.586 for one subproblem. Finally, we prove that the problem without any fixed sequence is actually strongly NP-hard, and design a 5 3 -approximation algorithm. • Consider the problem of scheduling with conflict constraints on two parallel dedicated machines. • Present a 9 5 -approximation algorithm for the strongly NP-hard case where jobs on one machine have a fixed processing sequence, and give improvements to its hard subproblems. • Prove that the problem without any fixed sequence is strongly NP-hard too and propose a 5 3 -approximation algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF