Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms

DOI10.1007/978-3-319-21398-9_8zbMath1353.90130arXiv1309.0082OpenAlexW1606021957MaRDI QIDQ3196375

Kameng Nip, Zhen-bo Wang, Wen-Xun Xing

Publication date: 29 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

schedulingshortest pathapproximation algorithmopen shopjob shopcombination of optimization problems

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (1)

On the approximability of the two-phase knapsack problem

Cites Work

• A note on two problems in connexion with graphs
• Combination of parallel machine scheduling and vertex cover
• Makespan minimization in open shops: A polynomial time approximation scheme
• A combination of flow shop scheduling and the shortest path problem
• Optimal two- and three-stage production schedules with setup times included
• Approximating Min-Max (Regret) Versions of Some Polynomial Problems
• Open Shop Scheduling to Minimize Finish Time
• Computational Complexity of Discrete Optimization Problems
• Improved Approximation Algorithms for Shop Scheduling Problems
• Short Shop Schedules
• Makespan Minimization in Job Shops: A Linear Time Approximation Scheme
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Combination of Two-Machine Flow Shop Scheduling and Shortest Path Problems
• Hardness of Approximating Flow and Job Shop Scheduling Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms