Approximating a vehicle scheduling problem with time windows and handling times

In this paper, we study a problem of finding a vehicle scheduling to process a set of n jobs which are located in an asymmetric metric space. Each job j has a positive handling time h(j), a time window [r(j),d(j)], and a benefit b(j). We consider the following two problems: MAX-VSP asks to find a schedule for a single vehicle to process a subset of jobs with the maximum benefit; and MIN-VSP asks to find a schedule to process all given jobs with the minimum number of vehicles. We first give an O(ρn3+γ) time algorithm that delivers a 2-approximate solution to MAX-VSP, where ρ=maxj,j′(d(j)−r(j))/h(j′) and γ is the maximum number of jobs that can be processed by the vehicle after processing a job j and before visiting the processed job j again by deadline d(j). We then present an O(ρn4+γ) time algorithm that delivers a 2H(n)-approximate solution to MIN-VSP, where H(n) is the nth harmonic number.