Exact algorithm for task scheduling on N identical processors?

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.