The　Traveling　Salesman　Problem　with　Job-times　(TSPJ)　is　an　extension　problem　that　integrates　the　Traveling　Salesman　Problem　and　the　Job　Scheduling　Problem.　TSPJ　refers　to　finding　the　optimal　route　for　a　salesman　to　visit　each　location　exactly　once　while　assigning　one　job　to　each　location.　Each　job　can　only　be　assigned　once,　and　its　completion　time　depends　on　the　assigned　location.　The　objective　of　the　TSPJ　is　to　minimize　the　maximum　completion　time　of　all　jobs.　This　paper　studies　the　problem　from　a　new　perspective　and　illustrates　the　realistic　application　scenarios　of　TSPJ.　To　solve　the　problem　efficiently,　we　propose　a　Variable　Neighborhood　Search　algorithm　embedded　in　an　adaptive　shaking　strategy　and　an　intensive　local　search　procedure.　The　adaptive　shaking　strategy　invokes　the　small-perturbation　or　large-perturbation　strategy　according　to　the　searching　states　and　results　during　the　searching　procedure.　In　the　proposed　local　search　procedure,　the　first　improvement　strategy　is　adopted　and　the　parameter　of　perturbation　strength　is　updated　for　the　following　procedures.　Experimental　results　on　310　benchmark　instances　demonstrate　that　the　proposed　algorithm　outperforms　the　state-of-the-art　heuristic　methods.　In　particular,　the　best-known　solutions　are　improved　in　241　instances　and　the　proposed　algorithm　can　obtain　the　same　results　as　the　best-known　solutions　in　60　instances.　Two　statistical　tests　show　that　the　results　obtained　by　the　proposed　algorithm　have　significant　differences　from　those　of　the　compared　methods　and　therefore　verify　the　superiority　of　our　method.