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

Jean-Claude Picard and Maurice Queyranne
Additional contact information
Jean-Claude Picard: Federal University of Paraiba, Campina Grande, Brazil
Maurice Queyranne: Ecole Polytechnique, Montreal, Quebec

Operations Research, 1978, vol. 26, issue 1, 86-110

Abstract: 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.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (53)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.26.1.86 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:26:y:1978:i:1:p:86-110

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().