Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph

DOI10.1007/s10878-021-00793-3zbMath1490.90238OpenAlexW3194595331MaRDI QIDQ2125230

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

Publication date: 13 April 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-021-00793-3

zbMATH Keywords

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

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items (2)

Path cover problems with length cost ⋮ Path cover problems with length cost

Cites Work

• Unnamed Item
• Unnamed Item
• Restrictions of graph partition problems. I
• Scheduling with conflicts: Online and offline algorithms
• The two-equal-disjoint path cover problem of matching composition network
• Scheduling subject to resource constraints: Classification and complexity
• Approximability of flow shop scheduling
• Mutual exclusion scheduling
• Multicoloring trees.
• Flow shop scheduling problem with conflict graphs
• Scheduling jobs on identical machines with agreement graph
• Approximation algorithms for two-machine flow-shop scheduling with a conflict graph
• Algorithmic graph theory and perfect graphs
• HAMILTONian circuits in chordal bipartite graphs
• A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
• Nontrivial path covers of graphs: existence, minimization and maximization
• Optimal two- and three-stage production schedules with setup times included
• Some new results in flow shop scheduling
• Scheduling unit-time tasks in renewable resource constrained flowshops
• Bounds for Multiprocessor Scheduling with Resource Constraints
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Flowshop and Jobshop Schedules: Complexity and Approximation
• The Complexity of Flowshop and Jobshop Scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A New Heuristic for Three-Machine Flow Shop Scheduling
• Short Shop Schedules
• A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs

This page was built for publication: Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph