My backtracking algorithm is built from my previous brute force algorithm it is different only by one extra comparison in the recursion. The algorithm searches a schedule tree depth first for the lowest cost schedule, each node in the tree contains three sums of time taken on the three processors. The tree is built and searched in a recursive function by adding the time for the task it is currently on to three new nodes on the tree and calls itself three times for the nodes it has just made. The function stops when it has added the last task and compared all the leaves to find the smallest. Below is a visual description of the tree:
This is what a tree would look like containing all the orderings of 2 tasks. In the nodes there are some thing like iPj, that is the time for task i on processor j, you can see that the leaves of the tree contain all the possible orderings.
The backtracking works by limiting the search to parts of the processor scheduling tree that certainly will contain a lower cost scheduling, and ignoring sub-trees that will always contain higher costs. Here is pseudo-code for the backtracking algorithm:
call(P1, P2, P3, addtask)if addtask = n do
if max(P1, P2, P3) ;SPMlt; lowest do
changelowest(max(P1,P2,P3))
else
if max(P1, P2, P3) ;SPMlt; lowest do
inc(addtask)
p1s.push(addtask)
call(
)
p1s.pop(popped)
p2s.push(addtask)
call(
)
p2s.pop(popped)
p3s.push(addtask)
call(
)
p3s.pop(popped)
taskweight is a two dimensional array that stores the costs for each task on each processor. The changelowest function simply reassigns lowest and stores the current stacks into a separate stacks.