Approximation algorithms for two-machine flow-shop scheduling with a conflict graph

DOI10.1007/978-3-319-94776-1_18OpenAlexW2963222815MaRDI QIDQ1790974

An Zhang, Randy Goebel, Yinhui Cai, Yong Chen, Longcheng Liu, Guangting Chen, Guo-Hui Lin

Publication date: 4 October 2018

Full work available at URL: https://arxiv.org/abs/1803.02862

zbMATH Keywords

approximation algorithm\(b\)-matchingpath coverconflict graphflow-shop scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (3)

Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph ⋮ New complexity results for shop scheduling problems with agreement graphs ⋮ Two-machine open shop problem with agreement graph

This page was built for publication: Approximation algorithms for two-machine flow-shop scheduling with a conflict graph