We consider several novel combinatorial optimization problems,which combine the classic shop scheduling problems(namely,flow shop scheduling,open shop scheduling or job shop scheduling)and the shortest path problem.The objective of the obtained problems 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 shop(flow shop,open shop 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 design several approximation algorithms for these combination problems.