Approximation Algorithm for the Single Machine Scheduling Problem with Release Dates and Submodular Rejection Penalty

Xiaofei Liu and Weidong Li
Additional contact information
Xiaofei Liu: School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China
Weidong Li: School of Mathematics and Statistics, Yunnan University, Kunming 650504, China

Mathematics, 2020, vol. 8, issue 1, 1-11

Abstract: In this paper, we consider the single machine scheduling problem with release dates and nonmonotone submodular rejection penalty. We are given a single machine and multiple jobs with probably different release dates and processing times. For each job, it is either accepted and processed on the machine or rejected. 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 nonmonotone submodular function. We design a combinatorial algorithm based on the primal-dual framework to deal with the problem, and study its property under two cases. For the general case where the release dates can be different, the proposed algorithm have an approximation ratio of 2. When all the jobs release at the same time, the proposed algorithm becomes a polynomial-time exact algorithm.

Keywords: scheduling; submodular rejection penalty; approximation algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/1/133/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/1/133/ (text/html)

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:gam:jmathe:v:8:y:2020:i:1:p:133-:d:309327

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().