Heuristics for a scheduling problem of minimizing the number of one驴way vehicles on paths with deadlines

摘要

In this paper, we deal with a vehicle scheduling problem on paths with handling times and deadlines. Let G = (V,E) be a path with a set V = {驴i | i = 1, 2, . . . , n} of vertices and a set E = {{驴i, 驴i+1} | i = 1, 2, . . . , n - 1} of edges. Vehicles are initially situated at v1.There is a job i at each vertex {驴i 驴 V, which has its own handling time hi and deadline di. With each edge {vi, vi+1} 驴 E, a travel time wi,i+1 is associated. A routing of a vehicle is called one-way if the vehicle visits every edge {vi, vi+1} exactly once (i.e., it simply moves from v1 to vn on G). Any vehicle is assumed to move on G under the one-way routing constraint. The problem asks to find a schedule of one-way vehicles that minimizes the number of vehicles, meeting the deadline constraints for all jobs. In this paper, we propose an iterative DP heuristic algorithm to the problem, and show that it runs in O(n3) time and the approximation ratio is O(log n).