问题我有n个作业要在P秒钟内在不限数量的具有作业之间相关性的机器上进行调度，即对于每个作业，只有在完成该作业后才安排一组作业。在任何机器上在第j秒内调度第ith个作业的利润为f(i，j)，为正。
我的目标是通过最多每P秒安排一次作业来最大化总利润。
我们可以假设所有作业总是可以在P秒内安排。
一切都是事先已知的，即离线问题。
同样0
依赖项的数量为O(n)。
这个问题容易吗？ [可能是由于有限的约束]
我的方法
为简单起见，首先假设一份工作的利润与时间无关。
也就是说，对于所有i，f(i，j)都与j无关，并且仅依赖于i。
这样，任何适合于P秒的拓扑排序都将起作用。
如果没有依赖性，那么我们也为每个工作选择最高的利润分配时间，这也很容易。
但是问题是，当一份工作的利润随时间而变化并具有依赖性时，在这种情况下，我无法想到任何通用算法。
我在处理作业之间的依赖关系时遇到麻烦，是否有任何资源可用于在线安排依赖单元任务的调度算法？
请分享任何有帮助的想法...
更新:我已经添加了各种参数的界限，因为它们可能是分析问题所必需的。
最佳答案
这是一个动态的编程问题。为了简单起见，我们假设所有利润均为非负数。
将F(i, j)定义为通过调度第i个作业以及所有依赖于该作业的事物(递归向下)，在第j个第二秒或更晚的时间(如果不可能)或-1来获得的最大利润。
如果F(i, j)的任何-1依赖项F(i_1, j+1)是-1，则i_1就是i。否则，它是(f(i, j)加上F(i_1, j+1)的总和)或F(i, j+1)中的较大者。
然后您的答案是所有没有依赖项的作业F(i, 0)的i的总和。
(如果没有无限的机器，这个问题将变得很难解决...)
这是一个如何使用您的问题来建模MAX-SAT方程的示例，其中每个子句都没有否定所有项或所有词都否定了。
假设我们有4个 bool 变量A，B，C和D。作为示例，假设我们要为方程(A && B) || (!A && !C) || (!B && !C && !D) || (C && D)做最大可满足性。 (其中!表示不是，&&表示和，||表示或。)
我们将J1 > J2标记用于必须在J1之前运行J2的作业。并在括号中分布，以便J1 > (J2, J3)表示J1) is a dependency for both J2 and J3`。
现在为 bool 模型建模，让我们设置12个作业。 A1 > A2 > A3，B1 > B2 > B3，C1 > C2 > C3和D1 > D2 > D3。然后，作业A2, B2, C2, D2必须在2或3的时间发生，并且 bool A是语句“A2在时间2发生”的真相。对于其他 bool 值也是如此。
无论这些工作在什么时间运行，所有这些工作都会获得1的利润。我们引入的工作数量是 bool 值的3倍，但是到目前为止，这很简单。
现在让我们为这些子句添加作业。如果这些作业中的每一个都在几秒钟内运行11或2，而在几秒钟内运行3，那么它们将获得1的 yield 。因此，当您找到 bool 值的设置以使真实的子句数量最大化时，将获得最大的利润。(A2, B2) > J1对(A && B)的真相进行建模。J2 > (A2, C2))对(!A && !C)的真相进行建模。J3 > (B2, C2, D2)对(!B && !C && !D)的真相进行建模。(C2, D2) > J4对(C && D)的真相进行建模。
这又是一个简单的转换，添加的作业数量等于子句的数量。
因此，我们正在通过调度对MAX-SAT问题进行建模。但是我们不能为所有模型建模。特别是，我们无法对带有(A && !B)的混合否定条件的子句建模。因此，即使MAX-SAT是NP-hard的，也可能没有此限制版本。但是，MAX-SAT的其他受限制版本(例如MAX-2SAT)往往具有NP严格性，而且我的直觉也是如此。
但是要证明或否定这种直觉，您应该在一个更合适的论坛上提问。像https://cs.stackexchange.com/一样。
关于c++ - 通过依赖关系最大化计划单元任务的利润，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27343038/