Indexed by:
Abstract:
We study a precedence-constrained identical parallel machine scheduling problem with rejection. There is a communication delay between any two jobs connected in the precedence network where jobs may be rejected with penalty. The goal is to minimize the sum of the makespan and the rejection cost. We propose two 3-approximation algorithms for this problem under linear and submodular rejection costs respectively. These two algorithms are both based on linear programming rounding technique.
Keyword:
Reprint Author's Address:
Email:
Source :
JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN: 1382-6905
Year: 2018
Issue: 1
Volume: 35
Page: 318-330
1 . 0 0 0
JCR@2022
ESI Discipline: MATHEMATICS;
ESI HC Threshold:63
JCR Journal Grade:3
Cited Count:
WoS CC Cited Count: 22
SCOPUS Cited Count: 25
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 2
Affiliated Colleges: