Let G = (V,E) be a graph. The travel times w(u, v) and w(v,u) are associated with each edge {u,v} ∈ E, and a job, which is also denoted as v, is located at each vertex v ∈ V. Each job v has release time r(v) and handling time h(v). A start vertex s ∈ V and a set Q ⊆ V of goal vertices are specified. The VSP (vehicle scheduling problem) asks to find a routing schedule of the single vehicle that starts from vertex s at time 0 and reaches one of the goal vertices in Q after visiting all jobs v ∈ V for processing. The processing of a job v cannot be started before its release time t = r(v) (hence the vehicle has to wait if it arrives at v before r(v) for processing) and takes h(v time units once its processing has started (no interruption is allowed). The objective is to find a schedule that minimizes the completion time i.e., the time to process all jobs). We first establish a dynamic programming algorithm for solving VSP on a general graph, and show that VSP can be solved in O(nb) time when G is a tree with b leaves and all handling times are zero. We then prove that VSP is strongly NP-hard even if graph G is a general tree and all handling times are zero.
