Parallel-Machine Scheduling Problem under the Job Rejection Constraint - (Extended Abstract)
Parallel-Machine Scheduling Problem under the Job Rejection Constraint - (Extended Abstract)
复制标题
DOI：
10.1007/978-3-319-08016-1_15
复制
发表时间：
2014-06
影响因子：
7.8
通讯作者：
Weidong Li;Jianping Li;Xuejie Zhang;Zhibin Chen
中科院分区：
文献类型：
--
作者：
Weidong Li;Jianping Li;Xuejie Zhang;Zhibin Chen
给定相同的机器和独立的作业，每个作业都有一个处理时间（或大小）和一个惩罚。一个作业可以被拒绝，在这种情况下，它的惩罚被支付，或者在其中一台机器上安排，在这种情况下，它的处理时间有助于该机器的负载。目标是在拒绝作业的总惩罚不超过给定的boundB的约束下，最小化接受作业的计划的完工时间。本文给出了一种强多项式时间内的二次逼近算法和一种运行时间为一般情况的多项式时间逼近格式。此外，对于机器数量为固定常数的情况，我们给出了一个全多项式时间逼近格式。该结果改进了以往mo (nm+ 2/εm) toO（1/ε2m+ 3+mn2）的最佳运行时间。
Givenmidentical machines andnindependent jobs, each jobJjhas a processing time (or size)pjand a penaltyej. A job can be either rejected, in which case its penalty is paid, or scheduled on one of the machines, in which case its processing time contributes to the load of that machine. The objective is to minimize the makespan of the schedule for accepted jobs under the constraint that the total penalty of the rejected jobs is no more than a given boundB. In this paper, we present a 2-approximation algorithm within strongly polynomial time and a polynomial time approximation scheme whose running time isfor the general case. Moreover, we present a fully polynomial time approximation scheme for the case where the number of machines is a fixed constant. This result improves previous best running time fromO(nm+ 2/εm) toO(1/ε2m+ 3+mn2) .