论文标题
安排许多共享资源
Scheduling with Many Shared Resources
论文作者
论文摘要
考虑许多共享的资源调度问题，其中必须在相同的平行机上安排作业，以最大程度地减少MakePan。但是，每个作业都需要一个附加的共享资源才能执行并防止在处理时执行需要相同资源的作业。以前是$（200万/（M+1））$ - 近似是此问题的最著名结果。此外，只有两台机器的案件的$ 6/5 $ - 附件均已知道，以及具有恒定机器数量的外壳的PTA。我们提出了一个简单而快速的5/3 approximation，并且涉及更多但仍然是合理的1.5 Approximation。此外，我们为只有恒定数量的机器的情况提供了一个PTA，可以说，这比以前已知的机器更简单，更快，以及具有资源增强的PTA。近似方案利用了N折内整数编程机械，该机械最近在调度领域中发现了越来越多的应用程序。可以改善后一个结果并扩展到更一般的情况是合理的。最后，我们给出了$ 5/4- \ varepsilon $ inapproximability rapproximability结果，因为自然问题扩展是每个作业可能需要多达不同资源的恒定数字（尤其是$ 3 $）。
Consider the many shared resource scheduling problem where jobs have to be scheduled on identical parallel machines with the goal of minimizing the makespan. However, each job needs exactly one additional shared resource in order to be executed and hence prevents the execution of jobs that need the same resource while being processed. Previously a $(2m/(m+1))$-approximation was the best known result for this problem. Furthermore, a $6/5$-approximation for the case with only two machines was known as well as a PTAS for the case with a constant number of machines. We present a simple and fast 5/3-approximation and a much more involved but still reasonable 1.5-approximation. Furthermore, we provide a PTAS for the case with only a constant number of machines, which is arguably simpler and faster than the previously known one, as well as a PTAS with resource augmentation for the general case. The approximation schemes make use of the N-fold integer programming machinery, which has found more and more applications in the field of scheduling recently. It is plausible that the latter results can be improved and extended to more general cases. Lastly, we give a $5/4 - \varepsilon$ inapproximability result for the natural problem extension where each job may need up to a constant number (in particular $3$) of different resources.
