Routing Two-Machine Flowshop Problems on Networks with Special Structure

We consider a version of the routing two-machine flowshop problem, where n jobs located at different nodes of a transportation network must be executed by two machines traveling between the jobs. Each job must be processed by both machines in the order, machine 1 first, machine 2 second. The goal is to minimize the makespan given that the total distance traveled must be as small as possible. Properties of the problem are discussed, and algorithms with complexity O(n log n) are developed for the problem on trees and cactuses.