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

被引:11
作者
Liu, Xiaofei [1 ]
Li, Weidong [2 ]
机构
[1] Peking Univ, Sch Elect Engn & Comp Sci, Beijing 100871, Peoples R China
[2] Yunnan Univ, Sch Math & Stat, Kunming 650504, Yunnan, Peoples R China
基金
中国国家自然科学基金;
关键词
scheduling; submodular rejection penalty; approximation algorithm; SUBJECT; TIMES;
D O I
10.3390/math8010133
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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.
引用
收藏
页数:11
相关论文
共 24 条
[1]   Multiprocessor scheduling with rejection [J].
Bartal, Y ;
Leonardi, S ;
Marchetti-Spaccamela, A ;
Sgall, J ;
Stougie, L .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (01) :64-78
[2]   A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties [J].
Du, Donglei ;
Lu, Ruixing ;
Xu, Dachuan .
ALGORITHMICA, 2012, 63 (1-2) :191-200
[3]   A push-relabel framework for submodular function minimization and applications to parametric optimization [J].
Fleischer, L ;
Iwata, S .
DISCRETE APPLIED MATHEMATICS, 2003, 131 (02) :311-322
[4]   Improved algorithms for single machine scheduling with release dates and rejections [J].
He, Cheng ;
Leung, Joseph Y. -T. ;
Lee, Kangbok ;
Pinedo, Michael L. .
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2016, 14 (01) :41-55
[5]   A combinatorial strongly polynomial algorithm for minimizing submodular functions [J].
Iwata, S ;
Fleischer, L ;
Fujishige, S .
JOURNAL OF THE ACM, 2001, 48 (04) :761-777
[6]   OPTIMAL SEQUENCING OF A SINGLE MACHINE SUBJECT TO PRECEDENCE CONSTRAINTS [J].
LAWLER, EL .
MANAGEMENT SCIENCE SERIES A-THEORY, 1973, 19 (05) :544-546
[7]   Vector scheduling with rejection on a single machine [J].
Li, Weidong ;
Cui, Qianna .
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2018, 16 (01) :95-104
[8]   Penalty cost constrained identical parallel machine scheduling problem [J].
Li, Weidong ;
Li, Jianping ;
Zhang, Xuejie ;
Chen, Zhibin .
THEORETICAL COMPUTER SCIENCE, 2015, 607 :181-192
[9]   Improved Approximation Algorithms for the Facility Location Problems with Linear/Submodular Penalties [J].
Li, Yu ;
Du, Donglei ;
Xiu, Naihua ;
Xu, Dachuan .
ALGORITHMICA, 2015, 73 (02) :460-482
[10]   Faster algorithms for single machine scheduling with release dates and rejection [J].
Ou, Jinwen ;
Zhong, Xueling ;
Li, Chung-Lun .
INFORMATION PROCESSING LETTERS, 2016, 116 (08) :503-507