与依赖调度单元的任务实现利润最大化 [英] Maximize profit in scheduling unit tasks with dependencies

问题描述

问题我有n个作业在无限数量的机器具有依赖性的P秒调度之间的工作IE浏览器。对于每一项工作有一整套这是只有在这项工作完成后，以安排工作。该利润调度I ^日为J ^作业日第二个在任何机器上为f（I，J），这是肯定的。
而我的目标是通过安排每个作业只有一次最多P秒最大化利润总额。

Problem I have n jobs to schedule in P seconds on unlimited number of machines with dependencies between the jobs i.e . for every job there is a set of jobs which are to be scheduled only after this job is finished. The profit for scheduling the i^th job in j^th second on any machine is f(i,j), which is positive.
And my target is to maximize the total profit by scheduling each job exactly once in at most P seconds.

我们可以假设，所有的工作可以安排P中秒钟始终。

We can assume that all the jobs can be scheduled in P seconds always.

一切事先已知即脱机问题。

Everything is known in advance i.e. offline problem.

此外0℃，= F（I，J）其中; = B。对于所有I，J。

Also 0 <= f(i,j) <= B . for all i, j .

和依赖性的数量是为O（n）。

and number of dependencies is of O(n).

这方面的问题容易吗？ [可能是由于有限的约束]

Is this problem easy ? [may be due to finite constraints ]

我的做法
为简单起见，先假设一个工作的利润是与时间无关。
也就是说为f（I，J）是独立的J对所有的i和是仅依赖于岛
那么任何拓扑排序这符合P中秒会工作。
如果没有相关性，那么我们也选择了最高的利润给的时间为每个作业，这是很容易也。

My approach
For simplicity , first assume that for a job its profit is time independent.
That is f(i,j) is independent of j for all i and is dependent on only i.
Then any topological ordering which fits in P seconds will work.
If there is no dependency, then also we choose the highest profit giving time for each job and this is easy also.

但是问题是当利润的作业随时间具有相关性变化的，在这种情况下，我无法认为任何通用算法。

But problem is when profit for a jobs varies with time with dependencies, in this case, I am unable think any general algorithm.

我有处理依赖性作业之间的麻烦，是否有相关单位的任务调度算法的任何资源网上？

I am having trouble dealing with the dependencies between the jobs , Are there any resources for dependent unit tasks scheduling algorithms online ?

请分享任何想法，可以帮助...

Please share any idea which can help ...

更新：我已经添加了界限各种参数，因为它们可能需要对问题的分析

Update : I have added the bounds for various parameters as they may be required for analysis of the problem.

推荐答案

这是一个动态的规划问题。让我们假设为简单起见，所有的利润都是非负

This is a dynamic programming problem. Let's assume for simplicity that all profits are non-negative.

定义 F（I，J）来是进行从调度我次出现的最大利润工作，所有这一切依赖于它（递归向下）的东西或晚于Ĵ次出现第二或 1 如果这是不可能的。

Define F(i, j) to be the maximum profit to be made from scheduling the i'th job and all of the things that depend on it (recursively downwards) at or later than the j'th second, or -1 if that is impossible.

然后 F（I，J）是 1 如果 F（I_1， J + 1）是 1 任何依赖性 I_1 我。否则，它是（ F（I，J）加上的总和F（I_1，J + 1））或者 F（I，J + 1）。

Then F(i, j) is -1 if F(i_1, j+1) is -1 for any dependency i_1 of i. Otherwise it is the larger of (f(i, j) plus the sum of F(i_1, j+1)) or F(i, j+1).

然后你的答案是 F（I，0）所有作业我无依赖的总和

And then your answer is the sum of F(i, 0) for all jobs i with no dependencies.

（没有无限的机器这个问题将成为NP难...）

(Without unlimited machines this problem would become np-hard...)

下面是如何使用的问题来模拟MAX-SAT公式，每个条款并没有否定所有条款或全部条款否定的例子。

Here is an example of how to use your problem to model MAX-SAT equations where each clause has all terms not negated or all terms negated.

