多机调度的几何

作者：Nikhil Bansal,Jatin Batra

摘要：我们考虑以下一般调度问题：在时间0处有m个相同的机器和n个作业都被释放。每个作业j具有处理时间pj，以及指定j的成本的任意非递减函数fj，对于每个可能的完成时间。目标是找到最低成本的先发制人迁移计划。这模拟了几个自然目标，例如加权完成时间范围，加权延迟等等。

我们给出了该问题的第一个O（1）近似算法，改进了由Moseley（2019）引起的O（loglognP）约束。为此，我们首先从几何上看Moseley的工作覆盖不等式，将问题减少到用矩形和三角形容量剖面覆盖线上需求的问题。由于三角形的容量不均匀，直接使用准均匀采样会丢失O（loglogP）因子，因此第二个想法是使其适应我们的设置以仅丢失O（1）因子。我们关于覆盖具有非均匀容量概况（以前未进行过研究）的点的想法可能具有独立的意义。

原文标题：Geometry of Scheduling on Multiple Machines

原文摘要：We consider the following general scheduling problem: there aremidentical machines and n jobs all released at time0. Each job j has a processing time pj, and an arbitrary non-decreasing functionfjthat specifies the cost incurred forj, for each possible completion time. The goal is to find a preemptive migratory schedule of minimum cost. This models several natural objectives such as weighted norm of completion time, weighted tardiness and much more.

We give the firstO(1)approximation algorithm for this problem, improving upon theO(loglognP)bound due to Moseley (2019). To do this, we first view the job-cover inequalities of Moseley geometrically, to reduce the problem to that of covering demands on a line by rectangular and triangular capacity profiles. Due to the non-uniform capacities of triangles, directly using quasi-uniform sampling loses aO(loglogP)factor, so a second idea is to adapt it to our setting to only lose anO(1)factor. Our ideas for covering points with non-uniform capacity profiles (which have not been studied before) may be of independent interest.

地址：https://arxiv.org/abs/1907.05473