The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling

The time-dependent traveling salesman problem may be stated as a scheduling problem in which n jobs have to be processed at minimum cost on a single machine. The set-up cost associated with each job depends not only on the job that precedes it, but also on its position (time) in the sequence. The optimization method described here combines finding shortest paths in an associated multipartite network with subgradient optimization and some branch-and-bound enumeration. Minimizing the tardiness costs in one-machine scheduling (in which the cost is a non-decreasing function of the completion time of each job) is then attacked by this method. A branch-and-bound algorithm is designed for this problem. It uses a related time-dependent traveling salesman problem to compute the required lower bounds. We give computational results for the weighted tardiness problem.