Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle

We consider the single vehicle scheduling problem in which the customers are located at the vertices of a tree or a cycle, and have release and service time requirements. The objective is to minimize the makespan. In the tour-version the makespan means the time when the vehicle returns to its initial location after serving all customers. While in the path-version the makespan refers to the maximum completion time of all customers. For the problem on a tree, we present a 9/5-approximation algorithm for the tour-version and a 27/14-approximation algorithm for the path-version. For the problem on a cycle, we present 12/7-approximation algorithms for both versions.