A study on several combination problems of classic shop scheduling and shortest path

In this paper, we study several combinatorial optimization problems which combine the classic open shop or job shop scheduling problem and the shortest path problem. Our goal is to select a subset of jobs that constitutes a feasible solution of the shortest path problem, and then execute the selected jobs on the shop machines to minimize the makespan, i.e., the last completion time of all the jobs. We prove that these problems are NP-hard even if there are two machines. If the number of machines is an input, we show that it is unlikely to find approximation algorithms with performance ratios better than 2 unless P=NP. We present an intuitive approximation algorithm when the number of machines is an input, and an improved approximation algorithm when the number of machines is fixed. In addition, we propose a polynomial time approximation scheme for the open shop case when the number of machines is fixed.