文献类型：期刊文献

英文题名：New approximation algorithms for machine scheduling with rejection on single and parallel machine

作者：Liu, Peihai[1];Lu, Xiwen[1]

机构：[1]East China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China

年份：2020

卷号：40

期号：4

起止页码：929

外文期刊名：JOURNAL OF COMBINATORIAL OPTIMIZATION

收录：;EI(收录号：20203609134529);WOS:【SCI-EXPANDED(收录号:WOS:000566359600002)】；

基金：This work was supported by the National Nature Science Foundation of China (11871213) and the Natural Science Foundation of Shanghai under Grant Number 19ZR1411800.

语种：英文

外文关键词：Scheduling; Rejection; Release date; Approximation algorithm; Worst-case ratio

摘要：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.