gpt4 book ai didi

java - N个相同处理器上任务调度的精确算法?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:53:43 24 4
gpt4 key购买 nike

我正在寻找精确的算法,以在 N 个相同的处理器中找到任务调度的最佳解决方案。

这个算法的时间并不重要,最重要的是一个最好的解决方案(最后一个任务完成时所有处理器的最小时间)。

理论上描述该算法的方程如下:P||Cmax

如果有人有算法(尤其是 Java)或伪代码,我将不胜感激。

我尝试编写自己的确切算法,但 id 不起作用:(。在下面的代码中,permUtil 是一个对应于排列的类。

方法参数:
- 任务 --> 索引标识任务和值时间的所有任务
- op --> assignment processor(分配任务的处理器)
//我们有一个全局数组 op processors proc,其中索引是标识,值是该处理器上的任务调度时间

public void schedule(Byte[] tasks, int op)
{
PermUtil<Byte> permA = new PermUtil<Byte>(tasks);
Byte[] a;
// permutation of all tasks
while ((a = permA.next()) != null)
{

// assign tasks
for(int i=1; i< a.length; i++)
{
// get the b set from i to end
Byte[] b = Arrays.copyOfRange(a, i, a.length);
// all permutations off b set
PermUtil<Byte> permB = new PermUtil<Byte>(b);
while ((b = permB.next()) != null)
{
// task on assign processor
proc[op] = sum(Arrays.copyOfRange(a, 0, i));
if (op < proc.length)
schedule(b, ++op);
else
{
proc[++op] = sum(b);
}
}
}
}
}

最佳答案

这是迭代所有可能分配的蓝图。在实际实现中,您应该将 long 替换为 BigInteger,并将数组初始化移到内部循环之外。

public void processOne(int nProcs, int nTasks, int[] assignment) {
/* ... */
}

public void checkAll(int nProcs, int nTasks) {
long count = power(nProcs, nTasks);
/* Iterate over all the possible assignments */
for (long j = 0; j < count; j++) {
int[] assignment = new int[nTasks];
for (int i = 0; i < nTasks; i++)
assignment[i] = (int) (j / power(nProcs, i) % nProcs);
processOne(nProcs, nTasks, assignment);
}
}

诀窍是用数字编码赋值。由于赋值表示 nTasks 个决策,每个决策都有 nProcs 个结果,因此可以将其视为具有 nTasks 数字。每个这样的数字都对应一个有效的分配,并且每个分配在这个范围内都有一个唯一的数字。迭代所有赋值很容易,因为我们基本上是在整数范围内迭代。

您所要做的就是填写 processOne(int, int, int[]) 函数,这应该相当简单。

关于java - N个相同处理器上任务调度的精确算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4684104/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com