Improved approximation algorithms for the combination problem of parallel machine scheduling and path

Li Guan, Jianping Li, Weidong Li () and Junran Lichen
Additional contact information
Li Guan: Yunnan University
Jianping Li: Yunnan University
Weidong Li: Yunnan University
Junran Lichen: Yunnan University

Journal of Combinatorial Optimization, 2019, vol. 38, issue 3, No 3, 689-697

Abstract: 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}$$ P st of the given directed graph, and to schedule the jobs corresponding to the arcs of the path $$P_{st}$$ 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.

Keywords: Parallel machine scheduling; Shortest path; Approximation algorithm; Polynomial time approximation scheme (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00406-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:3:d:10.1007_s10878-019-00406-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00406-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().