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 processorpublic 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.
精彩评论