Complexity Of The Single Vehicle Scheduling Problem On Graphs

AbstractLet 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 ...