A study on several combination problems of classic shop scheduling and shortest path

DOI10.1016/j.tcs.2015.12.027zbMath1353.90131OpenAlexW2213043031MaRDI QIDQ344790

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

Publication date: 24 November 2016

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

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

zbMATH Keywords

shortest pathapproximation algorithmopen shopjob shopcombination of optimization problemsshop scheduling

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

Shop scheduling in manufacturing environments: a review, On the approximability of the two-phase knapsack problem, Improved approximation algorithms for the combination problem of parallel machine scheduling and path

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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