A 53-approximation algorithm for scheduling vehicles on a path with release and handling times

DOI10.1016/S0020-0190(02)00474-XMaRDI QIDQ1007578zbMATH OpenOpenAlexFDO

Authors Daya Ram Gaur, Ramesh Krishnamurti, Arvind Kumar Gupta

Publication date 23 March 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(02)00474-x

zbMATH Keywords

approximation algorithmsdesign of algorithms

Mathematics Subject Classification ID

Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• scientific article; zbMATH DE number 1875418
• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• scientific article; zbMATH DE number 2080977
• An approximability result of the multi-vehicle scheduling problem on a path with release and handling times
• Single Vehicle Scheduling Problems on Path/Tree/Cycle Networks with Release and Handling Times

Cites work

• scientific article; zbMATH DE number 2080977 (Why is no real title available?)
• scientific article; zbMATH DE number 1875418 (Why is no real title available?)
• Routing and Scheduling on a Shoreline with Release Times
• Special cases of traveling salesman and repairman problems with time windows
• Vehicle scheduling on a tree with release and handling times

Cited in

(15)

• Vehicle routing problems on a line-shaped network with release time constraints
• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• An approximability result of the multi-vehicle scheduling problem on a path with release and handling times
• Improved algorithms for single vehicle scheduling on tree/cycle networks
• Vehicle scheduling problems with two agents on a line
• Routing and scheduling problems with two agents on a line-shaped network
• Data mule scheduling on a path with handling time and time span constraints
• Survey of research in the design and control of automated guided vehicle systems
• Single-vehicle scheduling problems with release and service times on a line
• Routing open shop and flow shop scheduling problems
• Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle
• Emergency path restoration problems
• scientific article; zbMATH DE number 1875418 (Why is no real title available?)
• Scheduling on a graph with release times
• The multiple traveling salesman problem on spiders

This page was built for publication: A \(\frac{5}{3}\)-approximation algorithm for scheduling vehicles on a path with release and handling times

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1007578)