Back to Search
Start Over
Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints.
- Source :
-
Theoretical Computer Science . Jan2023, Vol. 941, p167-179. 13p. - Publication Year :
- 2023
-
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]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 941
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 160820040
- Full Text :
- https://doi.org/10.1016/j.tcs.2022.11.012