Paper Info
Title
New Approximation Algorithms For Machine Scheduling With Rejection On Single And Parallel Machine
Abstract
In this paper we consider three machine scheduling problems with the special feature that jobs may be rejected at a certain penalty. There are n jobs which are characterized by a release date, a processing time and a penalty. Each job is either accepted and then processed by one machine, or rejected and then a rejection penalty is paid. The objective is to minimize the maximum completion time of all accepted job plus the total penalties of all rejected jobs. When jobs have identical release dates, we present a (3/2 - 1/2m)-approximation algorithm for the parallel machine problem. When jobs have general release dates, we propose a 4/3-approximation algorithm for the single machine problem and a (1 + max{0.618, 1 - 1/m})-approximation algorithm for the parallel machine problem, respectively.
Year
DOI
Venue
2020
10.1007/s10878-020-00642-9
JOURNAL OF COMBINATORIAL OPTIMIZATION
Keywords
DocType
Volume
Scheduling, Rejection, Release date, Approximation algorithm, Worst-case ratio
Journal
40
Issue
ISSN
Citations 
4
1382-6905
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Peihai Liu1526.01
Xiwen Lu218221.03