假设我们有4个布尔变量 A ， B ， C 和 D 。作为一个例子假设我们想要做的最大的满足性的方程（A和和B）|| （A和！＆安培;！C）|| （B＆安培;！＆安培;！C＆放大器;＆安培;！D）|| （C＆放大器;和D）。 ！（这里的 表示没有，＆功放;＆安培; 表示，并和 || 表示或）。

Suppose we have 4 boolean variables A, B, C, and D. As an example suppose that we want to do maximum satisfiability for the equation (A && B) || (!A && !C) || (!B && !C && !D) || (C && D). (Where ! means not, && means and, and || means or.)

让我们用符号 J1＆GT; J2 的职位，其中 J1 有 J2 之前运行。而分布于括号使 J1＆GT; （J2，J3）表示 J1）是一个依赖于两个 J2 和 J3 `

Let's use the notation J1 > J2 for jobs where J1 has to run before J2. And distribute over parentheses so that J1 > (J2, J3) means that J1) is a dependency for bothJ2andJ3`.

现在来模拟布尔值，让我们设立了12个就业岗位。 A1＆GT; A2＆GT; A3 ， B1＆GT; B2＆GT; B3 ， C1＆GT; C2＆GT; C3 和 D 1＆GT; D2＆GT; D3 。然后，作业 A2，B2，C2，D2 必须发生在时间 2 或 3 和布尔 A 是语句的真相 A2 发生在时间2 。同样地对于其他布尔值。

Now to model the booleans let's set up 12 jobs. A1 > A2 > A3, B1 > B2 > B3, C1 > C2 > C3, and D1 > D2 > D3. Then the jobs A2, B2, C2, D2 must occur at time 2 or 3, and the boolean A is the truth of the statement "A2 happens at time 2". And likewise for the other booleans.

所有这些工作都获得了利润 1 的无论他们在运行什么时候。我们推出了3倍更多的就业岗位为布尔值，但到目前为止，这很简单。

All of these jobs are given a profit of 1 no matter what time they run at. We introduced 3x as many jobs as booleans, but so far this is straightforward.

现在让我们增加就业机会的条款。所有这些工作都将有一个盈利的 11 ，如果它运行在几秒钟 2 或 3 和 1 否则。当你发现设置你的布尔值的最大化是真实子句的数目您最大的利润将因此达到了。

Now let's add jobs for the clauses. Each of these jobs will have a profit of 11 if it runs in seconds 2 or 3, and 1 otherwise. Your maximum profit will therefore be reached when you find settings for your booleans that maximize the number of clauses that are true.

（A2，B2）＆GT; J1 模式的真相。（A和和B）

J2＆GT; （A2，C2））模式的真相（A和！＆安培;！C）

J3＆GT; （B2，C2，D2）模式的真相（B＆安培;！＆安培;！C＆放大器;＆安培;！D）。

（C2，D2）＆GT; J4 车型的真相（C＆放大器;和D）。

这又是一个简单的转变，就业人数增加等于子句的数目。

This is again a straightforward transformation, with the number of jobs added equal to the number of clauses.

因此​​，我们模拟MAX-SAT问题的调度。但是，我们不能模拟所有的人。特别是，我们都没有办法模拟与混合否定像条款（A和＆安培;！B）。因此，即使MAX-SAT是NP难题，这是可能的，这受限版本不是。 MAX-SAT的但是其他受限版本，例如MAX-2SAT，往往是NP难，这是我的直觉，这将是一个为好。

So we're modeling MAX-SAT problems with scheduling. But we can't model all of them. In particular we have no way to model clauses with mixed negation like (A && !B). So even though MAX-SAT is NP-hard, it is possible that this restricted version is not. However other restricted versions of MAX-SAT, for instance MAX-2SAT, tend to be NP-hard, and it is my intuition that this one will be as well.

但这种直觉的证明或反证，你应该问一个更合适的论坛。如 http://cs.stackexchange.com/ 。

But for a proof or disproof of that intuition, you should ask on a more appropriate forum. Like http://cs.stackexchange.com/.

这篇关于与依赖调度单元的任务实现利润最大化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！