SPECIAL CASES OF TRAVELING SALESMAN AND REPAIRMAN PROBLEMS WITH TIME WINDOWS

Consider a complete directed graph in which each arc has a given length. There is a set of jobs, each job i located at some node of the graph, with an associated processing time h(i), and whose execution has to start within a prespecified time window [r(i), d(i)]. We have a single server that can move on the arcs of the graph, at unit speed, and that has to execute all of the jobs within their respective time windows, We consider the following two problems: (a) minimize the time by which all jobs are executed (traveling salesman problem) and (b) minimize the sum of the waiting times of the jobs (traveling repairman problem). We focus on the following two special cases: (a) The jobs are located on a line and (b) the number of nodes of the graph is bounded by some integer constant B. Furthermore, we consider in detail the special cases where (a) all of the processing times are 0, (b) all of the release times r(i) are 0, and (c) all of the deadlines d(i) are infinite. For many of the resulting problem combinations, we settle their complexity either by establishing NP-completeness or by presenting polynomial (or pseudopolynomial) time algorithms. Finally, we derive algorithms for the case where, for any time t, the number of jobs that can be executed at that time is bounded.