We investigate a generalization of classical shop scheduling where
jobs are located at the vertices of a general undirected graph and
machines must travel between the vertices to process the jobs. The aim is to minimize the makespan. For the open shop problem, we develop an
)-approximation algorithm that significantly improves upon the best known
-approximation algorithm. For the flow shop problem, we present an
)-approximation algorithm that improves upon the best known
-approximation algorithm, where
is the approximation factor for metric TSP.