v78*_*v78 13 c++ algorithm optimization maximize job-scheduling
问题我有几个工作要在P秒内安排在无限数量的工作机器上具有相关性的机器,即.对于每个工作,都有一组作业,只有在完成这项工作后才能安排.用于调度第i利润个 j中工作个第二任何机器上为f(I,J),它是正的.
我的目标是通过在最多P秒内完成一次调度每个作业来最大化总利润.
我们可以假设所有作业都可以在P秒内安排.
一切都是提前知道的,即离线问题.
0 <= f(i,j)<= B.对于所有我,j.
并且依赖数是O(n).
这个问题容易吗？[可能是由于有限的约束]
我的方法
为简单起见,首先假设对于一份工作来说,它的利润与时间无关.
即f(i,j)对于所有i而言与j无关,并且仅依赖于i.
然后任何适合P秒的拓扑排序都可以.
如果没有依赖关系,那么我们也为每个工作选择最高的利润给予时间,这也很容易.
但问题是,当工作的利润随着时间的推移随着依赖性而变化时,在这种情况下,我无法想到任何通用算法.
我在处理作业之间的依赖关系时遇到问题,在线调度算法的依赖单元任务是否有任何资源？
请分享任何有助于...的想法
更新:我已添加各种参数的边界,因为它们可能是分析问题所必需的.
这是一个动态规划问题。为了简单起见，我们假设所有利润都是非负的。
定义为在第 1 秒或晚于第 1 秒或在不可能的情况下调度第 1 个作业以及依赖于它的所有事物（递归向下）F(i, j)所获得的最大利润。ij-1
然后F(i, j)是-1ifF(i_1, j+1)是-1的任何依赖i_1项i。f(i, j)否则，它是（加上F(i_1, j+1)） 或 的较大者F(i, j+1)。
F(i, 0)然后你的答案是所有i没有依赖关系的作业的总和。
（如果没有无限的机器，这个问题将变得 np 困难......）
下面是如何使用您的问题对 MAX-SAT 方程进行建模的示例，其中每个子句的所有项均未否定或所有项均否定。
假设我们有 4 个布尔变量A、B、C和D。举个例子，假设我们想要使方程 达到最大可满足性(A && B) || (!A && !C) || (!B && !C && !D) || (C && D)。（其中!表示“不”，&&表示“和”，“and”||表示“或”。）
让我们使用必须在 之前运行的J1 > J2作业的表示法。并分布在括号上，这意味着J2 J3`。J1J2J1 > (J2, J3)J1) is a dependency for bothand
现在为了对布尔值建模，我们设置 12 个作业。 A1 > A2 > A3，B1 > B2 > B3，C1 > C2 > C3， 和D1 > D2 > D3。那么作业A2, B2, C2, D2必须发生在时间2或3，并且布尔值A是语句“A2发生在时间 2”的真值。对于其他布尔值也是如此。
1所有这些工作无论什么时间运行都会有利润。我们引入的作业数量是布尔值的 3 倍，但到目前为止这很简单。
现在让我们为子句添加作业。如果这些作业在几11秒钟内运行，则每一个作业都会有利润，否则。因此，当您找到能够最大化正确子句数量的布尔值设置时，您将获得最大利润。231
(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 难的，但这个受限版本可能不是 NP 难的。然而 MAX-SAT 的其他受限版本，例如 MAX-2SAT，往往是 NP 困难的，我的直觉是这个版本也是如此。
但要证明或反驳这种直觉，您应该在更合适的论坛上提问。就像https://cs.stackexchange.com/。