Single-vehicle scheduling with time window constraints

Single-vehicle scheduling with time window constraints

0.00 Avg rating0 Votes
Article ID: iaor2001742
Country: United Kingdom
Volume: 2
Issue: 4
Start Page Number: 175
End Page Number: 187
Publication Date: Jul 1999
Journal: Journal of Scheduling
Authors: ,
Abstract:

In the single-vehicle scheduling problem with time window constraints, a vehicle has to visit a set of sites on a graph, and each site must be visited after its ready time but no later than its deadline. The goal is to minimize the total time taken to visit all sites. We prove the conjecture proposed by Psaraftis et al.: if the topological graph is a straight line, the problems are NP-hard for both part and tour version. In addition, we give an O(n2) algorithm to solve a special case where all sites have a common ready time. This algorithm illustrates a duality relationship between the vehicle scheduling problems with arbitrary ready times and that with arbitrary deadlines on a straight line.

Reviews

Required fields are marked *. Your email address will not be published.