如何在安排活动工作

Question

这是一个非常困难的动态规划的问题，我想与大家分享，我们可以讨论一点点朝其解决方案中获得最低的成本：

你会把你的新应用云服务器;你必须安排你的工作，以获得最低的成本。您无需关心在同一台服务器上同时运行的作业数量。每个工作k由一个发布时间sk，一个截止时间fk和一个持续时间dk给出，其中dk≤fk - sk。这项工作需要安排在时间sk和fk之间连续几分钟的时间间隔内。服务器公司将每台服务器每分钟收费。您只需要一个虚拟服务器，并且可以省钱将作业从sk移动到fk，从而最大限度地缩短时间，而无需运行任何作业，换句话说，可以最大限度地减少运行一个或多个作业的时间。采用动态规划解决问题。你的算法应该是n中的多项式，即作业的数量。

Answer 1

这是最小化繁忙时间的问题。

见定理17 this paper的：

罗希特Khandekar，巴鲁克希伯，哈达Shachnai和塔米塔米尔。最大限度地减少多台计算机的实时调度中的繁忙时间 。在软件技术的基础和理论计算机科学 （FSTTCS）第30届年会论文集，169页 - 180，2010

对于一个多项式时间算法的描述。

的关键是：

1. 为了实现还有一些需要考虑（如果你有一个时间表，考虑推迟每个忙碌的间隔，直到你打一个最后期限的工作之一，只有某些有趣的时光正在处理）

2. 要考虑何时完成最长的工期。这将问题分解成两部分;之前和之后，这可以以正常的动态编程方式独立解决。