我在寻找确切的算法，该算法找到N个相同的处理器上任务计划的最佳解决方案。

该算法的时间并不重要，最重要的是最好的解决方案（所有处理器miminum时间时的最后一个任务将完成）。

在理论方程描述这个算法如下：点||的Cmax

如果任何人有一种算法（尤其是在Java中）或伪code我会grathefull寻求帮助。

我试着写我自己的确切algoritm但ID不会工作:(在下面的permUtil的code是对应的置换类。

方法的args： - 任务 - >所有任务，其中索引标识任务和价值的时候 - 操作 - >分配处理器（处理器，它分配一个任务） //我们有一个全球性的数组运算处理器PROC，其中指数是身份和价值的任务计划时间在该处理器

 公共无效时间表（字节[]任务，INT运）
{
    PermUtil＆LT;字节＆GT;博=新PermUtil＆LT;字节＆GT;（任务）;
    byte []的一个;
    //所有任务排列
    而（（A = permA.next（））！= NULL）
    {

        //分配任务
        的for（int i = 1; I＆LT;则为a.length;我++）
        {
            //获取对B组由我来结束
            字节[] B = Arrays.copyOfRange（A，I，则为a.length）;
            //关闭B设置的所有排列
            PermUtil＆LT;字节＆GT; permB =新PermUtil＆LT;字节＆GT;（二）;
            而（（B = permB.next（））！= NULL）
            {
                //在分配处理器任务
                PROC [OP = SUM（Arrays.copyOfRange（一，0，I））;
                如果（OP＆LT; proc.length）
                    时间表（B，++运算）;
                其他
                {
                    PROC [++ OP = SUM（B）;
                }
            }
        }
    }
}
 

解决方案

下面是遍历所有可能分配的蓝图。 在实际的实现，你应该替换长与的BigInteger ， 和移动数组初始化内环以外。

 公共无效processOne（INT nProcs，诠释nTasks，INT []分配）{
    / * ... * /
}

公共无效checkAll（INT nProcs，诠释nTasks）{
    长计数=功率（nProcs，nTasks）;
    / *遍历所有可能的分配* /
    为（长J = 0; J＆LT;计数; J ++）{
        INT []赋值=新INT [nTasks]
        的for（int i = 0; I＆LT; nTasks;我++）
            分配[I] =（INT）（J /功率（nProcs，I）％nProcs）;
        processOne（nProcs，nTasks，分配）;
    }
}
 

关键是要连接code在一些分配。由于分配再presents nTasks 的决定，每个 nProcs 的结果，它可以被看作是一个数量在基 nProcs 为 nTasks 数字。每一个这样的号码对应一个有效的赋值，每一个任务在该范围内的唯一号码。可以很容易地遍历所有的任务，因为我们基本上遍历一个整数范围。

所有你需要做的就是填写 processOne（INT，INT，INT []）功能，这应该是相当简单的。

I'm looking for exact algorithm which find the best solution on task schedule in N identical processors.

The time of this algorithm is not important, the most important is one best solution (miminum time of all processors when the last task will be finished).

In theory equation describing this algorithm is as follows: P||Cmax

If anyone has an algorithm (especially in Java) or pseudocode I will be grathefull for help.

I tried write my own exact algoritm but id doesn't work :(. In the code below the permUtil is a class which corresponds for permutations.

Method args: - tasks --> all task where index identity the task and value time - op --> assignment processor (processor which assign a tasks) // we have a global array op processors proc where index is identity and value is task schedule time on this processor

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);
                }
            }
        }
    }
}

Here's a blueprint of iterating over all the possible assignments. In a real implementation you should replace long with BigInteger, and move the array initialization outside the inner loop.

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);
    }
}

The trick is to encode an assignment in a number. Since an assignment represents nTasks decisions, each with nProcs outcomes, it can be thought of as a number in base nProcs having nTasks digits. Every such number corresponds to a valid assignment and every assignment has a unique number in such range. It's easy to iterate over all the assignments, since we're basically iterating over a range of integers.

All you have to do is to fill in the processOne(int, int, int[]) function, which should be rather straightforward.