A Combinatorial 2-Approximation Algorithm for the Parallel-Machine Scheduling with Release Times and Submodular Penalties

Wencheng Wang and Xiaofei Liu
Additional contact information
Wencheng Wang: School of Mathematics and Statistics, Yunnan University, Kunming 650500, China
Xiaofei Liu: School of Information Science and Engineering, Yunnan University, Kunming 650500, China

Mathematics, 2021, vol. 10, issue 1, 1-10

Abstract: In this paper, we consider parallel-machine scheduling with release times and submodular penalties ( P | r j , r e j e c t | C max + π ( R ) ), in which each job can be accepted and processed on one of m identical parallel machines or rejected, but a penalty must paid if a job is rejected. Each job has a release time and a processing time, and the job can not be processed before its release time. The objective of P | r j , r e j e c t | C max + π ( R ) is to minimize the makespan of the accepted jobs plus the penalty of the rejected jobs, where the penalty is determined by a submodular function. This problem generalizes a multiprocessor scheduling problem with rejection, the parallel-machine scheduling with submodular penalties, and the single machine scheduling problem with release dates and submodular rejection penalties. In this paper, inspired by the primal-dual method, we present a combinatorial 2-approximation algorithm to P | r j , r e j e c t | C max + π ( R ) . This ratio coincides with the best known ratio for the parallel-machine scheduling with submodular penalties and the single machine scheduling problem with release dates and submodular rejection penalties.

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

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/1/61/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/1/61/ (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:10:y:2021:i:1:p:61-:d:711094

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 ().