Linear time approximation schemes for vehicle scheduling problems

DOI10.1016/j.tcs.2004.05.013zbMath1091.90015OpenAlexW2092293193MaRDI QIDQ1887080

Steven S. Seiden, John E. Augustine

Publication date: 23 November 2004

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

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

zbMATH Keywords

Dynamic programmingApproximation algorithmPolynomial time approximation schemeVehicle scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39) Approximation algorithms (68W25)

Related Items (7)

Strip packing with precedence constraints and strip packing with release times ⋮ Routing open shop and flow shop scheduling problems ⋮ Scheduling on a graph with release times ⋮ Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle ⋮ Single-vehicle scheduling problems with release and service times on a line ⋮ Improved algorithms for single vehicle scheduling on tree/cycle networks ⋮ Vehicle scheduling problems with two agents on a line

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Euclidean traveling salesman problem is NP-complete
• Vehicle scheduling on a tree with release and handling times
• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• Routing and Scheduling on a Shoreline with Release Times
• Special cases of traveling salesman and repairman problems with time windows
• Complexity of Task Sequencing with Deadlines, Set-Up Times and Changeover Costs
• VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
• Complexity Of The Single Vehicle Scheduling Problem On Graphs
• Reducibility among Combinatorial Problems

This page was built for publication: Linear time approximation schemes for vehicle scheduling problems