  We consider several combinatorial optimization problems which combine the
classic shop scheduling problems, namely open shop scheduling or job shop
scheduling, and the shortest path problem. The objective of the obtained
problem is to select a subset of jobs that forms a feasible solution of the
shortest path problem, and to execute the selected jobs on the open (or job)
shop machines to minimize the makespan. We show that these problems are NP-hard
even if the number of machines is two, and cannot be approximated within a
factor less than 2 if the number of machines is an input unless P=NP. We
present several approximation algorithms for these combination problems.
