标题： 具有机器成本约束的拒绝多处理器调度问题的EPTAS 显示英文标题

标题： An EPTAS for multiprocessor scheduling with rejection under a machine cost constraint

摘要： 我们研究在机器成本约束下的具有拒绝功能的多处理器调度问题。 在此问题中，每个作业要么被拒绝并产生拒绝惩罚，要么被接受并在其中一台机器上进行处理。 机器成本与在该机器上安排的作业的总处理时间成正比。 该问题的目标是在总机器成本不超过给定上限的前提下，最小化被接受作业的完成时间与被拒绝作业的总拒绝惩罚之和。 我们为该问题提出一个简单的$2$-近似算法，并且当机器数量$m$为固定常数时，我们获得了EPTAS。 显示英文摘要

摘要： We study the multiprocessor scheduling with rejection problem under a machine cost constraint. In this problem, each job is either rejected with a rejection penalty or; accepted and scheduled on one of the machines for processing. The machine cost is proportional to the total processing time of the jobs scheduled on it. The problem aims to minimize the makespan of accepted jobs plus the total rejection penalty of rejected jobs while the total machine cost does not exceed a given upper bound. We present a simple $2$-approximation algorithm for the problem and we achieve an EPTAS when the number $m$ of machines is a fixed constant.