2013/08/31 by Kameng Nip, Nip, Kameng, Zhenbo Wang +3
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Optimization and Search Problems #Scheduling and Optimization Algorithms #cs.DS
paper · pdf · doi:10.48550/arxiv.1309.0082
19 pages, 1 figure
arxiv created 2013/08/31 · openalex publication_date 2013/08/31 · arxiv updated 2013/09/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.