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

DOI10.1016/j.tcs.2022.11.012OpenAlexW4310061950MaRDI QIDQ2680859

Yong Chen, Guangting Chen, Liang Zhang, Xing Wang, An Zhang

Publication date: 4 January 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.11.012

zbMATH Keywords

approximation algorithmNP-hardparallel dedicated machinesconflict graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Restrictions of graph partition problems. I
• Scheduling with conflicts: Online and offline algorithms
• The complexity of generalized clique packing
• NP-completeness of graph decomposition problems
• The hardness of approximation: Gap location
• Mutual exclusion scheduling
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Multicoloring trees.
• Scheduling problems for parallel dedicated machines under multiple resource constraints.
• Scheduling jobs on identical machines with agreement graph
• Scheduling parallel dedicated machines under a single non-shared resource
• New results in two identical machines scheduling with agreement graphs
• Scheduling: agreement graph vs resource constraints
• Packing-Based Approximation Algorithm for the k-Set Cover Problem
• Bounds for Multiprocessor Scheduling with Resource Constraints

This page was built for publication: Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints