Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints

DOI10.1007/978-3-030-92681-6_10OpenAlexW4206038303MaRDI QIDQ2149860

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

Publication date: 29 June 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-92681-6_10

zbMATH Keywords

approximation algorithmNP-hardparallel dedicated machinesconflict graph

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

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: Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints