Traveling Salesman Problem including Job scheduling.

What is it about?

This paper explores a problem related to both the Traveling Salesman Problem and Scheduling Problem where a traveler moves through n locations (nodes), visits all locations and each location exactly once to assign and initiate one of n jobs, and then returns to the first location. After initiation of a job, the traveler moves to the next location immediately and the job continues autonomously. This is representative of many practical scenarios including autonomous robotics, equipment maintenance, highly automated manufacturing, agricultural harvesting, and disaster recovery. The goal is to minimize the time of completion of the last job, i.e. makespan. Although the makespan objective typically is used in scheduling problems, the transportation times can be significant relative to the processing time, and this changes the optimization considerations. We refer to this problem as the Traveling Salesman Problem with Job-times (TSPJ) and present a mathematical formulation and local search improvement heuristics for it. Computational experience in solving the TSPJ using both commercial solvers and heuristics is reported. Keywords: Traveling Salesman Problem, Scheduling Problem, Assignment Problem, Sequence-dependent Setup-time, Min Makespan Link to free download: https://authors.elsevier.com/a/1cV7915N8SFYFw

Featured Image

Photo by Capturing the human heart. on Unsplash

Photo by Capturing the human heart. on Unsplash

Why is it important?

It is not a variation of the TSP or a new solution method. It is a new branch on TSP. We presented a basic problem and the variations are available for future researchers who are interested in continuing this research.

Perspectives