标题： 具有约束拒绝的调度问题 显示英文标题

标题： Scheduling Problems with Constrained Rejections

摘要： 我们研究了在不同机器上进行总完成时间最小化的双准则版本以及圣诞老人问题，通过允许有限数量的拒绝。 给定一个不同机器上总完成时间最小化的实例，其中在$m$台不同机器上调度$n$个作业的最优总完成时间为$T$，(Feige 和 Vondrák, 2006) 提供了一个算法，在时间$T$内调度了$(1-1/e+10^{-180})$的作业。 我们表明，如果我们允许总完成时间$3T/2$，这个比率可以改进到$0.6533>1-1/e+0.02$。 据我们所知，这是首次研究在makespan不是$T$或$2T$时，makespan与调度作业比例之间的权衡结果。 对于圣塔克劳斯问题（Makespan Minimization的Max-Min版本），类似的双准则目标由（Golovin，2005）研究过，他提出了一种算法，使得对于任何$k \in \mathbb{Z}^+$和$T$，即每个代理可以获得的最佳最小值，分配使得至少$(1-1/k)$比例的代理获得的价值至少为$T/k$。 我们通过证明存在常数$\delta,\varepsilon>0$使得找到一个分配，其中 a$(1-\delta)$的代理获得的价值至少为$(1-\varepsilon) T$是 NP 困难的，提供了第一个硬度结果。 为了证明这个硬度结果，我们引入了 Set Packing 的双准则版本，这可能具有独立的兴趣，并为其证明了一些算法和硬度结果。 总体而言，我们认为这些双准则调度问题值得进一步研究，因为它们提供了一个有趣的视角来理解原始优化目标的难度可能有多稳健。 显示英文摘要

摘要： We study bicriteria versions of Makespan Minimization on Unrelated Machines and Santa Claus by allowing a constrained number of rejections. Given an instance of Makespan Minimization on Unrelated Machines where the optimal makespan for scheduling $n$ jobs on $m$ unrelated machines is $T$, (Feige and Vondr\'ak, 2006) gave an algorithm that schedules a $(1-1/e+10^{-180})$ fraction of jobs in time $T$. We show the ratio can be improved to $0.6533>1-1/e+0.02$ if we allow makespan $3T/2$. To the best our knowledge, this is the first result examining the tradeoff between makespan and the fraction of scheduled jobs when the makespan is not $T$ or $2T$. For the Santa Claus problem (the Max-Min version of Makespan Minimization), the analogous bicriteria objective was studied by (Golovin, 2005), who gave an algorithm providing an allocation so a $(1-1/k)$ fraction of agents receive value at least $T/k$, for any $k \in \mathbb{Z}^+$ and $T$ being the optimal minimum value every agent can receive. We provide the first hardness result by showing there are constants $\delta,\varepsilon>0$ such that it is NP-hard to find an allocation where a $(1-\delta)$ fraction of agents receive value at least $(1-\varepsilon) T$. To prove this hardness result, we introduce a bicriteria version of Set Packing, which may be of independent interest, and prove some algorithmic and hardness results for it. Overall, we believe these bicriteria scheduling problems warrant further study as they provide an interesting lens to understand how robust the difficulty of the original optimization goal might be.