Algorithm Design Decisions

Foreword

While researching the different options of algorithms to implement, such as A*, DFS and BFS algorithms, a number of issues were recognized. These algorithms all require an increasingly large amount of memory space on large inputs. Furthermore, they all visited repeated states and did not provide any easy solutions for the homogeneous processor problem (all processors are equivalent so scheduling the same task partitions onto different processors is not required to be explored). As a result, this increases the amount of time required for these algorithms to solve the task scheduling problem.

More complex algorithms were researched; these were BBA*, IDA* and AO

BBA*

The BBA* was the first researched. This algorithm involved running a depth first search, adding tasks to the solution space with the inclusion of bounding techniques to remove the need to search through states which are already determined to be non-optimal.

As the algorithm progresses through the states in a depth first manner, it offers a significant reduction in memory from an A* implementation. Furthermore, the bounding techniques applied significantly increased the performance time.

It still has the homogeneous states issues which was addressed earlier; however, this can be dealt with by introducing additional features to the algorithm.

IDA*

The iterative deepening A* algorithm involves making iterations of depth first search, utilising a lower bound as a stopping point. This lower bound is incremented on failure to find a solution. This continues until a solution is found.

This algorithm also offers a reduced memory requirement, and increased time performance from the basic A* algorithms. This is because the lower limit reduces the time spent examining states which will not be currently optimal (for the current iteration).

IDA* also provides easy methods to solve the homogeneous processor and the duplicate state issues outlined above. The group was able to find an article which included pseudocode detailing how to do this.

However, the algorithm is slightly more difficult to implement than BBA*.

AO

The AO algorithm, which involves completing an allocation of tasks onto processors step, followed by ordering the tasks on each allocation, was a unique and complex algorithm. The main benefit the algorithm provided was the speed of operation on larger inputs.

This increased speed was caused by the algorithm eliminating the homogeneous processors problem, as well as reducing the number of repeated states which were looked over. AO proved to be more effective in these areas than the other algorithms in these areas. However, this required a large amount of overhead, meaning it would be inefficient for a small number of states. As the initial requirements suggested that only a small input this options was perhaps an inefficient algorithm for this particular problem.

Furthermore, there was not very much documentation for this type of algorithm on the internet, making it difficult to research further, and also making it difficult to debug and improve further.

Final Algorithm Decision (BBA*)

The BBA* algorithm was chosen to be implemented. This was because of the time performance it offered (for both large and small options), combined with its extensive online documentation. Finally, being able to remove the homogeneous state issue and duplicate states made it the best option.

Pseudocode for Base BBA*

BBA* Base
Initialise bestState to null
Initialise upperBound to sum of all task weights
Compute list of free tasks

For t in list of free tasks
	Recursive (t, 0)

Return bestState

Recursive function for BBA

If cost of allocation less than upperBound
Assign task to processor at earliest possible start time
Recompute list of free tasks

If current allocation has not been computed before
		If current solution contains all nodes and cost below :
			// New solution with a lower cost has been found
			Reassign upperBound and bestState
	
		For t in list of free tasks
			For p is between 0 and number of processors
				// Makes recursive call
				Recursive (t, p)
	
Sanitise Schedule (Backtrack) to allocation prior to adding task
Recompute list of free tasks