Journal
JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume 44, Issue 1, Pages 343-353Publisher
SPRINGER
DOI: 10.1007/s10878-021-00842-x
Keywords
Scheduling; Submodular function; Approximation algorithm
Funding
- NSF of China [11971146]
- NSF of Hebei Province of China [A2019205089, A2019205092]
- Hebei Province Foundation for Returnees [CL201714]
Ask authors/readers for more resources
This paper considers the parallel-machine scheduling problem with release dates and submodular rejection penalties, and designs a 2-approximation algorithm based on the primal-dual framework.
In this paper, we consider the parallel-machine scheduling problem with release dates and submodular rejection penalties. In this problem, we are given m identical parallel machines and n jobs. Each job has a processing time and a release date. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on one of the m identical parallel machines. The objective is to minimize the sum of the makespan of the accepted jobs and the rejection penalty of the rejected jobs which is determined by a submodular function. Our main work is to design a 2-approximation algorithm based on the primal-dual framework.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available