Premium
Special cases of traveling salesman and repairman problems with time windows
Author(s) -
Tsitsiklis John N.
Publication year - 1992
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230220305
Subject(s) - travelling salesman problem , time complexity , computer science , bounded function , combinatorics , graph , discrete mathematics , mathematics , theoretical computer science , algorithm , mathematical analysis
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 presepecified 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.