Advertisement
Published in:
26-03-2019
Improved approximation algorithms for the combination problem of parallel machine scheduling and path
Published in: Journal of Combinatorial Optimization | Issue 3/2019
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In this paper, we study a combination problem of parallel machine scheduling and the s–t path problem, which is to find a s–t path \(P_{st}\) of the given directed graph, and to schedule the jobs corresponding to the arcs of the path \(P_{st}\) on m parallel machines, such that the makespan is minimized. It has been proved that this problem is NP-hard and admits 2-approximation algorithm. We present a polynomial-time algorithm with approximation ratio 1.5. By modifying the dynamic programming method for the restricted shortest path problem, we also give a polynomial time approximation scheme.